Подготовка к олимпиадам по информатике

[к списку интервью]

Подготовка к олимпиадам по информатике дело довольно ответственное и порой без посторонней  квалифицированной помощи не обойтись. Как готовить школьников  к олимпиадам? На изучение какого языка программирования сделать упор? Эти и другие вопросы затронуты в интервью с  Михаилом Медведевым, доцентом кафедры математической информатики факультета кибернетики Киевского национального университета имени Тараса Шевченко.

Расскажите коротко о себе.

Я, Медведев Михаил Геннадиевич,  окончил среднюю образовательную школу в городе Киеве. Мне очень нравилась математика и программирование – дома был компьютер «Специалист», собранный отцом по страницам журнала «Моделист-конструктор». В школе занимал призовые места на городских олимпиадах по математике. С 1990 по 1995 гг. учился на факультете кибернетики Киевского национального университета имени Тараса Шевченко. Потом поступил в аспирантуру (заочно) и в 1999 году защитил диссертацию, став кандидатом физико-математических наук. В данный момент являюсь доцентом кафедры математической информатики факультета кибернетики. Занимаюсь преподавательской и научной деятельностью. Имею особенный интерес к олимпиадам по программированию.

В каких учебных учреждениях вы работаете?

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

Где вы познакомились с компьютером?

Первые свои программы я писал на домашнем компьютере «Специалист» с памятью 64 Кб, набивая их непосредственно в кодах. Потом появился Ассемблер – для меня в то время это был верх совершенства, хотя всю таблицу из 256 кодов процессора КР580ИК80А я знал наизусть :-). В школе два года преподавания информатики были посвящены алгоритмическому языку программирования и Бейсику. В университете на первом курсе (1990 год) я познакомился с Паскалем и писал на Искрах.

Как вы считаете, необходимо ли преподавать программирование в школе или может лучше сделать упор на офисные программы?

Если бы я знал только те программы и компьютеры, которые были в 90-х годах (когда я учился в университете), и не изучал бы ничего нового, то наверное  сегодня не смог бы написать ни одной программы. Если математика – наука, база которой не меняется десятилетиями (например, формула Ньютона  - Лейбница была, есть и будет), то таких языков как Алгол, Фокал, PL/1 сегодня уже, наверное, не услышишь. Компьютерные науки меняются очень быстро, приходит новое и уходит старое. И самое главное, что наверное и отличает университет от обычных курсов, это то, что тебя там учат учиться и дают фундаментальные знания. Я считаю, что такие вещи как среда Windows, работа с архиваторами, офисные программы и так далее студент (или школьник) должен сам выучить, когда получает доступ к компьютеру (конечно еще лучше, когда этот компьютер дома). А в школе школьника должны учить алгоритмическому мышлению. Может именно поэтому олимпиады по информатике как правило включают в себя алгоритмические задачи, которые следует решить выбрав один из языков программирования. Хорошо бы вообще разработать школьную программу, где информатику начали бы изучать с 7 класса, причем информатика шла бы как предмет, который расширяет математику. 

Какой язык программирования, на ваш взгляд,  предпочтительней изучать в школе?

Однозначно считаю, что следует переходить на язык Си. Сразу. И вот почему. Конечно, мы, взрослые программисты, когда-то писали и на Алголе и на Фортране. Я например, даже в свое время работал в операционной среде «Примус» и писал программы на языке PL/1. На персональных компьютерах сначала появился Бейсик как первый язык высокого уровня, потом постепенно его вытеснил Паскаль. Например, в большинстве киевских школ изучают Паскаль. А еще три года назад и в Киевском университете на факультете кибернетики на первом курсе студенты знакомились с этим замечательным языком, которому скоро исполнится 35 лет. С появлением и развитием операционной среды Windows появились такие среды как Delphi, поддерживающая Паскаль и Visual Studio, где можно писать на Си (и на Бейсике, Visual Basic). Но дело в том, что Си имеет достаточно богатую библиотеку функций, которая постоянно развивается от версии одной среды к версии другой. Я считаю, что стандартная библиотека шаблонов STL (Standart Template Library) сегодня просто убила Паскаль. Как писать сортировку? Конечно, в Паскале есть функция qsort. Возьмем задачу чуть посложнее – написать бинарный поиск или генерацию перестановок. Для этого надо на Паскале написать до десятка строк. А в библиотеке шаблонов есть просто функции binary_search или соответственно next_permutation. Сколько Вам требуется кода, чтобы реализовать сбалансированное бинарное дерево (известное как красно-черное)? В Паскале на это потребуется 4 килобайта кода и 20 минут времени. А в языке Си есть такая динамическая структура: set. Так вот, если пять лет назад в школах и университетах массово переходили с Turbo (Borland) Pascal на Free Pascal, то сегодня так же массово переходят на Си. Например, даже на студенческом чемпионате мира по программированию, проводимом ежегодно Ассоциацией компьютерных машин (ACM), со следующего, 2007 года, из языков программирования убран Паскаль. Но и язык Си будет трансформироваться дальше. Когда программистам надоели указатели, был создан язык без указателей, но с синтаксисом Си – это всем известный язык Java. Но Java является лишь интерпретатором, программисты пошли еще дальше и создали язык C# (C sharp). Сегодня, как правило, три языка (С, С#, Java) доступны на мировых студенческих первенствах и различных тренировочных сайтах. Например, в среде .NET поддерживаются языки C/C++, C# и Бейсик.

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

