32. Буки программирования. Программа

1. Повторим Азы.
   – Программирование и язык программирования.
   – Теоретическое и прикладное программирование.
   – Процедурное программирование.
   – Переменная, присваивание, процедура, цикл, массив.
   – Что такое правильная программа?
   – Доказательство правильности, тестирование, отладка.
   – Теоретическое и прикладное программирование.
   – Уровни абстракции в программировании.
   – Парадигмы программирования.
   – Сложность алгоритмов. Анализ сложности.
   – Обзор литературы.
   
   
2. Целые числа.
   – Значение и внешнее представление числа.
   – Системы счисления.
   – Перевод из одной системы в другую.
   – Моделирование действий.
   – Вычисления с повышенной точностью.
   – Моделирование длинной арифметики.
   – Элементы теории чисел.
   – Делимость.
   – Простые числа.
   
   
3. Построение последовательностей.
   – Явно заданные последовательности.
   – Прямые вычисления и рекуррентные соотношения.
   – Программирование прямых вычислений.
   – Избавление от рекуррентности.
   – Математическая индукция.
   – Программирование рекуррентных соотношений.
   – Неявно заданные последовательности.
   – Рекуррентность вместо прямых вычислений.
   – Построение с поиском.
   – Методы сокращения поиска.
   – Сведение поиска к рекуррентности.
   – Сведение поиска к прямому вычислению.
   
   
4. Анализ последовательностей.
   – Общая постановка задачи.
   – Однопроходные алгоритмы.
   – Поиск в последовательности.
   – Поиск как частный случай анализа.
   – Поиск последовательным перебором.
   – Поиск в упорядоченном массиве.
   – Двоичный поиск.
   – Поиск по образцу.
   – Алгоритм перебора.
   – Алгоритм Кнута-Мориса-Пратта.
   – Алгоритм Бойера-Мура.
   – Алгоритм Рабина.
   
   
5. Элементы комбинаторики.
   – Комбинаторные задачи.
   – Подмножества.
   – Перестановки.
   – Размещения.
   – Сочетания.
   – Количество подмножеств.
   – Перебор подмножеств и двоичный код.
   – Плавный перебор подмножеств.
   – Коды Грэя.
   – Размещения с повторениями.
   – Перебор размещений с повторениями.
   – Размещения без повторений.
   – Перебор размещений без повторений.
   – Перебор с возвратом.
   – Перестановки.
   – Количество перестановок.
   – Перебор перестановок.
   – Переход к следующей перестановке.
   – Плавный перебор перестановок.
   – Сочетания.
   – Количество сочетаний.
   – Перебор сочетаний.
   – Плавный перебор сочетаний.
   
   

Пояснительная записка

Что такое Буки программирования?

Вас заинтриговало это название? Может быть, оно показалось вам угрюмым и мрачным? Не пугайтесь! Наши БУКИ не имеют ничего общего с бяками. БУКИ — это то, что идет после АЗов, то, что на наш взгляд должны изучать начинающие программисты после того, как они освоили основные элементы своего первого языка, радостно вывели на экран «Hello, world!» и научились подсчитывать сумму элементов массива.

Чем мы будем заниматься?

Мы будем учиться решать задачи, в том числе олимпиадного типа.

Будем рассматривать классические задачи и методы их решения.

Будем составлять и анализировать алгоритмы, причем составлять не «по наитию», а «по науке».

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

И конечно же, мы будем писать программы — ведь без этого научиться программировать просто невозможно.

Чего у нас не будет?

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

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

На кого рассчитан курс?

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

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

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

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

Организация работы

Команды получают из RU следующие материалы:

• календарный план занятий и конкурсов;
• темы для изучения и задачи.

Процесс обучения в каждом семестре строится так:

• изучение тем семестра
• общение с куратором и сокурсниками
• турнир
• перекрестная проверка и проверка куратора
• подведение итогов, разбор решений, анализ типичных ошибок

Связь с куратором

Если у вас остались вопросы, то их можно задать куратору Зайдельману Якову Наумовичу по адресу buki@yz.botik.ru.