воскресенье, 23 декабря 2012 г.

«Разрешите Вас пригласить...»


В последнее время меня стали часто приглашать где-то выступить, с кем-то встретиться, провести онлайн-занятие по Skype и т.п. С одной стороны, приятно, конечно, что твоё мнение кто-то ценит. С другой стороны, тяжело отказывать людям, и каждому приходится долго объяснять, почему я часто отказываюсь от подобных предложений.

Одну из причин таких приглашений я хорошо понимаю: методистам различных центров нужна отчётность. Фразу «мы почитали материалы на сайте X» к отчёту не подошьёшь, а формулировку «мы приглашали на семинар X» — запросто.

Давайте проанализируем ситуацию с точки зрения системного подхода. В системном подходе главное — это цель. Какую цель мы преследуем в данном случае? Почему недостаточно материалов, размещенных на сайте, и важна именно личная встреча? Как правило, на эти вопросы нет вразумительных ответов. Поэтому цели нет, и смысла в таких встречах тоже нет, это будет просто пустая трата времени для обеих сторон. Я уверен, что мы все можем потратить это время нашей жизни более продуктивно. Поскольку конец света мы уже пережили, как сказал один известный в Рунете персонаж, «теперь не отвертишься, надо работать».

Всё, что есть у меня интересного, я выкладываю на сайт, с этой целью он и был создан. Маловероятно, что я смогу сказать что-то принципиально отличное от уже размещённых материалов. Если речь идёт о материалах для подготовки к ЕГЭ по информатике, они лежат в открытом доступе, я написал всё что смог на данный момент, по каждому типу задач. Адекватные вопросы всегда можно задать на форуме egekp.unoforum.ru, а в случае необходимости — по электронной почте, которая также доступна.

В то же время я с удовольствием принимаю все приглашения, когда понимаю, что в ходе встречи будет получен конкретный результат, важный для всех участников. Некоторые материалы таких выступлений можно найти на сайте.

На некоторые вопросы, которые встречаются чаще других, хочется ответить сразу и для всех:

Вопрос: «Коллеги хотят, чтобы Вы им лично объяснили, как решать задачи ЕГЭ (B15, C3, C4 и т.п.). Возможно ли это?»

Все способы решения этих задач, которые мне известны, изложены на сайте в материалах для подготовки к ЕГЭ. Других способов я пока не знаю. Если что-то в этих материалах непонятно, можно задать вопрос на форуме egekp.unoforum.ru или, если никто не ответил на форуме, по электронной почте.

Вопрос: Как Вы относитесь к новым ФГОС? Как они повлияют на Вашу работу?

Я занимаюсь информатикой или, как принято называть её за рубежом, computer science. Для меня совершенно ясно, что её развитие идет само по себе, и ФГОСы в одной отдельно взятой стране на него никак не влияют. ФГОСы изменяют только слова, которые используют методисты для обоснования программ, учебников и пособий. Поэтому все вопросы по этому поводу (а также по поводу портфолио, инноваций и нанотехнологий) нужно адресовать методистам.

Ярлыки: , , ,

Автор: КП @ 16:20   Комментарии: 4

вторник, 13 ноября 2012 г.

Компьютерный ЕГЭ: что вы хотели знать, но боялись спросить


В конце октября во многих регионах была проведена апробация ЕГЭ по информатике в компьютерной форме (см. материалы для проведения экзамена). В связи с этим снова стал актуальным вопрос о соответствии компьютерного ЕГЭ (КЕГЭ) действующим санитарным нормам, которые ограничивают время работы школьников за компьютерами. Учителя информатики хорошо помнят, что этот вопрос постоянно задавался различным официальным лицам, связанным с проведением ЕГЭ, но ни от одного из них не удалось получить вразумительного ответа.

В регламенте проведения КЕГЭ по этому поводу есть единственная фраза, сохраняющая интригу:

«...в части пребывания участников КЕГЭ за компьютером рекомендуется соблюдать перерывы в работе через каждые 25-30 минут, в течение которых участник КЕГЭ может продолжить работу с бумажным экземпляром КИМ и черновиком.»

Рекомендация — это ведь не обязательное требование, то есть фактически никаких строгих ограничений нет.

Давайте читать нормативные документы. Их два.

Во-первых, есть СанПиН 2.2.2/2.4.1340-03. «Гигиенические требования к персональным электронно-вычислительным машинам и организации работы». В нём имеется Приложение 7 «Предложения по организации работы с ПЭВМ», в котором нам наиболее интересен раздел 4 «Организация занятий с ПЭВМ детей школьного возраста и занятий с игровыми комплексами на базе ПЭВМ детей дошкольного возраста»
    4.1. Рекомендуемая непрерывная длительность работы, связанной с фиксацией взора непосредственно на экране ВДТ, на уроке не должна превышать:
- для обучающихся в I-IV классах — 15 мин;
- для обучающихся в V-VII классах — 20 мин;
- для обучающихся в VIII-IX классах — 25 мин;
- для обучающихся в Х-XI классах на первом часу учебных занятий 30 мин, на втором — 20 мин.
    4.2. Оптимальное количество занятий с использованием ПЭВМ в течение учебного дня для обучающихся I-IV классов составляет 1 урок, для обучающихся в V-VIII классах - 2 урока, для обучающихся в IX-XI классах - 3 урока.
    ...
  4.7. Внеучебные занятия с использованием ПЭВМ рекомендуется проводить не чаще 2 раз в неделю общей продолжительностью:
- для обучающихся в II-V классах не более 60 мин;
- для обучающихся VI классах и старше — не более 90 мин.
    Время проведения компьютерных игр с навязанным ритмом не должно превышать 10 мин для учащихся II-V классов и 15 мин для учащихся более старших классов. Рекомендуется проводить их в конце занятия.
    ...
    4.16. Не допускается одновременное использование одного ВДТ для двух и более детей независимо от их возраста.

Но вот что важно: Приложение 7, которое мы только что цитировали, имеет статус рекомендованное и на регистрацию в Минюст РФ не представлялось! Поэтому, строго говоря, требовать его выполнения нельзя — оно не обязательно.

Во-вторых, есть СанПиН 2.4.2.2821-10. «Cанитарно-эпидемиологические требования к условиям и организации обучения в общеобразовательных учреждениях», который говорит, что «продолжительность непрерывного использования в образовательном процессе технических средств обучения устанавливается согласно таблице 5»:

Таблица 5

Классы Непрерывная длительность (мин.), не более
Работа с изображением на индивидуальном
мониторе компьютера и клавиатурой
1-2 ... 15 ...
3-4 ... 15 ...
5-7 ... 20 ...
8-11 ... 25 ...
Эти нормативы имеют статус обязательных, но они ограничивают только время, которое ученик смотрит на экран, не отрываясь. Никаких ограничений типа «в течение урока не более чем...» или «в течение учебного дня не более чем...» здесь нет!

Есть в России организация, в чьи задачи входит контроль соблюдения санитарных норм в всех областях — это Роспотребнадзор. На сайте Роспотребнадзора есть страница, откуда граждане могут отправить сообщение и «выразить свое мнение по какому-либо вопросу, дать свой комментарий, изложить жалобу или предложение». Этой возможностью и воспользовался автор этого блога, поинтересовавшись, какими нормативными актами ограничивается время, проводимое учащимися за компьютерами во время компьютерного ЕГЭ.

