          ИТОГИ II НЕЗАВИСИМОЙ ОЛИМПИАДЫ ПО ПРОГРАММИРОВАНИЮ

     Олимпиада состоялась 19 октября в торгово-экономическом институте.
В олимпиаде приняло участие 36 человек. Руководствуясь "Временным  поло-
жением о Независимой  олимпиаде ОСП", жюри  Олимпиады в составе  Николая
Безрукова (председатель), Бориса Литвинова и Вадима Ткаченко на заключи-
тельном  заседании  приняло  решение  о следующем распределении призовых
мест среди участников (за счет спонсорского взноса фирмы Доверие стипен-
дии повышены по сравнению с ранее публиковавшимся объявлением):

                               I место
   (стипендия 200 руб. в месяц и компилятор Turbo C++ 2.0 фирмы Борланд):
            Юрий Зайцев, студент II курса КГУ (ф-т кибернетики).

                               II место
  (стипендия 150 руб. в месяц и пакет Turbo Debugger & Tools фирмы Борланд):
            Станислав Малышев, студент I курса КГУ (ф-т кибернетики);
            Виктор Тарасюк, студент III курса КГУ (ф-т кибернетики).

                               III место
                     (стипендия 100 руб. в месяц):
            Андрей Бабак, студент I курса механико-математический ф-та КГУ;
            Олег Пекар, студент I курса КГУ (ф-т кибернетики);
            Артем Шелест, студент III курса КПИ (ф-т ПМА).

    В целом, можно констатировать, что демонстрируемый участниками  уро-
вень понимания  теории и  владения техникой  программирования возрос  по
сравнению с предыдущей олимпиадой. Многие участники пытались  исполь-
зовать рекурсивные алгоритмы, двое - описывать с помощью БНФ  простейшие
формальные языки  (СТРОШ-описание шапки  таблицы). В  целом, большинство
участников продемострировало пределенный  уровень понимания теории  про-
граммирования. В этом плане они приятно констрастируют с некоторыми  из-
вестными нам по семинару "героями-хакерами", которые предпочитают совер-
шенствоваться в инсталляции систем без документации, а не изучать  скуч-
ную теорию ("сера теория мой  друг, но древо жизни вечно  зеленеет", как
сказал классик). Кстати Юрий Зайцев, занявший первое место на этой олим-
пиады был единственным школьником, попавшем в число призеров  предыдущей
олимпиады (тогда он занял III место).
     Если говорить о критериях оценки решения первой задачи, то жюри ру-
ководствовалось следующими:
     - учет возможности  переполнения счетчика (счетчик  должен занимать
два слова, а не одно);
     - приведение как минимум двух алгоритмов решения (с массивом на 256
символов, в соответствующих элементах которого указано количество едини-
чных битов для  данной битовой компбинации  и методом сдвига).  В случае
метода сдвига решение признавалось эквивалентным по качеству  табличному
методу в случае наличия (или указание на возможность) оптимизации  внут-
реннего цикла путем его развертки в линию;
     - использование  в качестве  тестовой программы  программы на языке
высокого уровня;
     - уровень овладения ассемблером (макрокоманды структурного програм-
мирования для управляющих структур, правильное использование директив  и
прочее).
     Вторая задача фактически представляла собой в несколько  завуалиро-
ванной форме проект компилятора  с некоторого формального языка  - языка
СТРОШ-описаний  (оригинальная  статья  на  которой базируется эта задача
приведена в файле Shapka.a39 данного каталога). Поэтому здесь  наивысшие
оценки получили решения в которых использовался (точнее наблюдались  не-
которые проблески) синтаксически-ориентированного  подхода к решению,  в
частности,  использование  рекурсии  для  неявного представления дерева,
введение  понятия  лексемы  при  вводе  СТРОШ-описания, модуляризация по
принцику "лексический анализатор - программа разбора - генератор кода" и
пр. В частности, обе работы, в которых была приведена форма Бэкуса-Наура
для СТРОШ, попали в число победителей. Это связано с тем, что БНФ  можно
рассматривать как исполняемую программу для некоторого компилятора  (на-
пример, YACC), что условиями задачи не запрещалось и тем самым  снимался
вопрос правильности логики программы на языке высокого уровня (если  та-
ковая была приведена).
     С точки зрения использования языка высокого уровня жюри приветство-
валось объектно ориентированное программирование (С++ и Turbo Pascal 5.5
или 6.0).  К сожалению  уровень документированности  представленных про-
грамм оставлял желать лучшего. Только немногие догадались выделить  клю-
чевые фрагменты, а подпрограммы, непринципиальные с точки зрения  основ-
ного алгоритма, представить фрагментарно. Практически никто не  обсуждал
возможность использования альтернативных принятым структур данных.
     Если  программы,  представленные  победителями выглядели достаточно
обнадеживающе и их авторы  со временем безусловно смогут  (если захотят)
стать квалифицированными системными програмистами, то результаты  ответа
на первый  вопрос ("Перечислить  названия глав  первого тома  монографии
Д.Кнута "Искусство программирования для ЭВМ" и указать возраст ее автора
в момент выхода в  свет английского издания") выглядят  обескураживающе.
Из двух участников сделавших попытку  ответить на этот вопрос лишь  один
назвал правильно две главы.  И это для книги  являющейся фундаментальной
работой по системному программированию. В общем мне кажется, что победи-
тели должны компенсировать этот пробел в своих знаниях и, возможно, при-
нять участие  в проводимых  на январском  заседании семинара "Кнутовских
чтениях".
   Конечно свет клином на Д.Кнуте не сошелся и можно изучать все эти во-
просы по книгам других авторов. Однако уровень понимания проблематики  в
монографии Кнута выше чем у большинства авторов монографий  аналогичного
содержания. Это прежде всего связано с тем, что личный вклад в  програм-
мирование Д.Кнута и остальных "писателей" на мой взгляд просто несравни-
мы. Например, в неплохой книге Н.Вирта "Алгоритмы + программы =  данные"
приводимые алгоритмы искажены Паскалем и чересчур ревностным применением
концепции  структурного  программирования.  Поэтому  ее не рекомендуется
изучать изолированно от монографии Кнута. Тем более, что в ряде мест это
просто краткий конспект  оригинального материала Кнута.  Конечно, многих
отпугивает ассемблер MIX.  Программы на том  же Паскале намного  легче и
читать и понимать. Так ведь несложно написать MIX-интерпретатор и  смот-
реть поведение соответствующих программ "живьем". К сожалению, при  реа-
лизации на Паскале многие весьма тонкие ньансы остаются "за кадром"  или
даже специально затушевываются из "политических соображений" (в частнос-
ти, книга Вирта не свободна от коньюнктурных веяний того времени: автору
явно хотелось быть "правоверным католиком". А "римский папа" (по  уровню
фанатизма скорее аятолла) - Эдгар Дейкстра в те времена сильно увлекался
доказательством программ).
   После этого "лирического отступления" вернемся к проблемам проведения
следующей олимпиады. Она намечена на октябрь 1992 г. Поскольку  основная
часть победителей это студенты университета, олимпиаду имеет смысл  про-
водить в КГУ. Кроме того, наверное было бы неплохо дополнительно к  объ-
явлению в бюллетене и газете Вечерний Киев повесить объявления непосред-
ственно в вузах.

14.11.91

   Председатель жюри олимпиады
   доцент, канд. физ.-мат. наук                             Безруков Н.Н.
