1.
Математические основы информатики
1.1.
Функции, отношения и множества
1.1.1.
Функции, обратная функция,
композиция
1.1.2.
Отношения (рефлексивность,
симметричность, транзитивность, эквивалентность, лексикографический порядок)
1.1.3.
Множества (диаграммы Венна, дополнения,
декартовы произведения)
1.1.4.
Вполне упорядоченные множества *
1.1.5.
Мощность и счетность *
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.7.
Основы алгебры
1.7.1.
Многочлены и операции над ними.
Решение квадратных уравнений. Теорема Виета
1.7.2.
Общий случай теоремы Виета.
Симметрические многочлены *
1.7.3.
Понятие группы *
1.7.4.
Свойства групп *
1.7.5.
Теоремы о гомоморфизме и изоморфизме *
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.11.
Основы теории игр
1.11.1.
Понятие игры и результата игры
1.11.2.
Простейшие игры и стратегии
1.11.3.
Игры на матрицах *
| 