Через несколько дней почта доставила ответ заместителя руководителя Управления Роспотребнадзора по г. Санкт-Петербургу Н.С. Башкетовой, которым хочется поделиться с коллегами:

Это официальный документ, подписанный официальным лицом главной в России организации, которая следит за соблюдением санитарных норм. И он всё ставит на свои места. Из него следует, что в России нет документа, который в обязательном порядке ограничивает время, проводимое учеником за компьютером в течение учебного дня, поэтому никаких проблем с выполнением санитарных норм у организаторов компьютерного ЕГЭ не возникает.

Ярлыки: , , ,

Автор: КП @ 14:51   Комментарии: 15

вторник, 23 октября 2012 г.

Ещё раз про однозначное декодирование

Введение

В последние годы в заданиях КИМ ЕГЭ по информатике, как в демо-версиях, так и в реальных вариантах, неизменно присутствует задача на кодирование данных следующего типа [1, задание А9]:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А — 00, Б — 01, В — 100, Г — 101, Д — 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Д — 11; 2) это невозможно; 3) для буквы Г — 10; 4) для буквы Д — 10

Как показывает практика, эта задача вызывает серьезные трудности не только у многих учеников, но даже у учителей информатики.

Нужно сказать, что этот материал практически не рассматривается в существующих школьных учебниках информатики, поэтому все (как ученики, так и учителя) вынуждены разбираться самостоятельно. В то же время вузовские учебники [2-5], где соответствующая теория изложена строго и научно, достаточно сложны для понимания. Попробуем разобраться в сути кодирования и декодирования на школьном уровне, то есть так, как можно объяснить ученикам 8-11 классов.

В чём проблема?

Предположим, нам нужно передать сообщение по цифровым каналам связи. Для этого его необходимо закодировать, то есть сопоставить каждому символу исходного сообщения некоторый код (кодовое слово). Для определенности будем использовать двоичные коды, то есть последовательности нулей и единиц.

Пример 1. Пусть для кодирования фразы «МАМА МЫЛА ЛАМУ» выбран такой код:
МАЫЛУпробел (1)
0010101011
Коды букв «сцепляются» в одну битовую строку и передаются, например, по сети:
МАМА МЫЛА ЛАМУ → 0010011100010111010010
Эта цепочка битов приходит в пункт назначения, и тут возникает проблема — как восстановить исходное сообщение (конечно, при условии, что мы знаем код, то есть знаем все пары «символ–кодовое слово», которые использовались при кодировании).

Итак, мы получили 0010011100010111010010. Легко понять, что при использовании кода (1) раскодировать такое сообщение можно самыми разными способами. Например, можно предположить, что оно составлено только из букв А (код 1) и Л (код 0). Тогда получаем
ЛЛАЛЛАААЛЛЛАЛАААЛАЛЛАЛ
В общем, ни мамы, ни ламы.

Определение. Код называется однозначно декодируемым, если любое кодовое сообщение можно расшифровать единственным способом (однозначно).

Сказанное выше означает, что код (1) НЕ является однозначно декодируемым. Как же определить, является ли заданный код однозначно декодируемым? Этим вопросом мы и займемся.

Равномерные коды

Проблема состоит в том, чтобы правильно разбить полученную битовую цепочку на отдельные кодовые слова. Для того, чтобы её решить, можно, например, использовать равномерный код, то есть код, в котором все кодовые слова имеют одинаковую длину. Например, в нашей фразе 6 символов, поэтому можно использовать 3-битный код (который позволяет закодировать 8 = 23 различных символов).

Пример 2. Закодируем фразу из примера 1, используя код:
МАЫЛУпробел (2)
000001010011100101
Получаем закодированное сообщение
МАМА МЫЛА ЛАМУ → 000001000001101000010011001101011001000100
Длина этого сообщения — 42 бита вместо 22 в предыдущем варианте, зато его легко разбить на отдельные кодовые слова и раскодировать («_» обозначает пробел): 
000 001 000 001 101 000 010 011 001 101 011 001 000 100
 М   А   М   А   _   М   Ы   Л   А   _   Л   А   М   У
Видим, что равномерные коды неэкономичны (закодированное сообщение в примере 2 почти в два раза длиннее, чем в примере 1), но зато декодируются однозначно.

Неравномерные коды

Для того, чтобы сократить длину сообщения, можно попробовать применить неравномерный код, то есть код, в котором кодовые слова, соответствующие разным символам исходного алфавита, могут иметь разную длину.

Пример 3. Используем для кодирования фразы из примера 1 следующий код:
МАЫЛУпробел (3)
01001011100101011
Получаем
МАМА МЫЛА ЛАМУ → 0100010011011011100001110000011010
Здесь 34 бита. Это, конечно, не 22, но и не 42.

Несложно показать, что эта битовая цепочка декодируется однозначно. Действительно, первая буква — М (код 01), потому что ни одно другое кодовое слово не начинается с 01. Аналогично определяем, что вторая буква — А. Действительно, за 01 следует 00 (код буквы А) и никакое другое кодовое слово не начинается с 00. Это же свойство, которое называется условием Фано, выполняется не только для кодовых слов 01 и 00, но и кодовых слов всех других букв (проверьте это самостоятельно).

Условие Фано. Никакое кодовое слово не совпадает с началом другого кодового слова.

Коды, для которых выполняется условие Фано, называют префиксными (префикс слова — это его начальный фрагмент). Все сообщения, закодированные с помощью префиксных кодов, декодируются однозначно.
Префиксные коды имеют важное практическое значение — они позволяют декодировать символы полученного сообщение по мере его получения, не дожидаясь, пока всё сообщение будет доставлено получателю.

Упражнение. Расшифруйте сообщение, закодированное кодом (3). При расшифровке кода очередной буквы не заглядывайте вперёд!
1000001101011010001001101101110000
Термины «условие Фано» и «префиксный код» не используются в заданиях ЕГЭ и ГИА, однако для решения этих задача важно, чтобы ученики понимали содержание условия Фано.

Пример 4. Рассмотрим ещё один код
МАЫЛУпробел (4)
10001101001010111
Ясно, что он не является префиксным: код буквы А (00) совпадает с началом кода буквы Л (001) и код пробела (11) совпадает с началом кода буквы Ы (11). Закодированное сообщение
МАМА МЫЛА ЛАМУ → 1000100011101101001001100100100101
также имеет длину 34 бита, как и при использовании кода (3). Начнем раскодировать с начала. Ясно, что первой стоит буква М, потому что ни один другой код не начинается с 10. Затем — комбинация 001, которая может быть кодом буквы Л или кодом буквы А (00), за которым следует код буквы Ы или пробела. Получается, что для декодирования сообщения нам нужно «заглядывать вперёд», что очень неудобно.

Попробуем декодировать с конца битовой строки. Последние биты 0101 могут представлять только букву У, следующие 10 — только букву М и т.д. Можно проверить, что теперь сообщение однозначно декодируется с конца! Это происходит потому, что выполняется условие, которое можно назвать «обратным» условием Фано: никакое кодовое слово не совпадает с окончанием другого кодового слова. Коды, для которых выполняется обратное условие Фано, называют постфиксными (постфикс или суффикс слова — это его конечный фрагмент). В этом случае тоже обеспечивается однозначное декодирование. Таким образом,

