Математические основы информатики.

Функции, отношения и множества.

1.1.1.   Функции, обратная функция, композиция.

1.1.2.   Отношения (рефлексивность, симметричность, транзитивность, эквивалентность, лексикографический порядок).

1.1.3.   Множества (диаграммы Венна, дополнения, декартовы произведения).

1.1.4.   Вполне упорядоченные множества.*

1.1.5.   Мощность и счетность.*

Основные геометрические понятия.

1.2.1.  Точка, прямая, отрезок, вектор, угол.

1.2.2.  Декартовы координаты в евклидовом пространстве.

1.2.3.  Евклидово расстояние.

1.2.4.  Векторное и скалярное произведение на плоскости.

1.2.5.  Треугольник, прямоугольник, многоугольник.

1.2.6.  Выпуклые многоугольники.

Основы логики.

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.  Основы вычислений:

•     Правила суммы и произведения.

•     Арифметические и геометрические прогрессии.

•     Числа Фибоначчи.

•     Принцип включения-выключения.*

1.4.2.  Рекуррентные соотношения.

1.4.3.  Матрицы и действия над ними.*

Методы доказательства.

1.5.1.  Прямые доказательства.

1.5.2.  Доказательство через контрпример.

1.5.3.  Доказательство через противопоставление.

1.5.4.  Доказательство через противоречие.

1.5.5.  Математическая индукция.

1.5.6.  Структура формальных доказательств.*

Основы теории чисел.

1.6.1.  Простые числа. Основная теорема арифметики.

1.6.2.  Деление с остатком.

1.6.3.  Наибольший общий делитель.

1.6.4.  Взаимно простые числа.

1.6.5.  Делимость. Кольцо вычетов по модулю.*

Основы алгебры.

1.7.1.   Многочлены и операции над ними. Решение квадратных уравнений. Теорема Виета.

1.7.2.  Общий случай теоремы Виета. Симметрические многочлены.*

1.7.3.  Понятие группы.*

1.7.4.  Свойства групп.*

1.7.5.  Теоремы о гомоморфизме и изоморфизме.*

Основы комбинаторики

1.8.1.  Перестановки, размещения и сочетания:

•     Основные определения.

•     Тождество Паскаля.

•     Биномиальная теорема.

1.8.2.  Коды Грея: подмножества, сочетания, перестановки.*

1.8.3.  Таблицы инверсий перестановок.*

1.8.4.  Разбиения на подмножества. Числа Стирлинга.*

1.8.5.  Скобочные последовательности.*

Теория графов.

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. Понятие вероятности и математического ожидания. Аксиомы теории вероятностей.*

1.10.2. Формула полной вероятности и формула Байеса. Условное математическое ожидание.*

1.11.   Основы теории игр.

1.11.1. Понятие игры и результата игры.

1.11.2. Простейшие игры и стратегии.

1.11.3. Игры на матрицах.*

Разработка и анализ алгоритмов.

Алгоритмы и их свойства.

2.1.1.  Понятие алгоритма.

2.1.2.  Концепции и свойства алгоритмов.

2.1.3.  Запись алгоритма на неформальном языке.

Структуры данных.

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.1.  Нотация О большое.

2.3.2.  Стандартные классы сложности.

2.3.3.   Асимптотический анализ поведения алгоритмов в среднем и крайних случаях.

2.3.4.  Компромисс между временем и объемом памяти в алгоритмах.*

2.3.5.   Использование рекуррентных отношений для анализа рекурсивных алгоритмов.*

2.3.6.  NP-полнота.*

Алгоритмические стратегии.

2.4.1.  Алгоритмы полного перебора.

2.4.2.  "Жадные" алгоритмы.

2.4.3.  Алгоритмы "разделяй и властвуй".*

2.4.4.  Перебор с возвратом.*

2.4.5.  Эвристики.*

Рекурсия

2.5.1.  Понятие рекурсии.

2.5.2.  Рекурсивные математические функции.

2.5.3.  Простые рекурсивные процедуры.

2.5.4.  Реализация рекурсии.

2.5.5.  Стратегия "разделяй и властвуй".*

2.5.6.  Рекурсивный перебор с возвратами.*