1.1.4. Обратная функция, композиция *
1.1.5. Лексикографический порядок *
1.1.6. Декартовы произведения *
1.1.7. Вполне упорядоченные множества **
1.1.8. Мощность и счетность множества. Конечные и бесконечные
множества **
1.2. Основные геометрические понятия
1.2.1. Точка, прямая, отрезок, вектор, угол
1.2.2. Треугольник, прямоугольник, многоугольник
1.2.3. Выпуклые многоугольники
1.2.4. Декартовы координаты в евклидовом пространстве
1.2.5. Евклидово расстояние *
1.2.6. Векторное и скалярное произведение на плоскости *
1.3. Основы логики
1.3.1. Логические переменные, операции, выражения
1.3.2. Таблицы истинности
1.3.3. Булевы функции
1.3.4. Формы задания и синтез логических функций *
1.3.5. Преобразование логических выражений *
1.3.6. Минимизация булевых функций **
1.3.7. Основные законы логики суждений **
1.3.8. Логика предикатов **
1.4. Основы вычислений
1.4.1. Основы вычислений:
· Правила суммы и произведения
· Арифметические и геометрические прогрессии *
· Числа Фибоначчи *
· Принцип «включения-выключения» **
1.4.2. Рекуррентные соотношения *
1.4.3. Матрицы и действия над ними **
1.5. Методы доказательства
1.5.1. Прямые доказательства
1.5.2. Доказательство методом «от противного»
1.5.3. Доказательство методом исключения
1.5.4. Доказательство через контрпример
1.5.5. Математическая индукция *
1.5.6. Структура формальных доказательств **
1.6. Основы теории чисел
1.6.1. Простые числа
1.6.2. Деление с остатком
1.6.3. Наибольший общий делитель
1.6.4. Основная теорема арифметики *
1.6.5. Взаимно простые числа *
1.6.6. Делимость. Кольцо вычетов по модулю **
1.7. Основы алгебры
1.7.1. Многочлены и операции над ними. Решение квадратных уравнений. Теорема Виета *
1.7.2. Общий случай теоремы Виета. Симметрические многочлены **
1.7.3. Понятие группы **
1.7.4. Теоремы о гомоморфизме и изоморфизме **
1.8. Основы комбинаторики
1.8.1. Перестановки, размещения и сочетания:
· Основные определения
· Тождество Паскаля *
· Биномиальная теорема *
1.8.2. Коды Грея: подмножества, сочетания, перестановки **
1.8.3. Таблицы инверсий перестановок **
1.8.4. Разбиения на подмножества. Числа Стирлинга **
1.8.5. Скобочные последовательности **
1.9. Теория графов
1.9.1. Типы графов
1.9.2. Маршруты и связность
1.9.3. Деревья
1.9.4. Операции над графами *
1.9.5. Остовные деревья *
1.9.6. Раскраска графов *
1.9.7. Эйлеровы и гамильтоновы графы *
1.9.8. Покрытия и независимость **
1.9.9. Укладка графов. Плоские (планарные) графы **
1.9.10. Двусвязность графа. Мосты, блоки, точки сочленения **
1.9.11. Связь ориентированных ациклических графов и отношений порядка. Транзитивное замыкание **
1.9.12. Двудольные графы **
1.9.13. Потоки и сети **
1.10. Основы теории синтаксического анализа
1.10.1. Обратная польская запись
1.10.2. Синтаксический анализ простых выражений *
1.10.3. Регулярные выражения, конечные автоматы **
1.11. Основы теории вероятностей
1.11.1. Понятие вероятности и математического ожидания *
1.11.2. Аксиомы теории вероятностей **
1.11.3. Основы вычисления вероятностей **
1.12. Основы теории игр
1.12.1. Понятие игры и результата игры
1.12.2. Простейшие игры
1.12.3. Простейшие стратегии игры *
1.12.4. Игры на матрицах **
1.12.5. Решение игровых задач с использованием функции Гранди **
2. Разработка и анализ алгоритмов
2.1. Алгоритмы и их свойства
2.1.1. Понятие алгоритма
2.1.2. Концепции и свойства алгоритмов
2.1.3. Запись алгоритма на неформальном языке
2.2. Структуры данных
2.2.1. Простые базовые структуры
2.2.2. Множества
2.2.3. Последовательности
2.2.4. Списки
2.2.5. Неориентированные графы *
2.2.6. Ориентированные графы *
2.2.7. Деревья *
2.2.8. Пирамида и дерево отрезков **
2.2.9. Сбалансированные деревья **
2.2.10. Хэш-таблицы и ассоциативные массивы **
2.2.11. Бор **
2.3. Основы анализа алгоритмов
2.3.1. Нотация О большое *
2.3.2. Стандартные классы сложности *
2.3.3. Асимптотический анализ поведения алгоритмов в среднем и крайних
случаях *
2.3.4. Компромисс между временем и объемом памяти в алгоритмах **
2.3.5. Использование рекуррентных отношений для анализа рекурсивных алгоритмов **
2.3.6. NP-полнота **
2.4. Алгоритмические стратегии
2.4.1. Алгоритмы полного перебора
2.4.2. "Жадные" алгоритмы *
2.4.3. Алгоритмы "разделяй и властвуй" *
2.4.4. Перебор с возвратом *
2.4.5. Эвристики **
2.5. Рекурсия
2.5.1. Понятие рекурсии
2.5.2. Рекурсивные математические функции *
2.5.3. Простые рекурсивные процедуры *
2.5.4. Реализация рекурсии *
2.5.5. Рекурсивный перебор с возвратами **
2.6. Фундаментальные вычислительные алгоритмы
2.6.1. Простые численные алгоритмы
2.6.2. Классические комбинаторные алгоритмы
2.6.3. Алгоритмы с подмножествами: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего (прибавление и вычитание единицы)
2.6.4. Алгоритмы последовательного и бинарного поиска
2.6.5. Алгоритмы с сочетаниями и перестановками (генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего) *
2.6.6. Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками) *
2.6.7. Сортировка подсчетом за линейное время *
2.6.8. Алгоритмы сортировки за время O(N log N) (быстрая сортировка, пирамидальная сортировка, сортировка слиянием) **
2.6.9. Цифровая сортировка **
2.6.10. Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов **
2.6.11. Арифметика многоразрядных целых чисел **
2.7. Числовые алгоритмы
2.7.1. Разложение числа на простые множители
2.7.2. Решето Эратосфена *
2.7.3. Алгоритм Евклида *
2.7.4. Расширенный алгоритм Евклида. Способы реализации алгоритма без деления **
2.7.5. Решение линейных сравнений с помощью алгоритма Евклида **
2.7.6. Эффективная реализация решета Эратосфена (O(n)) **
2.7.7. Эффективная проверка числа на простоту **
2.7.8. Быстрые алгоритмы разложения чисел на простые множители.
Ро-эвристика **
2.8. Алгоритмы на строках
2.8.1. Поиск подстроки в строке. Наивный метод *
2.8.2. Алгоритмы поиска подстроки в строке за O(N+M) **
2.8.3. Периодические и циклические строки **
2.8.4. Алгоритм поиска нескольких подстрок за линейное время **
2.9. Алгоритмы на графах
2.9.1. Вычисление длин кратчайших путей в дереве
2.9.2. Обход графа в ширину и в глубину
2.9.3. Способы реализации поиска в ширину (“наивный” и с очередью) *
2.9.4. Проверка графа на связность *
2.9.5. Алгоритмы поиска кратчайшего пути во взвешенных графах *
2.9.6. Топологическая сортировка графа, нахождение компонент сильной связности и построение диаграммы порядка **
2.9.7. Циклы отрицательной длины – критерий наличия, поиск **
2.9.8. Задача о синхронизации времени и задача о системе неравенств **
2.9.9. Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального) **
2.9.10. Нахождение транзитивного замыкания графа **
2.9.11. Алгоритмы нахождения взвешенных остовных деревьев **
2.9.12. Алгоритмы отыскания компонент двусвязности, точек сочленения, мостов с помощью поиска в глубину **
2.9.13. Алгоритм нахождения максимального паросочетания и минимального вершинного покрытия в двудольном графе **
2.9.14. Поиск максимального потока в сети **
2.10. Динамическое программирование
2.10.1. Основная идея динамического программирования. Рекурсивная реализация и развертывание в цикл *
2.10.2. Задачи с монотонным направлением движения в таблице *
2.10.3. Задача о рюкзаке – решение методом динамического программирования *
2.10.4. Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних параметров) **
2.10.5. Восстановление решения в задачах динамического программирования **
2.10.6. Общая схема решения задач динамического программирования **
2.11. Алгоритмы теории игр
2.11.1. Динамическое программирование и полный перебор как методы решения игровых задач **
2.11.2. Игры на ациклическом графе **
2.11.3. Оценка позиций. Альфа-бета отсечение **
2.12. Геометрические алгоритмы
2.12.1. Алгоритмы определения совпадения точек, лучей, прямых и отрезков
2.12.2. Представление точек, прямых и отрезков на плоскости *
2.12.3. Нахождение расстояний между объектами на плоскости **
2.12.4. Алгоритмы определения пересечения отрезков на плоскости **
2.12.5. Алгоритмы вычисления площади многоугольника с заданными координатами вершин. Случай целочисленной решетки (формула Пика) **
2.12.6. Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса) **
2.12.7. Окружности на плоскости, пересечение их с другими геометрическими объектами **
2.12.8. Эффективный алгоритм нахождения пары ближайших точек на
плоскости **
3. Основы программирования
3.1. Языки программирования
3.1.1. Классификация языков программирования
3.1.2. Процедурные языки
3.1.3. Основы синтаксиса и семантики языков высокого уровня *
3.1.4. Формальные методы описания синтаксиса: форма Бэкуса-Наура **
3.1.5. Объектно-ориентированные языки **
3.2. Основные конструкции программирования
3.2.1. Переменные, типы, выражения и присваивания
3.2.2. Основы ввода/вывода
3.2.3. Операторы проверки условия и цикла
3.2.4. Функции и передача параметров *
3.2.5. Структурная декомпозиция **
3.3. Переменные и типы данных
3.3.1. Концепция типа данных как множества значений и операций над ними
3.3.2. Свойства объявлений (связывание, область видимости, блоки и время
жизни) *
3.3.3. Обзор проверки типов *
3.4. Типы структур данных
3.4.1. Примитивные типы
3.4.2. Массивы
3.4.3. Записи *
3.4.4. Стратегии выбора подходящей структуры данных *
3.4.5. Представление данных в памяти **
3.4.6. Статическое, автоматическое и динамическое выделение памяти **
3.4.7. Указатели и ссылки **
3.4.8. Связанные структуры **
3.4.9. Методы реализации стеков, очередей и хэш-таблиц **
3.4.10. Методы реализации графов и деревьев **