Сообщение декодируется однозначно, если для используемого кода выполняется прямое или обратное условие Фано.

Обратим внимание на то, что условие Фано (и обратное условие Фано) — это достаточное, но не необходимое условие однозначной декодируемости. Это значит, что
  • для однозначной декодируемости достаточно выполнение хотя бы одного из двух условий, или прямого, или обратного;
  • могут существовать коды, для которых не выполняется ни прямое, ни обратное условие Фано, но они, тем не менее, обеспечивают однозначное декодирование.
Наиболее интересен второй вывод, который сразу вызывает два вопроса: 1) что это за коды? и 2) как в общем случае установить, что код декодируется однозначно? Обсудим это в следующем разделе.

Однозначно декодируемые коды

Пример 5. Рассмотрим код, предназначенный для кодирования сообщений, состоящих только из букв А, Б и В:
АБВ (5)
011010
Так как код буквы А (0) совпадает как с началом, так и с концом кода буквы В (010), для этого кода не выполняются ни прямое, ни обратное условие Фано. Поэтому пока мы не можем с уверенностью сказать, декодируется ли он однозначно.

Закодируем сообщение 
АББААВВА → 01111000100100
и попытаемся раскодировать эту строку, используя код (5). В первую очередь, замечаем, что две соседние единицы могут появиться только при использовании буквы Б (код 11), поэтому сразу выделяем две таких группы:
0ББ000100100
Здесь жёлтым фоном выделена уже декодированная часть сообщения. В оставшейся части единица может появиться только в коде буквы В (010), в битовой строке находим две такие группы:
0ББ00ВВ0
Оставшиеся нули — это коды букв А. Анализ алгоритма показывает, что такой код всегда однозначно декодируется.

Полный ответ на вопрос об однозначной декодируемости получил в начале 1960-х годов советский математик Ал.А. Марков, предложивший решение с помощью графов [2]. Продемонстрируем его метод на примере.

Пример 6. Рассмотрим код
АБВГД (6)
0101001111101
Здесь не выполняется ни «прямое», ни «обратное» условие Фано, поэтому возможно, что декодировать сообщение однозначно не удастся. Но утверждать это заранее нельзя.

Следуя методу Ал.А. Маркова, построим граф следующим образом:
  1. Определяем все последовательности (строки), которые
       а) совпадают с началом какого-то кодового слова и одновременно с концом какого-то кодового слова и
       б) сами не являются кодовыми словами.
    В данном случае это две последовательности:
       0 (начало кода буквы А и конец кода буквы Б) и
       1 (начало кода буквы Г и конец кода буквы Д);
       10 (начало кода буквы Д и конец кода буквы Б);
    последовательности 01 и 11 не учитываем, потому что они совпадают с кодами букв А и Г;
  2. Добавляем к этому множеству {0, 1, 10} пустую строку, которую обычно обозначают греческой буквой Λ; элементы полученного множества {Λ, 0, 1, 10} будут вершинами графа:
  3. Соединяем вершины дугами (направленными ребрами) по такому правилу: две вершины X и Y соединяются дугой, если последовательная запись кода вершины X, кода некоторой буквы (или нескольких букв) и кода вершины Y дает код ещё одной буквы:
    Надпись «W→Z» на дуге, ведущей из X в Y, означает, что если между словами X и Y вставить последовательность букв W (она может состоят из нескольких символов), то полученная цепочка кодов совпадёт с кодом буквы Z. Например, последовательная запись пустой строки (Λ), кода буквы А (01) и цепочки 0 дает цепочку 010 (код буквы Б); поэтому рисуем дугу из вершины «Λ» в вершину «0» и у этой дуги пишем «А→Б», и т.д. Поскольку код буквы Г можно записать как 11 = 1Λ1, у вершины «1» появляется петля «Λ→Г».
Результат Ал.А. Маркова состоит в следующем:

Код является однозначно декодируемым тогда и только тогда, когда в построенном таким образом графе нет ориентированных циклов, включающих вершину Λ.

Иначе говоря,
  1. если есть сообщение, которое декодируется неоднозначно, то в графе есть цикл, проходящий через вершину Λ;
  2. если в графе есть цикл, проходящий через вершину Λ, то можно построить сообщение, которое декодируется неоднозначно; для этого нужно, проходя по циклу, последовательно выписывать коды всех встречающихся вершин и дуг;
С сайта автора можно скачать программу на языке Python 3, которая строит граф Ал.А. Маркова, обнаруживает в нём циклы, проходящие через вершину Λ, и определяет соответствующие им кодовые последовательности, которые декодируются неоднозначно.

В нашем графе есть, по крайней мере, четыре таких цикла:
  1. цикл «Λ0Λ», соответствующий сообщению ΛА0ГΛ = 01011; это сообщение может быть расшифровано как АВ и как БГ;
  2. цикл «Λ1Λ», соответствующий сообщению ΛА1АΛ = 01101; это сообщение может быть расшифровано как АД и как ВА;
  3. цикл «Λ01Λ», соответствующий сообщению ΛА01АΛ = 010101; это сообщение может быть расшифровано как ААА и как БД;
  4. цикл «Λ0101Λ», соответствующий сообщению ΛА0101АΛ = 01010101; это сообщение может быть расшифровано как АБД и как БДА;
Кроме того, у вершины «1» есть петля, которая даёт более длинные циклы «из Λ в Λ». Действительно, проходя по стрелкам из вершины Λ, мы приходим в вершину 1, там «вертимся» какое-то количество раз, и возвращаемся обратно в вершину Λ, замыкая цикл. Поэтому неоднозначно декодируется любая последовательность вида 01…101, где многоточие обозначает любое количество единиц. Например, сообщение 0111101 может быть декодировано как АГД или ВГА.

Таким образом, код (6) не обладает свойством однозначной декодируемости.

Проверим таким же способом код (5), который, как мы уже выяснили, не является ни префиксным, ни постфиксным. Множество последовательностей, которые совпадают с началом и концом кодовых слов, состоит из пустой строки и единицы: {Λ, 1}. Граф, построенный с помощью приведённого выше алгоритма, содержит два узла и одну петлю:

В этом графе нет цикла, содержащего вершину Λ, поэтому любое сообщение, записанное с помощью такого кода, декодируется однозначно. Выше мы показали это с помощью простых рассуждений.

Нужно отметить, что на практике применяются, главным образом, префиксные коды, поскольку они позволяют декодировать сообщение по мере его получения, не дожидаясь окончания приёма данных.

Ещё примеры

Пример 7. Рассмотрим задачу А9 из демо-варианта КИМ ЕГЭ-2013 [1], которая сформулирована в начале статьи. Нужно оптимизировать код
А — 00, Б — 01, В — 100, Г — 101, Д — 110
выбрав один из вариантов
1) для буквы Д — 11    2) это невозможно
3) для буквы Г — 10    4) для буквы Д — 10
Решение. Сначала давайте посмотрим на исходный код, приведённый в условии. Можно заметить, что он префиксный — для него выполняется условие Фано: ни один из трехбитных кодов не начинается ни с 00 (код А), ни с 01 (код Б). Поэтому сообщения, закодированные с помощью такого кода, декодируются однозначно.

