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

Бакалавриат 2019/2020

Статус: Курс по выбору (Совместная программа по экономике НИУ ВШЭ и РЭШ)

Направление: 38.03.01. Экономика

Кто читает: Отдел сопровождения учебного процесса в Совместном бакалавриате ВШЭ-РЭШ

Где читается: Факультет экономических наук

Когда читается: 2-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Язык: русский

Кредиты: 6

Контактные часы: 64

Полная версия программы учебной дисциплины

Аннотация

В нашем курсе мы познакомим студентов с основами современной ``Computer Science''. Наука эта бурно развивается, и сейчас в ней есть масса разнообразных направлений, связанных с теорией графов, математической логикой и теорией алгоритмов, теорией кодирования и криптографией, теорией информации, теорией вероятностей и др. Разумеется, в одном семестровом курсе невозможно охватить такое многообразие сюжетов. Цель ——- дать почувствовать дух этой красивой и глубоко математизированной системы дисциплин. Курс будет интересен всем, кто увлекается комбинаторикой, теорией графов и алгоритмами, а также не боится слова ``вероятность''.

Цель освоения дисциплины

Целью освоения дисциплины «Теоретические основы информатики» является освоение теоретических основ информатики, необходимых для изучения и понимания прикладных информационных технологий и систем

Планируемые результаты обучения

Знает основы комбинаторного анализа
Владеет основными понятиями теории графов
Знаком с теорией вероятности и гиперграфами
Знает основы теории Рамсея

Содержание учебной дисциплины

Основы комбинаторного анализа.
1. Основные правила комбинаторики: правило сложения, правило умножения, принцип Дирихле. 2. Размещения, перестановки и сочетания. Факториал. Формулы для чисел размещения и сочетания с повторениями и без повторений. 3. Бином Ньютона, полиномиальная формула. Биномиальные и полиномиальные коэффициенты. Простейшие тождества. Как следствие, треугольник Паскаля и формулы для сумм степеней натуральных чисел. 4. Формула включения и исключения. Знакопеременные тождества. Задача о беспорядках. 5. Линейные рекуррентные соотношения с постоянными коэффициентами: полное решение для соотношений второго порядка и теорема б/д о соотношениях произвольного порядка. Числа Фибоначчи и короткая формула для них. 6. Степенные ряды и производящие функции. Теорема б/д о сходимости степенного ряда: отыскание радиуса сходимости, примеры, поясняющие формулу для радиуса, тонкости, связанные с граничными точками интервала сходимости (примеры). Производящая функция для чисел Фибоначчи. Отыскание сумм с биномиальными и полиномиальными коэффициентами. 7. Коды, исправляющие ошибки. Задача о максимальном количестве трехэлементных подмножеств конечного множества с запрещенным пересечением по одному элементу: конструкция и верхняя оценка по индукции.
Основы теории графов.
1. Определение графа, орграфа, мультиграфа, псевдографа и т.д. Примеры. 2. Маршруты в графах (цепи, циклы и пр.). 3. Связность графа, связные компоненты. 4. Деревья. 4 эквивалентных определения. Формула Кэли для числа деревьев на n вершинах. 5. Унициклические графы. Формула для числа унициклических графов на n вершинах (число лесов б/д). Асимптотика б/д 6. Эйлеровские циклы. Критерий эйлеровости графа. Планарность графа. Гомеоморфизм графов. Формулировка критерия Куратовского (б/д). 7. Гамильтоновы циклы. Признак Дирака б/д. Число независимости и вершинная связность графа. Признак Эрдеша—Хватала. Пример с графом, у которого вершины – трехэлементные подмножества n-элементного множества, а ребра – пары подмножеств с мощностью пересечения 1 8. Хроматическое число графа, клики и кликовое число графа, независимые множества вершин графа и его число независимости. Двудольные графы. Хроматическое, кликовое числа и число независимости для полного графа, цикла, дерева и др. примеры. Проблема 4х красок (просто постановка и небольшая история). Практические применения задачт о хроматическом числе графа. Нижние оценки хроматического числа: через кликовое число и через число независимости. Верхняя оценка через максимальную степень вершины. Уточнение Брукса (б/д)
Основы теории вероятностей и гиперграфы.
1. Классическое определение вероятности: пример с игральной костью и общее определение. Свойства классической вероятности. 2. Определение гиперграфа. Однородные гиперграфы. Хроматическое число гиперграфа. Задача о величине m(n). Нижняя оценка величиной 2^{n-1} с помощью классической вероятности. Простая верхняя оценка величиной C_{2n-1}^n. 3. Условная вероятность. Пояснение определения. Теорема умножения. Независимость с пояснением определения. Независимость в совокупности и ее связь с попарной независимостью. Формулы полной вероятности и Байеса с примерами. 4. Оценка m(n) <= (1+o(1))(e ln 2) 2^{n-2} n^2 с помощью независимого выбора случайных ребер. 5. Схема испытаний Бернулли. Классическое определение вероятности как частный случай. 6. Оценка m(n) >= \sqrt[3]{n/ln n} 2^{n-2} с помощью рандомизированного алгоритма, основанного на двухкратном применении схемы Бернулли.
Числа Рамсея.
1. Определение числа Рамсея в терминах знакомств, в терминах раскрасок и в терминах клик и независимых множеств. Числа R(3,3), R(1,s), R(2,s). Проблема числа R(3,t) 2. Рекуррентная верхняя оценка для R(s,t). Ее следствия. Описание проблемы экспоненциального понижения оценки (даже на 3.999 не удается пока заменить 4). 3. Нижняя оценка для R(s,s) величиной 2^{s/2}. Ее сравнение с верхней оценкой. Самая лучшая нижняя оценка (б/д). 4. Алгоритмическая нижняя оценка для R(s,s): Оценка Турана (s-1)^2 и ее улучшение до (1+o(1))s^3/6 с помощью графа из пп. 7 разделов 1 и 2. Самая лучшая известная оценка (б/д).

Элементы контроля

Промежуточная контрольная работа
Домашние задания ( 4 шт.)
Итоговая контрольная работа

Промежуточная аттестация

Промежуточная аттестация (3 модуль)
0.7 * Домашние задания ( 4 шт.) + 0.3 * Промежуточная контрольная работа
Промежуточная аттестация (4 модуль)
0.3 * Итоговая контрольная работа + 0.7 * Промежуточная аттестация (3 модуль)

Программа дисциплины