Я занимаюсь олимпиадным движением с 1996 года, с тех пор, как начал свою работу ассистентом на факультете кибернетики. В командных и личных первенствах университет, как правило, занимал призовые места. На полуфинальных соревнованиях чемпионата мира по программированию, которые являются самыми престижными среди студентов в области информационных технологий, команда университета, как правило, попадала в десятку. А в 2003 году вышла в финал и стала бронзовым призером чемпионата мира. Хочу также отметить, что начиная с 2003 года, я занимаюсь подготовкой команды НаУКМА (Киево-Могилянской академии). Несмотря на то, что Могилянка в основном является гуманитарным вузом, мне удалось создать команду, которая вот уже два года занимает третье почетное место в Киевском регионе (после команд Киевского университета имени Тараса Шевченко и Киевского Политехнического института), а в 2006 году в личном первенстве на двух всеукраинских олимпиадах в Харькове студенты НаУКМА заняли первое и второе место.

Пользуясь случаем, хочу от души поздравить российских студентов и их преподавателей с отличными выступлениями на ACM олимпиадах. Четыре раза чемпионами мира и соответственно обладателями кубка становились команды из России (http://icpc.baylor.edu/past/default.htm): Санкт-Петербургский государственный университет (2000, 2001), Санкт-Петербургский институт механики и оптики (2004), Саратовский государственный университет (2006). Нельзя не отметить здесь и заслуги школьных учителей –любовь к точным наукам и первые победы эти студенты наверняка получили еще на школьной скамье.

Среди учителей информатики существует мнение, что школьные олимпиады по информатике должны базироваться на школьном курсе информатики. Каково ваше мнение на этот счет?

Полностью согласен. Только надо так построить школьный курс, чтобы, начиная, например, с 7 класса, школьник изучал алгоритмический подход к решению задач, и язык программирования (я рекомендую сразу начинать изучение Си). Особенно следует уделять технике программирования – написанию эффективных процедур и функций, реализующих те или иные алгоритмы. Конечно, можно провести несколько занятий по операционным системам, офисным программ, приложениям – но я считаю, что эти темы может освоить и сам школьник. Или, по крайней мере, общие понятия можно дать по каждой их подобных тем за одно – два занятия. Конечно, следует учесть, что не все школьники станут программистами, поэтому все изложенное здесь мной скорее относится к школам с математическим или информационным уклоном. Читать ли лингвистам язык Си? Может и нет, но в любом случае при таком подходе лингвистов Вы же не будете отправлять на олимпиады по информатике.

Я согласен с вами, что такой подход оправдан в школах с математическим или информационным уклоном, но какие рекомендации вы могли дать для «обычных» школ, где информатику преподают только в старших классах по 1-2 часу в неделю? Замечательно, если компьютер есть дома у ученика, но это ведь не говорит о том, что он при его помощи изучает тот же Word или программирует. Итак, чему же все-таки можно научить за 1 час в неделю?

Трудно сразу ответить. Если бы этот вопрос прозвучал 10 – 15 лет тому назад, когда не было офисных программ, да и самого Windows – я бы сказал однозначно: алгоритмику, то есть программирование на текущем доступном языке: то ли Бейсик, то ли Паскаль, то ли просто блок-схемами. Кстати, мне в школе именно так и преподавали информатику (это было в 1989 году): начиная с алгоритма заварки чая и заканчивая методами сортировки, динамическими структурами и указателями. И у нас в школе информатика была 1 час в неделю. Сегодня область информационных технологий достаточно обширна, поэтому при изучении информатики все же следует дифференцировать направления: офисные приложения или программирование. Учитель скорее всего должен изложить ученику основные направления и задачи, которые можно решать при помощи компьютера, рассказать о его приложениях в разных сферах общественной жизни, а ученики уже сами найдут свой интерес. Если урок информатики проходит раз в неделю и предмет изучается два последние года, то просто надо дать общие представления и об операционных системах, и об офисных программах, структуре компьютера, ну и конечно же программировании. Причем последнее, если у учащихся нет дома компьютеров, лучше давать в алгоритмической форме. Можно показать ученику «внутренности» машины – например, программу debug, рассказать о внутренней памяти, сегментах – смещениях, даже познакомить с ассемблерами. Но как я уже говорил выше – главное научить ребенка учиться. Может он и не будет знать как называется в языке Си процедура генерации перестановок, но можно ему дать математические основы алгоритмов – что такое переборные алгоритмы, перестановки, подмножества, сортировка, числа Фибоначчи. Конечно же стоит рассказать что такое драйвер, как подключать сканер, принтер, модем и как с ними работать. То есть каждое занятие будет открывать ученику некоторую новую область знаний. А уж какое направление он выберет по окончании школы – решать ему самому.

Какие рекомендации вы могли бы дать учителям информатики по подготовке к олимпиадам? 

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

В мире сегодня существует множество сайтов с системами Online Judge. Зарегистрировавшись и получив пароль, Вы можете решать задачу и код решения отправлять на автоматическую проверку. Через несколько секунд Вы получаете один из ответов на ваше решение: Accepted (Задача решена верно), Time Limit (Ваше решение не прошло по времени, оно слишком долгое), Wrong Answer (Неверный ответ), Compile Error (Ошибка компиляции программы). Из сегодняшних таких страничек хочется отметить:

http://acm.timus.ru  –  Уральский университет.

http://acm.uva.es/problemset, http://acm.uva.es/contest  – университет Вальядолид (Испания).

http://ace.delos.com/usacogate - Подготовка к школьным олимпиадам в США.

http://dl.gsu.unibel.by – Беларусский сайт дистанционного образования.

http://acm.baylor.edu – Официальный сайт ACM соревнований.

http://www.topcoder.com – еженедельные соревнования, США

http://acm.sgu.ru – Саратовский государственный университет

http://acm.zju.edu.cn  - Университет ЖеЙанг, Китай

На сегодняшний день автор содержит страничку по подготовке к олимпиадам по программированию. Страничка находится на сайте кафедры математической информатики Киевского национального университета имени Тараса Шевченко, www.mi.unicyb.kiev.ua, далее следует выбрать «Библиотека», раздел «ACM олимпиады по программированию».

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

Когда я учился в школе, с удовольствием читал все книги по информатике и программированию, которые родители покупали мне без разбора. Сегодня век информационных технологий берет свое. Количество книг сегодня огромно, а уровень глубинки и ведущих школ страны просто не сравним. Хочу привести пример. Еще 5 лет назад когда в Киеве проходили отборы на международные олимпиады – читались лекции. День лекции, день практики – то есть решения задач. Посмотрите сегодняшние условия всеукраинских (всероссийских) и международных олимпиад – эти задачи не каждый студент университета решит. Сегодня на сборы приезжают ребята и говорят: зачем нам лекции? Мы это все знаем – от алгоритма Дейкстры и до сложных задач динамического программирования. Сегодня отборы состоят только из решения задач. Лекции нужны чтобы дойти до уровня всероссийской или международной олимпиады, чтобы воспитать и подготовить призеров олимпиад. 

Сегодня существует много хороших книг по алгоритмам: Кнут «Искусство программирования», Кормен «Построение и анализ алгоритмов», Ахо-Ульман «Структуры данных и алгоритмы». Хотя это уже книги высшей школы. Я считаю, что Кнута школьникам читать рановато, а вот Кормена и Ахо-Ульмана как раз. Особо заинтересованным рекомендую познакомиться с дискретной математикой. По операционным системам, офисным программам, структуре ПК существует масса книг, выпускаемая российскими издательствами. Считаю что каждая из них заслуживает внимания.

Я сам учился в основном по «интернету», в университете мне давали очень хорошую математическую подготовку. А выучить язык – это дело двух недель. Например, про Foxpro я узнал в 1994 году, когда пошел на работу. И Foxpro вместе с SQL выучил именно за две недели :-). Главное – понимать логику работы программы. И какая разница на каком синтаксисе (языке) писать условный или циклический оператор, определение процедур и функций. Недавно выпустил методичку на украинском языке «Олимпиадные задачи по программированию», но думаю что со временем это уже будет полноценная книга. Весь мой материал расположен в открытом виде на сайте, который я упоминал выше.

Что бы вы могли пожелать (посоветовать) учителям, которые прочтут это интервью?

Хочу сказать, что я всегда открыт для общения, с удовольствием отвечу на Ваши вопросы. Пишите мне на почту medv@roller.ukma.kiev.ua. Хочется пожелать, чтобы каждый из нас был настоящим профессионалом своего дела, чтобы с любовью и желанием относился к своей работе. Будь он педагогом высшей школы, или учителем сельской школы. Учитель – это действительно звучит гордо!

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

[к списку интервью]