Заметим, что «обратное» условие Фано не выполняется: код буквы А (00) совпадает с окончанием кода буквы В (100), а код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Теперь проверим, что получится, если сократить код буквы Д до 11 (вариант 1). Свойство однозначной декодируемости может быть потеряно только тогда, когда в результате такого сокращения нарушится условие Фано, то есть код буквы Д совпадёт с началом какого-то другого кодового слова. Видим, что этого не произошло — нет других кодовых слов, которые начинаются с 11, поэтому вариант 1 — это и есть верное решение.

Остается убедиться, что варианты 3 и 4 не подходят. Если мы сократим код буквы Г до 10 (вариант 3), условие Фано оказывается нарушенным, так как теперь код буквы Г (10) совпал с началом кода буквы В (100). Одновременно нарушено и «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100). Но, как мы знаем, при этом код может всё-таки быть однозначно декодируемым.

Конечно, можно построить граф, как было сделано выше, и проверить, есть ли в нём циклы, включающие вершину Λ. В данном случае граф выглядит так:

Здесь два цикла, проходящих через вершину Λ (не считая петли у вершины 0):
  1. цикл, соответствующий сообщению ΛГ0Λ1АΛ = 100100; это сообщение может быть расшифровано как ГБА или как ВВ;
  2. цикл, соответствующий сообщению ΛГ0Λ1ГΛ = 100110; это сообщение может быть расшифровано как ГБГ или как ВД.
Таким образом, вариант 3 не обеспечивает однозначную декодируемость сообщений.

Построение и анализ графа — дело достаточно трудоемкое и требующее аккуратности. Обычно в таких случаях значительно легче просто подобрать последовательность, которая может быть декодирована двумя разными способами.

Наконец, нужно убедиться, что вариант 4 не удовлетворяет условию. Если мы сократим код буквы Д до 10, условие Фано оказывается нарушенным, так как теперь код буквы Д (10) совпал с началом кода буквы В (100). Как и раньше, нарушено «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100) и код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Построим граф по методу Ал.А. Маркова:

Здесь два цикла, проходящих через вершину Λ (не считая петли у вершины 0):
  1. цикл, соответствующий сообщению ΛД0Λ1АΛ = 100100; это сообщение может быть расшифровано как ДБА или как ВВ;
  2. цикл, соответствующий сообщению ΛД0Λ1БΛ = 100101; это сообщение может быть расшифровано как ДББ или как ВГ.
Таким образом, вариант 4 также не соответствует условию. Поэтому правильный ответ — 1.

Пример 8. Оптимизируйте код 
А — 11, Б — 10, В — 011, Г — 000, Д — 001,
сохранив свойство однозначной декодируемости сообщений. Выберите один из вариантов:
1) для буквы Г — 00    2) это невозможно
3) для буквы В — 01    4) для буквы Б — 1
Решение. Определим, за счёт чего обеспечивается однозначная декодируемость исходного кода. Легко видеть, что код префиксный — для него выполняется условие Фано: ни одно из трёхбитовых кодовых слов не начинается ни с 11 (код А), ни с 10 (код Б). В то же время, обратное условие Фано не выполняется, потому что код буквы А (11) совпадает с окончанием кода буквы В (011).

Проверим вариант 1 — сократим код буквы Г до 00. При этом нарушилось условие Фано, которое обеспечивало однозначную декодируемость исходного варианта: теперь код буквы Г (00) совпадает с началом кода буквы Д (001). Но и обратное условие Фано тоже не выполняется для пары букв А-В. Поэтому можно предположить, что такой код не обладает свойством однозначной декодируемости. И действительно, легко находится цепочка 001011, которую можно раскодировать как ГБА (00 10 11) или ДВ (001 011).

Рассмотрим вариант 3 — сократим код буквы В до 01. При этом условие Фано выполняется, поскольку ни одно из кодовых слов не начинается с 01, то есть код является префиксным и однозначно раскодируется. Это и есть правильный ответ.

На всякий случай проверяем вариант 4 — сокращает код буквы Б до 1. При этом код перестает быть префиксным, и обратное условие Фано также не выполнено (код буквы Б совпадает с началом и концом кода буквы А). Сразу понятно, что последовательность 11 можно раскодировать как А или как ББ, поэтому этот вариант неверный.

Выводы

В заметке выполнен подробный анализ задачи на кодирование, которая предлагается на ЕГЭ в последние несколько лет. Нужно заметить, что в нём затрагивается вузовский курс дискретной математики. Понятно, что нельзя требовать от школьников знания теорем Ал.А. Маркова об однозначном декодировании, но учителю полезно более глубоко представлять себе эти вопросы, которые можно разбирать на факультативах. В качестве дополнительной литературы по этой теме можно рекомендовать [3-5].

С точки зрения практического подхода, для решения всех известных автору реальных задач подобного типа достаточно найти вариант, при котором выполняется условие Фано или обратное условие Фано (одно из двух!).

Литература

  1. Демонстрационный вариант контрольных измерительных материалов единого государственного экзамена 2013 года по информатике и ИКТ (проект).
  2. Ал.А. Марков, Введение в теорию кодирования. — М.: Наука, 1982.
  3. С.В. Яблонский, Введение в дискретную математику. — М.: Наука, 2000.
  4. Л.П. Жильцова. Современные проблемы теории кодирования. Учебно-методические материалы по программе повышения квалификации «Информационные технологии и компьютерное моделирование в прикладной математике». — Нижний Новгород: 2007.
  5. Л.П. Жильцова, Т.Г. Смирнова. Основы теории графов и теории кодирования в примерах и задачах: Учебное пособие. — Нижний Новгород: Издательство Нижегородского госуниверситета, 2008.
Автор благодарит М.А. Ройтберга за полезные замечания по материалу статьи и Л.Н. Евич за обсуждении вопросов однозначного декодирования на форуме egekp.unoforum.ru.


Ярлыки: , , ,

Автор: КП @ 19:54   Комментарии: 16

пятница, 5 октября 2012 г.

Break или не break?


В общении с коллегами — учителями информатики — я много раз сталкивался с твёрдым убеждением, что использование оператора break для досрочного выхода из цикла — это «неграмотно», «грязный хак», «не соответствует принципам структурного программирования» и вообще «я своим ученикам такое не зачту». В то же время общение с профессиональными программистами показывает, что такой прием на практике применяется очень часто, потому что это удобно и в большинстве случаев делает программу более понятной.

Такой «разброд» имеет совершенно объяснимые причины. Большинство преподавателей, с одной стороны, когда-то заучили, что структурное программирование — это хорошо, а любое отступление от него — это плохо. С другой стороны, сами они уже фактически отошли от промышленного программирования: я могу на пальцах одной руки пересчитать знакомых (в том числе и по Интернету) учителей информатики, которые сами написали что-то стóящее. Таким образом, наблюдаем закон Дж.Б. Шоу в действии.

Попробуем разобраться в сути вещей. Оператор break — это фактически оператор перехода, знаменитый GOTO, который в 1970-е годы был морально уничтожен, прежде всего, стараниями «отца структурного программирования» Эдсгера Дейкстры [1]. Однако сами «отцы» хорошо понимали, что программа без GOTO ещё не становится автоматически структурной программой. Поэтому появилось на свет эссе Дональда Кнута «Структурное программирование с операторами GOTO» [2]. Кнут писал (перевод мой):

