DS1/Функции Отношения Множества [основной]
DS2/Основы логики [основной]
DS3/Методы доказательства [основной]
DS4/Основы вычислений [основной]
DS5/Графы и деревья [основной]
DS6/Дискретная вероятность [основной]
DS/Функции Отношения Можества [основной]
Минимальное время, отводимое на модуль: 6 часов
Темы:
· Функции (сюръекции, инъекции, обратные функции, композиция)
· Отношения (рефлексивность, симметричность, транзитивность, эквивалентность)
· Множества (диаграммы Венна, дополнения, декартовы произведения, степенные множества)
· Принцип Дирихле
· Мощность и счетность
Цели обучения:
1. Объяснять с примерами основные понятия функций, отношений и множеств.
2. Выполнять операций, связанные с множествами, функциями и отношениями.
3. Связывать практические примеры с подходящими моделями множеств, функций и отношений, а также дать в
этом контексте интерпретацию соответствующих операций.
DS2/Основы логики [основной]
Минимальное время: 10 часов
Темы:
- Логика высказываний
- Логические связки
- Таблицы истинности
- Нормальные формы (конъюнктивные и дизъюнктивные)
- Общезначимость (тавтология)
- Логика предикатов
- Кванторы всеобщности и существования
- Правила modus ponens и modus tollens
- Ограничения логики предикатов
Цели обучения:
1. Обучить применению формальных методов символической логики высказываний и логики предикатов.
2. Показать использование формальных средств символической логики для моделирования алгоритмов и реаль-
ных жизненных ситуаций.
3. Использовать формальные логические доказательства и логическое рассуждение для решения задач, напри-
мер, головоломок.
4. Описать применимость и ограничения логики предикатов.
DS3/Методы доказательства [основной]
Минимальное время: 12 часов
Темы:
- Понятия импликации, обращения, противопоставления, контрапозиции, отрицания и противоречия
- Структура формальных доказательств
- Прямые доказательства
- Доказательство через контрпример
- Доказательство через контрапозицию
- Доказательство через противоречие
- Математическая индукция
- Сильная индукция
- Рекурсивные математические определения
- Вполне упорядоченные множества
Задачи обучения:
1. Обрисовать основную структуру и дать примеры каждого метода доказательств, описанных выше.
2. Обсудить, какой вид доказательства лучше подходит для данной задачи.
3. Связать идеи математической индукции с понятием рекурсии и рекурсивно определенных структур.
4. Указать различия между математической и сильной индукцией и дать примеры адекватного использования
каждого из этих методов.
DS4/Основы вычислений [основной]
Минимальное время: 5 часов
Темы:
- Основы вычислений:
- Правила суммы и произведения
- Принцип включения-выключения
- Арифметические и геометрические прогрессии
- Числа Фибоначчи
- Принцип Дирихле
- Перестановки и сочетания
- Основные определения
- Тождество Паскаля
- Биномиальная теорема
- Решение рекуррентных соотношений
- Общие примеры
- Основная теорема рекуррентных соотношений
Цели обучения:
1. Вычислять перестановки и сочетания множества, а также интерпретировать их значения в контек-
сте конкретного приложения.
2. Формулировать основную теорему рекуррентных соотношений.
3. Решать типичные рекуррентные соотношения.
4. Анализировать задачу построения рекуррентных уравнений или выявлять связанные с ней вычислительные вопросы.
DS5/Графы и деревья [основной]
Минимальное время: 4 часа
Темы:
- Деревья
- Неориентированные графы
- Ориентированные графы
- Остовные деревья/леса
- Стратегии обхода графов
Цели обучения:
1. Иллюстрировать на примерах основные понятия теории графов, а также их свойства и специальные случаи использования.
2. Демонстрировать различные методы обхода деревьев и графов.
3. Использовать деревья и графы при моделировании задач информатики.
4. Показывать связь графов и деревьев со структурами данных, алгоритмами и вычислениями.
DS6/Дискретная вероятность [основной]
Минимальное время: 6 часов
Темы:
- Конечное вероятностное пространство, вероятностная мера, события
- Условная вероятность, независимость событий, теорема Байеса
- Целочисленные случайные величины, математическое ожидание
- Закон больших чисел
Цели обучения:
1. Вычислять вероятности событий и математического ожидания случайных величин для элементарных задач, таких как игра в рулетку.
2. Различать независимые и зависимые события.
3. Применять биномиальную теорему для независимых событий и теорему Байеса для зависимых событий.
4. Применять вероятностные методы к решению таких задач, как метод Монте-Карло, анализ среднего случая алгоритмов и хеширование.
Литература
1. Санкт-Петербургский государственный университет. Рекомендации по преподаванию информатики в университетах. С.-Петербург, 2002
2. Computer Science 2008 (CS2008). Association for Computing Machinery and Computer Society of IEEE.
