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

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

Тема 1. Математические основы программирования

Тема отдельной дискуссии.

Тема 2. Техника программирования

1. Основы языка программирования (Паскаль, Си) Переменные и простейшие типы данных, размеры типов. Линейные программы. Условные операторы. Циклы. Процедуры и функции. Сложные типы данных (массивы, строки, записи, указатели, файлы).

2. Массивы Одномерные массивы. Двумерные массивы (матрицы). Многомерные массивы.

3. Строки. Элементы лексического и синтаксического разбора Операции над строками. Лексемы, подсчет лексем различных типов. Выделение чисел из строки.

4. Работа с файлами Чтение и запись в текстовый файл. Преобразование полученных из файла данных в удобную структуру. Работа с типизированными файлами. Нетипизированные файлы. Буферизация ввода.

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

6. "Длинная" арифметика Хранение в программе чисел, которые не вмещаются в стандартные типы. Арифметические операции над "длинными" числами. "Длинные" числа с десятичной частью. Извлечение корня с заданной точностью.

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

Тема 3. Алгоритмы, методы и принципы решения задач

1. Понятие сложности алгоритма. Определение сложности. Классы задач P и NP. NP-полные задачи.

2. Алгоритмы поиска и сортировки Поиск элемента в неупорядоченном массиве. Двоичный поиск по ключу в упорядоченном массиве (дихотомия). Поиск методом Фибоначчи. Поиск в упорядоченном n-мерном массиве. Поиск k-го по величине элемента массива. Простые методы сортировки ("пузырек", "выборка", "вставка", "подсчет"). Быстрые методы ("быстрая", "слиянием", "пирамидальная"), балансировка двоичных деревьев. Сортировка методом черпака.

3. Решение задач методом перебора вариантов. Применение рекурсии для перебора. Генерация сочетаний, размещений, перестановок и булеана множества. Полный перебор. Отсечение вариантов (эвристики). Метод ветвей и границ.

4. Вычислительная геометрия и численные методы. Длина отрезка. Уравнение прямой. Скалярное и векторное произведение. Точка пересечения отрезков. Принадлежность точки фигуре на плоскости (например: треугольнику). Площадь выпуклого многоугольника. Выпуклая оболочка множества точек: алгоритмы Грэхема, Джарвиса, "разделяй и властвуй". Ближайшая пара точек. Метод Гаусса для решения системы линейных уравнений. Нахождение решения уравнения.

5. Принцип динамического программирования. Понятие, применимость. Сравнение с перебором.

6. Жадные алгоритмы. Понятие, применимость. Сравнение с перебором и динамическим программированием.

7. Теория графов. Алгоритмы на графах Понятие графа. Определения теории графов. Структуры данных для представления графа в программе. Алгоритмы обхода графа (поиски в ширину и глубину). Лабиринт (метод волны). Эйлеров цикл. Кратчайший путь во взвешенном графе (алгоритмы Дейкстры и Минти). Транзитивное замыкание графа (алгоритм Флойда-Уоршилла). Минимальное остовное дерево (алгоритмы Прима и Краскала). Топологическая сортировка графа. Потоки в сетях (алгоритм Форда-Фалкерсона). Паросочетания в двудольном графе (метод удлиняющей цепочки, потоковое решение). Задача о назначениях, назначения на узкое место (венгерский алгоритм). Игры на графах. Раскраска графа. Уложение графа на плоскости. Сильная связность и двусвязность графа. Изоморфизм графов. K-клика. Гамильтонов цикл.

8. Лексический и синтаксический анализ Задача "Калькулятор". Синтаксические диаграммы. Формы Бэкуса-Наура. Стековая и рекурсивная модель синтаксического разбора. Конечные автоматы. Грамматики.

9. Задачи с "изюминками".

Тема 4. Олимпиады по информатике

1. Правила проведения олимпиад по программированию

2. Типичные ошибки и отладка программ

3. Приемы олимпиадника

Read More

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

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

Сравнение языков

Я бы рассматривал только такие языки: Free Pascal, GNU C++, Java, C#. С моей точки зрения Basic слишком тупиковая ветвь в плане синтаксиса, чтобы его изучать. Скриптовые языки Perl, Python, PHP, Groovy, Ruby и т.д., ориентированы на быстрое решение каких-то прикладных задач, в основном Web, и не являются базовыми для алгоритмизации. Есть функциональные языки, которые становятся все более популярными в практическом программировании, однако в школе их изучение вероятно только факультативно.

Pascal - классический алгоритмический язык, который позволяет сосредоточится на алгоритмах и реализации своих структур данных. Многие учителя знают этот язык. С другой стороны, не имеет серьезной прикладной реализации (Delphi - не в счет). Нет современной визуальной среды.

C и C++ - прекрасный язык для реализации эффективных алгоритмов. Имеет прикладное применение для реализации критических с точки зрения производительности модулей, разработки для iPhone / iPad. Прекрасно подходит для изучения ООП. Имеет мощные библиотеки алгоритмов, и более эффективный компилятор, нежели Free Pascal, что делает язык наилучшим для применения в олимпиадах. С другой стороны, язык более сложен для изучения - сложная работа с указателями, сложные синтаксис. Язык "позволяет совершать ошибки". Вряд ли у нас много учителей, которые знают С++ и могут ему обучать.

Java - очень востребованный на рынке труда язык (как и технологии с ним связанные), разработки для Android. Может применяться на олимпиадах, но, в основном, со студенческого уровня. Имеет современные среды разработки. С точки зрения обучения более сложен чем Pascal, т.к. требует понимания ООП.

C# -  востребованный на рынке труда язык (в рамках .NET технологии), разработки для мобильных приложений. Допустим в некоторых соревнованиях по программированию со студенческого уровня. С точки зрения обучения более сложен чем Pascal, т.к. требует понимания ООП. Имеет современные среды разработки.

Анализ Цели

Один из важных вопросов. Какую Цель наша образовательная система ставит перед собой? 

1. IT - одно из важнейших направлений экономического развития страны и мы массово готовим профессионалов?
2. Мы развиваем интеллектуальный потенциал нации и делаем акцент на естественные науки в школе?
3. Мы хотим более эффективно выбирать лучших людей способных к информатике, жертвуя при этом средними показателями?

В случае (1) - моя рекомендация ориентироваться на Java, С#, Web технологии. Что-то на постоянной основе, что-то на факультативной. С++ - факультатив для олимпиадников. (2) Наверное, Pascal + C++ - как факультатив для наиболее способных. (3) C++ как база плюс углубленная алгоритмика для олимпиадников.

Численный анализ

У меня есть предположения, что будет легче даваться ребятам, а что будет тяжелее. Но мне сложно дать численную оценку этой разницы. К примеру, оценить сколько людей потеряют интерес к информатике, если учить будут С++ а не Pascal.  Поэтому я бы провел так называемое a/b тестирование. На определенной выборке учителя, с примерно одинаковым знанием языков параллельные группы обучает двум разным языкам и сравнивает результаты по некоему тестированию. На основании этого делается статистический анализ.

Анализ опыта

Кстати, как с этим вопросом обстоят дела в России, США, Китае, Индии? Кто-то изучал их опыт? Нужно как-то синхронизироваться с институтами. Чему учат там?

Главный вопрос

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

С моей точки зрения, нам нужно сосредоточится на образовательной системе на основании удаленных лекций и курсов по примеру https://www.coursera.org/ 

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

Read More