«Другими словами, мы не должны просто удалять операторы GOTO из-за того, что сейчас модно это делать; присутствие или отсутствие операторов GOTO — это не главный вопрос. Истинная цель состоит в том, чтобы формулировать наши программы таким образом, чтобы их было легко понимать.»

Посмотрим, как обстоит дело с пониманием программ, содержащих циклы с операторами break и сравним их с программами, где операторов break умышленно избегают.

Пример 1. С клавиатуры вводятся числа, ввод заканчивается числом 999. Вычислить сумму введенных чисел.

Вот решение с использованием break:
s := 0;
while True do begin
  Readln(x);
  if x = 999 then break;
  s := s + x;
end;
На взгляд автора, этот алгоритм очень хорошо соответствует словесному описанию: «строим цикл, выход из которого происходит при получении числа 999».

Теперь посмотрим на «кошерные» альтернативы. Нужно как-то выполнить те же действия (то есть, выйти из цикла при получении числа 999), не используя оператор выхода из цикла.

Во-первых, можно поставить условие цикла x <> 999, но при этом нужно будет инициализировать переменную x до цикла каким-то «магическим числом», отличным от 999, например, 1 (или 998 :-). Программист, который будет разбираться в таком коде через некоторое время, спасибо вам не скажет. Кроме того, вторую часть тела цикла придется взять в условный оператор, а эта вторая часть может быть достаточно большой. Читабельность явно не повышается. Зато программа «структурная», можно «взять с полки пирожок». :-)
s:=0;
x := 1;
while x <> 999 do begin
  Readln(x);
  if x <> 999 then
    s := s + x;
end;
Заметим, что число 999 появляется в программе дважды: в заголовке цикла и в условии в теле цикла, что само по себе уже нехорошо.

Можно вынести оператор Readln за цикл, продублировав его в теле цикла:
s := 0;
Readln(x);
while x <> 999 do begin
  s := s + x;
  Readln(x);
end;
На взгляд автора, при этом два оператора ввода, выполняющие одну и ту же функцию, «размывают» логику программы и не добавляют ей «прозрачности». Кроме того, вместо Readln в других ситуациях может стоять целая группа операторов, и тут уже дублирование будет выглядеть совсем некрасиво.

Кроме того, можно ввести логическую переменную (флаг), которой присваивается истинное значение при получении числа 999:
stop := False;
while not stop do begin
  Readln(x);
  if x = 999 then
    stop := True
  else
    s := s + x;
end;
Но тут нужно вспомнить о «бритве Оккама» — не плоди лишних сущностей. И ещё — любое усложнение системы, как правило, снижает её надежность.

Еще один вариант — перейти на цикл с постусловием:
s := 0;
repeat
  Readln(x);
  if x <> 999 then
    s := s + x;
until x = 999;
Во-первых, как и в одном из предыдущих вариантов, здесь два раза всплывает число 999. Во-вторых, вторую часть тела цикла снова нужно помещать в условный оператор. В-третьих, читать программы с циклами repeat — это сущее наказание: встретив слово repeat, судорожно пытаемся найти соответствующий until с условием, без этого всё вообще непонятно. Потом опять нужно смотреть наверх: что же там в теле цикла...

Можно, конечно, и так :-):
s := 0;
try
  while True do begin
    Readln(x);
    if x = 999 then raise Exception.Create('');
    s := s + x;
  end;
except end;
Но по сути это то же самое, что и break. Использовать здесь исключения — всё равно, что гвозди микроскопом забивать.

Рассмотрим еще один пример.

Пример 2. Найти в массиве A[1..N] элемент, равный X, или сообщить, что такого элемента нет.

Решение с помощью break:
nX := 0;
for i:=1 to N do
  if A[i] = X then begin
    nX := i;
    break;
  end;
if nX = 0 then
     writeln('Не нашли!')
else writeln('nX = ', nX);
Как и для первого примера, программа с break почти дословно повторяет словесное описание идеи решения: «просматриваем все элементы массива с первого до последнего; как только нашли нужный элемент, запоминаем его номер и выходим из цикла».

Вот альтернатива без break:
nX := 1;
while (nX <= N) and (A[nX] <> X) do
  Inc(nX);
if nX > N then
     writeln('Не нашли!')
else writeln('nX = ', nX);
Теперь представим себе, что будет, если в трансляторе включена проверка выхода за границы массива, логические выражения вычисляются полностью и элемента, равного X, в массиве нет: программа вылетит в результате обращения за пределы массива.

Вот еще вариант, с логической переменной:
nX := 1;
found := False;
repeat
  if A[nX] = X then
       found:= True
  else Inc(nX);
until found or (nX > N);
if not found then
     writeln('Не нашли!')
else writeln('nX = ', nX);
Какая программа понятнее, каждый решает сам. :-)

Итак, подытожим.
  1. Оператор break есть практически во всех современных языках программирования. «Значит, это кому-нибудь нужно!»
  2. Это инструмент, который нужно использовать в соответствии с его назначением.
  3. Само по себе наличие или отсутствие оператора break ничего не говорит о том, грамотно ли написана программа; задача состоит в том, чтобы сделать ее наиболее понятной и «прозрачной».
  4. Использование оператора break относится к так называемым «структурным» переходам [3], то есть к переходам вперёд в пределах того же модуля, что не нарушает принципы структурного программирования.

Разобравшись с break, можно перейти к его непосредственному «родственнику» — оператору continue, который передает управление сразу в конец цикла, переходя к следующему шагу, если требуется.

Пример 3. В цикле обрабатываются все элементы массива A[1:N]. Для каждого из них сначала выполняются операторы S1, S2, ..., SN, в результате вычисляется некоторое значение x. Если получено значение x = 1, нужно выполнить еще операторы T1, T2, ..., TM, а в противном случае перейти к следующему элементу.

«Классическое» решение выглядит так:
for i:=1 to N do begin
  S1;
  S2;
  ...
  x := SN;
  if x = 1 then begin
    T1;
    T2;
    ...
    TM;
  end
end;
Вроде бы всё хорошо. Но мы потеряли «локальность»: при достаточно длинном теле условного оператора нужно еще «сканировать» цикл до конца, проверяя, не выполняются ли какие-то действия в том случае, когда x <> 1. А эту проблему может элегантно решить continue:
for i:=1 to N do begin
  S1;
  S2;
  ...
  x := SN;
  if x <> 1 then continue;
  T1;
  T2;
  ...
  TM
end;
Здесь уже точно ясно, что при x <> 1 никаких дополнительных операций не происходит. По мнению автора, такой вариант более «прозрачен» и, по крайней мере, не хуже предыдущего.

Остается еще один «смежный» вопрос: можно ли писать подпрограммы с несколькими выходами? Давайте посмотрим пример рекурсивной процедуры.

Пример 4. Разработать процедуру, которая выводит на экран решение задачи «Ханойская башня» [4].

Рекурсивное решение этой задачи хорошо известно, одна из реализаций выглядит так:
procedure Hanoi(n, k, m: integer);
var p: integer;
begin
  if n = 0 then exit;
  p := 6 - k - m;
  Hanoi(n-1, k, p);
  writeln(k, ' -> ', m);
  Hanoi(n-1, p, m)
