Цифровой журнал «Компьютерра» 2011 № 31 (79) - [19]

Кафедра Ваннаха: Хеширование знаний Ваннах Михаил

Опубликовано 25 июля 2011 года

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

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

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

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

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

А теперь вспомним — как происходит проверка при ЕГЭ?

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

И какая же это процедура?

Правильно — хеширование, hashing. Преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. В самом простейшем случае это вычисление контрольных сумм, исправляющее ошибки аппаратуры, сбои передачи данных по каналам связи с помехами (теория информация и началась с рассмотрения этой задачи — это прекрасно и доступно описано в вышеупомянутой книге Ягломов). Интернет, практическая реализация протокола TCP/IP, был бы невозможен без циклических кодов.

Дальше — хеширование криптографическое, то, без чего невозможна была бы и компьютерная связь, и компьютерные транзакции. Даже те, кто не является агентом или резидентом, регулярно прибегает к крипто-хешам, говоря по мобильнику или расплачиваясь карточкой. Эта процедура — фундамент ИТ-экономики, о чём годами в бумажной Компьютерре рассказывал Максим Отставнов.

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

И, видимо, точно так же можно, по аналогии, хешировать совокупность знаний так, чтобы правильные ответы мог дать только человек, усвоивший курс, чтобы статистически невероятно было их угадать. Это-то легко — этим свойством будет обладать достаточно длинный список, а вот второе ограничение важнее. Хорошо бы добиться того, чтобы человек, учебного курса не усвоивший, никоим образом не был в состоянии простым зазубриванием добиться высокого результата.

Сложно?

Неоднозначно?

Но криптографы аналогичные задачи решают успешно.

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

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