end;
Здесь n — количество дисков, которые нужно перенести; k — номер начального стержня и m — номер конечного стержня.

И все было бы хорошо, но тут нарушен ещё один принцип, который стал «священной коровой» ортодоксального структурного программирования: процедура имеет (увы :-) два выхода, один естественный, и второй — по признаку окончания рекурсии.

Можно ли было обойтись без этого? Да, можно, «упаковав» все тело процедуры внутрь условного оператора:
procedure Hanoi(n, k, m: integer);
var p: integer;
begin
  if n > 0 then begin
    p := 6 - k - m;
    Hanoi(n-1, k, p);
    writeln(k, ' -> ', m);
    Hanoi(n-1, p, m)
  end
end;
Но тут мы опять теряем локальность — при достаточно длинном тексте процедуры нужно еще посмотреть, не выполняются ли какие-то действия после условного оператора. Да и не совсем понятно, зачем добавлять лишний уровень вложенности. «Не плоди лишних сущностей». По мнению автора, первое приведенное решение более понятное и более красивое.

Пример 5. Разработать функцию, которая определяет, если ли в квадратной матрице элемент, равный заданному значению.

Будем предполагать, что введен тип данных
type Matrix = array[1..N,1..N] of integer;
Тогда функцию можно написать так:
function Find(const A: Matrix; X: integer): boolean;
var i, j: integer;
begin
  Result := True;
  for i:=1 to N do
    for j:=1 to N do
      if A[i,j] = X then exit;
  Result := False
end;
Здесь оператор exit фактически выполняет роль break для вложенного цикла. С формальной точки зрения у функции два выхода. В общем, «я своим ученикам никогда такое не зачту» — уже слышу я от учителей информатики.

А давайте подумаем, какие альтернативы? Можно вот так:
function Find(const A: Matrix; X: integer): Boolean;
var i, j: integer;
label finish;
begin
  Result := True;
  for i:=1 to N do
    for j:=1 to N do
      if A[i,j] = X then goto finish;
  Result := False;
finish:
end;
Но тут вообще «криминал» — метка и goto! Хотя по сути ничего не изменилось, тот же выход из вложенного цикла.

Конечно, здесь можно использовать исключение:
function Find(const A: Matrix; X: integer): Boolean;
var i, j: integer;
begin
  Result := False;
  try
    for i:=1 to N do
      for j:=1 to N do
        if A[i,j] = X then
          raise Exception.Create('');
  except
    Result := True
  end
end;
Но ведь это далеко не «исключительная ситуация», поэтому по смыслу исключения здесь всё-таки не особо уместны. Кроме того, нужно учитывать, что при обработке исключений выполняется большое число машинных команд, что снижает эффективность программы.

Любителей «чистого» структурного программирования наверняка устроит такой вариант решения:
function Find(A: Matrix; X: integer): Boolean;
var i, j: integer;
begin
  Result := False;
  for i:=1 to N do
    for j:=1 to N do
      if A[i,j] = X then Result := True
end;
Но, к сожалению, по эффективности он не может составить конкуренцию предыдущим, так как в любом случае рассматриваются все N2 элементов массива, даже если элемент A[1,1] равен X.

Выводы

Эта статья, прежде всего, о том, что любые идеи и принципы нужно воспринимать в контексте конечной цели. Одна из основных целей концепции структурного программирования — повысить читаемость программ и за счёт этого облегчить их отладку, тестирование и сопровождение. Поэтому применение операторов break, continue и exit нельзя считать отступлением от структурного программирования, если это не ухудшает читаемость программы и не приводит к запутыванию логики алгоритма.

В то же время попытки избавиться от этих операторов (для того, чтобы формально соблюсти «классические правила») могут привести к ухудшению читаемости программы.

Литература
  1. Dijkstra E.W., Go To Statement Considered Harmful // Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148. (PDF)
  2. Knuth D.E. Structured Programming with GO TO Statements // ASM Computing Surveys. 1974. 6(4). P.261-301. (HTML, PDF)
  3. Непейвода H.H., Скопин И.Н. Основания программирования. — Москва-Ижевск: Институт компьютерных исследований, 2003. (PDF)
  4. Гарднер М., Математические головоломки и развлечения. — М.: Мир, 1999.

Ярлыки: , , , , , , ,

Автор: КП @ 19:03   Комментарии: 23

пятница, 13 апреля 2012 г.

Есть ли operator присваивания в Паскале?

Иногда появляется повод задуматься над, казалось бы, привычными и понятными вещами. А когда задумаешься, выясняется, что все не очень просто, потому что остальные тоже считают, что это привычно и понятно. И тогда приходится разбираться.

В ходе подготовки учебника к экспертизе у редактора возникли сомнения по поводу моей фразы: «Оператор «:=» — это оператор присваивания». По её мнению, оператор присваивания — это всё выражение вида «переменная := выражение;», а символы «:=» — это знак присваивания.

Как оказалось, этот терминологический вопрос совсем не прост. Изучение источников как на русском, так и на английском языках, даёт противоречивые результаты.

Поскольку речь идет о Паскале, обратимся, прежде всего, к отчёту «The Programming Language Pascal», который написал Никлаус Вирт, создатель этого языка. Он пишет:

«The most fundamental statement is the assignment statement. It specifies that a newly computed value be assigned to a variable (or a component of a variable).»

«Assignment statement» — это оператор присваивания, здесь слово «statement» действительно переводится на русский как оператор в значении «инструкция», «команда».

Но вопрос в другом — как назвать символ «:=»? Вирт в своих работах не дает ему никакого названия, такой же подход принят и в стандарте ISO7185.

Часто утверждается, в Паскале вообще нет оператора присваивания, такого как в Си и Си++, потому что присваивание — «это утверждение, а не выражение». Однако существует и другое мнение. Например, в книге М. Канту «Essential Pascal» видим термин «colon-equal operator». А Н. Дейл прямо использует термин «assignment operator» (см. «Programming in Pascal», глава 2).

Итак, мы добрались до сути: «:=» — это оператор или не оператор? Чтобы ответить на этот вопрос, нужно понять, какое значение слова «оператор» имеется в виду. В английском языке используется два совершенно разных слова, которые переводятся на русский одним и тем же словом «оператор» — это «statement» и «operator». С оператором-statement вроде бы всё понятно. Оператор-operator — это другой термин, который связан с математическим понятие оператора — правила преобразования одного объекта в другой.

Выражение «assignment operator» широко используется в таких языках, как Си и Си++, где оператор присваивания обозначается знаком «=». Его суть в том, что оператор присваивания создает новый объект на основе двух существующих объектов, записывая новое значение в переменную.

Таким образом, для того, чтобы разобраться, является ли символ «:=» оператором в этом смысле, нужно выяснить, могут ли при присваивании выполняться какие-то преобразования.

Считается, что в «классическом» Паскале оператора присваивания (в смысле operator) нет. Но это не совсем верно. Вот пример программы, которая работает во всех современных версиях Паскаля: 
var a: integer;
    b: longint;
begin
  a := 5;
  b := a;
  b := 25;
  a := b;
end.
Очевидно, что здесь перед записью значения в переменную некоторые преобразования данных (приведение к другому типу) автоматически выполняются.

Кроме того, в современной версии Free Pascal символ «:=» вполне законно называется оператором присваивания, потому что его можно перегружать, как и в Си++. В программе, приведенной ниже, показан пример такой перегрузки. 
type
  complex = record re,im: real; end;
var z: complex;
  operator :=(r: double) z: complex;
  begin
    z.re:=r;
    z.im:=0;
  end;
begin
  z:=3;
end.
Выводы: Таким образом, в современном Паскале «X:=Y;»  — это оператор присваивания (statement), а «:=» — это тоже оператор присваивания (operator).

Автор благодарит О.А. Полежаеву за интересное обсуждение, в результате которого появилась эта заметка.

Ярлыки: , , ,

Автор: КП @ 19:36   Комментарии: 3

воскресенье, 9 октября 2011 г.

По следам новой теории ввода/вывода

Недавно в журнале «Информатика» появилась статья А.А. Дуванова и Н.Д. Шумилиной «Устройства ввода и вывода. Теория относительности» [1]. В ней авторы предлагают свое толкование привычных, казалось бы, терминов «устройство ввода» и «устройство вывода». По их версии, устройства ввода — это любые устройства, через которые компьютер получает данные, в том числе дисководы, модемы, флэш-диски и пр. Аналогично устройства вывода — это любые устройства, через которое данные выводятся из компьютера, причем получателем может быть как человек, так и другое цифровое устройство (те же дисковод и флэш-диск).

Как известно, об определениях не спорят. Напротив, спор в научном мире начинается с фиксации определений. Иногда он на этом и заканчивается, поскольку спор умных людей нередко вызван именно тем, что его участники называют одним и тем же термином совершенно разные вещи. Поэтому некорректно говорить о том, верные определения даны в [1] или неверные. Но можно сравнить их с альтернативными и проследить, к чему они в конечном счёте приводят: какую картину мира удается построить на основе этих определений.

Начнём с официальных источников. Согласно ГОСТ 25868-91 [2], «устройство ввода (вычислительной машины) — периферийное устройство, обеспечивающее преобразование информации в форму, необходимую для ее автоматического ввода в ЭВМ», и «устройство вывода (вычислительной машины) — периферийное устройство, обеспечивающее вывод данных из ЭВМ». Приведенное в ГОСТ определение устройства ввода явно подчеркивает его характерную черту — первичное преобразование информации из «некомпьютерного» вида в «компьютерный». Таким образом, определение из [1] противоречит определению в ГОСТ, что само по себе уже нехорошо, потому что способно только вызвать путаницу. Стандарт он тем и хорош, что создает общепринятый фундамент для дальнейших «строительных» работ.

Определение устройства вывода в ГОСТ значительно слабее, но по аналогии, сохраняя общую идеологию, хочется написать так: «устройство вывода (вычислительной машины) — периферийное устройство, обеспечивающее преобразование данных в форму, доступную для ее восприятия человеком».

В результате можно сделать следующий вывод: определения в [1] не позволяют как-то выделить (классифицировать) устройства, которые выполняют преобразование данных из «некомпьютерного» формата в «компьютерный» и обратно, то есть находятся на границе между «некомпьютерным» и «компьютерным» мирами. В сравнении с определениями ГОСТ, это шаг назад, поскольку среди устройств ввода/вывода (по терминологии [1]) затерялся целый подкласс устройств, обладающих принципиальными отличиями от всех остальных.

Представим на минуту, что куда-то исчезли все устройства, которые по ГОСТ назывались устройствами ввода. Вместе с ними исчезли и устройства вывода — мониторы, принтеры, наушники и т.д. Остались только флэшки, дисководы, роутеры, коммутаторы, модемы и пр. Что получим? «Компьютерный» мир оказывается замкнут, человек теряет все средства общения с ним, поскольку воспринимать цифровые сигналы непосредственно мы пока не научились. Этот факт говорит о том, что исходные определения упустили что-то важное, и устройства ввода (вывода) (по терминологии [1]) бывают разные.

Теперь проанализируем выводы, к которым приходят авторы [1] на основе введенных ими определений.

«Итак, компьютер — это процессор и внутренняя память». «Все другие устройства обеспечивают или ввод информации в память компьютера, или вывод из нее. Соответственно, все другие устройства, подключаемые к процессору и памяти, являются устройствами ввода и (или) вывода».

Вряд ли кто-то будет спорить с тем, что компьютер — это система, обладающая системным свойством — обрабатывать данные по введенной в него программе. Если мы говорим, что «компьютер — это процессор и внутренняя память», возникает вопрос о том, обладает ли эта пара тем же самым системным свойством? На наш взгляд, нет, потому что ввести в него программу не удастся, так же как и получить какие-то результаты.

«Флешка и принтер между собой принципиально не отличаются».

По мнению автора данной заметки, это неверное утверждение. Принтер выполняет преобразование информации из цифровой формы в «бумажную». Флэш-диск — это устройство «компьютерного» мира, которое никак не обменивается данными с реальным миром. Смешение двух понятий похоже на ситуацию в индейском племени хипо, в языке которого зеленый и голубой цвета обозначались одним и тем же словом, и сначала предполагалось, что индейцы не различают эти цвета вообще.
«На схеме зеленые стрелки показывают движение информации, а красные — управляющие воздействия процессора:»

При анализе этой схемы возникает несколько серьезных вопросов. Возьмем, для примера, флэш-диск, который часто используется для иллюстрации в [1]. Согласно предлагаемой терминологии, его можно считать устройством ввода и вывода, то есть внешним устройством (левый блок на схеме). В таком диске есть контроллер и память. Если с памятью все понятно, то на месте контроллера на схеме написано «устройство ввода/вывода». Кроме того, судя по схеме, процессор только управляет прямым доступом к памяти и не может обмениваться данными с внутренней памятью и напрямую с внешним устройством (нет зелёных стрелок), что, мягко говоря, не соответствует истине.

При чтении статьи [1] в воздухе постоянно витает вопрос «зачем»? Новые определения понятий «устройство ввода» и «устройство вывода» не имеют, на наш взгляд, никаких преимуществ перед классическими, закрепленными в ГОСТ. Картина немного проясняется в последних разделах статьи [1]: «Теория относительности ввода и вывода» и «Формальные определения», где утверждается, что
  • понятия «устройство ввода» и «устройства вывода» применимы не только к компьютерам, но и к любому процессу передачи информации вообще:

    «Так что же есть сканер? Для компьютера это устройство ввода. А для человека? А для человека сканер — устройство вывода. Мы ведь отдаем ему листок, “выводя” из папки, в которой листок хранили».

  • эти понятия зависят от направления передачи информации; два компьютера, обменивающиеся данными, попеременно являются друг для друга устройствами ввода и вывода.
Получается некая кибернетическая картина мира, в которой человеку отводится примерно такая же роль, как и любому компьютерному устройству. С точки зрения [1], компьютер может рассматриваться как устройства ввода и вывода для «флэшки», а человек — как устройство ввода для сканера. «Ну и что?» — скажет читатель. Да просто предложен еще один философско-кибернетический взгляд на мир. Более важный вопрос: «Что из него следует?» Да, в общем-то, и ничего и не следует. «Тогда зачем?» Это вопрос пока без ответа. Подведем итоги. По мнению автора этой заметки, понятия «устройства ввода» и «устройства вывода» должны быть на своём месте, обозначая устройства для преобразования данных между компьютерным и реальным мирами. Попытки расширить эти понятия пока ничего путного не дали. Литература
  1. А.А. Дуванов, Н.Д. Шумилина, Устройства ввода и вывода. Теория относительности // Информатика, № 14, 2011, с. 24-29.
  2. ГОСТ 25868-91. Оборудование периферийное систем обработки информации. Термины и определения.

Ярлыки: , ,

Автор: КП @ 15:39   Комментарии: 1

пятница, 8 апреля 2011 г.

Кумир и школьная информатика

Как все уже знают, в ближайшие два года будет происходить постепенный переход на компьютеризированный вариант сдачи ЕГЭ по информатике. Компьютерная тестирующая система (КТС ЕГЭ) пока ориентирована на использование кроссплатформенных систем программирования Кумир (Комплект Учебных МИРов, школьный алгоритмический язык) и FreePascal.

Сильный эффект произвело известие об административном внедрении системы Кумир, которая разработана в НИИСИ РАН по заказу Российской Академии Наук и распространяется свободно на условиях лицензии GNU GPL.

Конечно, все «старики», знакомые с учебниками информатики А.Г. Кушниренко 1990 года, знали о Кумире, кое-где даже использовали его DOS-версию, но широкого распространения (по крайней мере, в Питере) она никогда не имела по разным причинам, в первую очередь, из-за убогого интерфейса.

Первый сигнал о втором пришествии Кумира появился в апреле 2010 года после семинаров, которые проводили П.А. Якушкин, В.Р. Лещинер, А.Г. Кушниренко и М.А. Ройтберг на Дне учителя информатики 2.04.2010 в рамках Девятого московского педагогического марафона. Чуть позже в газете «Информатика» появилась статья В.Р. Лещинера и П.А. Якушкина, посвященная компьютерному варианту ЕГЭ.

Новость произвела эффект разорвавшейся бомбы среди учителей информатики. На педагогических сайтах развернулись бурные дискуссии (см. тему «Быть Кумиру?» и обсуждение на сайте pedsovet.org).
Большинство участников этих словесных баталий Кумир не приняли, было сказано много ругательных слов.

Автору этих строк Кумир тоже никогда не нравился, хотя нравились идеи С. Пейперта, Г.А. Звенигородского и учебник информатики А.Г. Кушниренко 1990 года. Такой вот парадокс. В результате была написана среда «Исполнители», которая успешно используется с 1992 года по сей день во многих школах. Кстати, в начале 90-х журнал «Информатика и образование» отклонил статью, посвященную «Исполнителям», только из-за того, что «среда Кумир уже получила широкое распространение и альтернативы не актуальны».

Но вернемся к Кумиру. По словам самих авторов, Кумир предназначен для начального обучения алгоритмизации и программированию (6-7 классы). Пока он занимал эту нишу, все было относительно хорошо и спокойно: практически никто из учителей не трогал Кумир, но и Кумир никого не трогал.

Но теперь встал вопрос о том, что Кумир становится одним из (двух) языков, разрешенных на компьютерном ЕГЭ по информатике, то есть «поднимается» на уровень 10-11 классов. Это заставило задуматься. Мера явно вынужденная: для компьютерного ЕГЭ требуется
  • кроссплатформенность
  • бесплатность
  • простота установки
  • относительная известность и популярность.
Таких сред не очень много, поэтому «архитекторов» нововведений можно понять. В начале этого учебного года стало ясно, что возвращение Кумира — это серьезно, и его проталкивают «сверху». Московский институт открытого образования (МИОО) проводит дистанционный курс Подготовка выпускников к ЕГЭ по информатике и ИКТ в компьютеризированной форме, где Кумиру отводится важнейшая роль. Для просмотра материалов курса требуется бесплатная регистрация, но выложенные материалы того стоят, рекомендую посмотреть. 29 ноября 2010 года тот же МИОО проводит апробацию компьютеризированной системы проведения ЕГЭ по информатике и ИКТ (КТС ЕГЭ). В газете «Информатика» (№№ 24/2010 и 2/2011) публикуются статьи А.Г. Леонова из серии «Освой КуМир за 6 часов». До этого, в 2009 году, напечатан цикл материалов А.Г. Кушниренко и А.Г. Леонова «Методика преподавания основ алгоритмизации на базе системы КуМир». На очередном Дне учителя информатики (01.04.2011) продвижение КуМира продолжается (семинар и круглый стол). Все это говорит о том, что с Кумиром придется считаться. Как и любое явление, он имеет достоинства и недостатки. О них много говорили на упомянутом курсе МИОО, даже была сделана Wiki-страничка «Плюсы и минусы Кумира». Там представлен широкий спектр мнений, поэтому здесь не будем повторяться. Автор в текущем учебном году решил попробовать перейти в 7-8 классах на Кумир. Сразу обнаружились достаточно серьезные проблемы, которые позволяли сделать вывод о непригодности среды в ее текущем состоянии для этих целей. Самые важные среди них:
  • чудовищная медлительность Кумира, работающего в сотни раз медленнее, чем любая из Паскаль-сред
  • отсутствие «нормальной» (не черепашьей) графики
  • совершенно неразвитые средства работы со строками (например, не было функции поиска)
  • устарелая и полностью кривая работа с файлами (например, перед тем, как открыть файл на запись, нужно каждый раз проверять, существует ли он, и если нет, то создавать пустой файл отдельной командой)
К счастью, вскоре удалось выйти на прямую связь с руководителем группы разработчиков Кумира М.А. Ройтбергом. В результате сотрудничества большинство проблем удалось снять, и появилась предварительная версия, в которой можно нормально работать, то есть делать то, что раньше мы делали на Паскале и Си. Медлительность, правда, осталась, но А.Г. Кушниренко обещал, что версия 2.0 будет существенно быстрее (ему, наверное, это обещали программисты). Материалы презентаций к урокам по Кумиру можно взять у меня на сайте (там около 400 слайдов). Самую последнюю версию Кумира можно скачать на сайте разработчиков. Необходимо отметить, что ряд проблем все же остаются в текущей версии (1.8.0):
  • нельзя менять значения аргументов внутри вспомогательных алгоритмов (например, в реализации алгоритма Евклида как функции приходится заводить две лишние переменные);
  • нельзя вызывать функцию как процедуру, игнорируя ее результат (например, когда результат функции — код возврата и в данном случае он меня не интересует);
  • неудобная и неполная справочная система;
  • нет форматного вывода на консоль и в файл, как в Паскале (типа вывод x:4), это нужно, например, чтобы вывести на экран матрицу ровными столбиками.
По словам разработчиков, по крайней мере, некоторые из этих недостатков будут устранены в версии 2.0. Общие выводы по результатам года:
  • русские команды школьники воспринимают намного легче английских
  • для изучения основ программирования и алгоритмизации Кумир ничем не хуже Паскаля, в новой версии можно делать практически все, что нужно; если удастся серьезно ускорить вычисления, будет совсем хорошо
  • Кумир очень неплохо идет даже в 9-11 классах на базовом уровне и может быть очень удачным выбором для тех, кто в будущем не будет профессионально программировать.
Напоследок приведу список сетевых ресурсов по Кумиру:

Ярлыки: , , , ,

Автор: КП @ 20:43   Комментарии: 22