# Вступительный экзамен

<!-- Не трогаем этот блок -->
<a class="btn btn-danger disabled" href="#" role="button"><i class="fa fa-file-pdf-o fa-fw"></i> Скачать PDF</a> <a class="btn btn-info" href="https://hackmd.io/s/ryUHFWfY4" role="button"><i class="fa fa-file-text-o fa-fw"></i> Открыть на HackMD</a> <a class="btn btn-primary" href="https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference" role="button"><i class="fa fa-question-circle fa-fw"></i> $\LaTeX$</a> <a class="btn btn-primary" href="http://ctan.altspu.ru/info/short-math-guide/short-math-guide.pdf" role="button"><i class="fa fa-question-circle fa-fw"></i> Short Math Guide v2.0</a> <a class="btn btn-danger" href="https://t.me/year2015" role="button"><i class="fa fa-heart fa-fw"></i> year2015</a>
<style>#doc.markdown-body,.ui-infobar{max-width:900px}#doc.markdown-body ul,#doc.markdown-body ol{padding-left:10px!important;margin-left:10px!important}#doc .btn{margin-top:5px}</style>

## Источники

- [cdtgos](https://code.google.com/archive/p/cdtgos/wikis/Tickets.wiki)
- [ifmo-ctd-2008-bachelor-gos](https://yadi.sk/d/AiGNrkU_rLETAQ)
- [Прошлогодний гуглодок](https://docs.google.com/document/d/e/2PACX-1vQrGPvwqOcdf0bvS5ZMh5fmx_DZrGt2_frEzq-AoGVJIxR0ArOTtmyBTwt87LCANKbHecXVsR6gttIa/pub)
- [Прошлогодний архив](https://www.dropbox.com/sh/4st5b16mvdf8gkj/AAAOoieXQez-Ms5kbnE6X60fa?dl=0) + [зеркало](https://yadi.sk/d/4h-sUT7FzWvITQ)

> ✅ — готов
> 🔄 — не совсем готов
> 🔴 — совсем не готов

## Математика

### 🔴 1. Кратные, поверхностные и криволинейные интегралы. Формулы Грина, Стокса и Остроградского.

### 🔴 2. Числовые ряды. Абсолютная и условная сходимость. Признаки сходимости числовых рядов.

### 🔴 3. Функциональные ряды, свойства равномерно сходящихся функциональных рядов. Степенные ряды. Ряд Тейлора.

### 🔴 4. Тригонометрические ряды Фурье. Преобразования Фурье.

### 🔴 5. Аналитические функции комплексной переменной. Интегральная формула Коши. Особые точки, вычеты. Конформные отображения.

### 🔴 6. Определители и их свойства. Системы линейных алгебраических уравнений и их исследование. Методы решения систем линейных алгебраических уравнений.

### 🔴 7. Линейные операторы в конечномерном пространстве и их матричное представление. Характеристический многочлен, собственные числа и собственные вектора линейного оператора. Сопряженные и самосопряженные операторы.

### 🔴 8. Задача Коши для системы обыкновенных дифференциальных уравнений. Существование и единственность решения. Устойчивость.

### 🔴 9. Линейные обыкновенные дифференциальные уравнения и системы. Фундаментальная система решений. Метод вариации постоянных для решения неоднородных уравнений.

### 🔴 10. Классификация линейных дифференциальных уравнений в частных производных второго порядка. Уравнение переноса, уравнение теплопроводности, волновые уравнения, уравнения эллиптического типа. Постановка краевых задач, граничные условия.

### 🔴 11. Случайные величины и их функции распределения. Математическое ожидание и дисперсия. Локальная предельная теорема.

## Прикладная математика

### 🔴 1. Элементы теории погрешностей вычислений: источники и классификация погрешностей, погрешности арифметических операций и функций.

### 🔴 2. Корректность вычислительных задач: вычислительная устойчивость и обусловленность, примеры хорошо и плохо обусловленных задач.

### 🔴 3. Численное решение нелинейных алгебраических уравнений: обусловленность задачи, методы простых итераций и Ньютона.

### 🔴 4. Прямые методы решения систем линейных алгебраических уравнений: обусловленность задачи, метод Гаусса и его модификации, метод прогонки.

### 🔴 5. Итерационные методы решения систем линейных алгебраических уравнений: методы простых итераций, Гаусса-Зейделя, последовательной релаксации, спуска.

### 🔴 6. Численное решение систем нелинейных уравнений: методы простых итераций, Ньютона, спуска, комбинированный метод.

### 🔴 7. Приближение функций: интерполяция и аппроксимация. Интерполяционный многочлен в форме Лагранжа и Ньютона-Котеса, стратегия интерполяции, интерполяция сплайнами. Метод наименьших квадратов.

### 🔴 8. Приближенное вычисление интегралов: формулы прямоугольников, трапеций, Симпсона, оценка погрешности. Способы вычисления кратных интегралов.

### 🔴 9. Одношаговые квадратурные методы решения задачи Коши для обыкновенных дифференциальных уравнений (ОДУ): явный и неявный методы Эйлера и Рунге-Кутты.

### 🔴 10. Многошаговые квадратурные методы решения задачи Коши для ОДУ: явный метод Адамса-Бэшфорта, неявный метод Адамса-Моултона, метод «предиктор-корректор».

### 🔴 11. Численное решение краевых задач для ОДУ: метод сведения к задаче Коши, разностный метод, проблема разрешимости.

### 🔴 12. Дискретизация начально-краевой задачи для дифференциальных уравнений в частных производных (ДУЧП): разностная сетка, шаблон и схема, явная и неявная разностные схемы. Понятия аппроксимации, устойчивости и сходимости, теорема Лакса.

### 🔴 13. Построение разностных схем: метод рядов Тейлора, параметрическая схема, метод конечных объемов (интегро-интерполяционный метод).

### 🔴 14. Анализ устойчивости разностных схем: методы дифференциального приближения и Фон-Неймана, критерий Куранта-Фридрихса-Леви.

### 🔴 15. Разностное решение систем ДУЧП параболического типа: явная схема, диагонально-неявная и полностью неявная схемы, векторная прогонка.

### 🔴 16. Разностное решение многомерных ДУЧП параболического типа: методы расщепления, схема переменных направлений.

## Информатика

### 🔄 1. Множества и операции над ними. Булевы функции, КНФ, ДНФ. Базисы, теорема Поста.

> Билеты: [3.01](https://yadi.sk/i/ptr3D13yML90oQ)
> Викиконспекты: [Множества](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0), [Булевы функции](http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.91.D1.83.D0.BB.D0.B5.D0.B2.D1.8B_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B8), [КНФ](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%9D%D0%A4), [ДНФ](http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%9D%D0%A4), [теорема Поста](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D1%81%D1%82%D0%B0_%D0%BE_%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D0%B9_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B5_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9)

### 🔄 2. Структуры данных. Линейные (списки, очереди, деки, вектора). Очереди с приоритетами. Деревья поиска.

> Билеты: [3.02](https://yadi.sk/i/kdD0hZL4YRIkbQ)
> Викиконспекты: [Алгоритмы и структуры данных](http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85), [Список](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA), [Очередь](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C), [Дек](http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA), [Вектор](http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2), [Очередь с приоритетами](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BE%D1%80%D0%B8%D1%82%D0%B5%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D0%B8), [Поисковые структуры данных](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA%D0%BE%D0%B2%D1%8B%D0%B5_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85),

### 🔄 3. Алгоритмы на графах. Обходы графов. Кратчайшие пути. Остовные деревья.

> Билеты: [3.03](https://yadi.sk/i/W1V7GB86d-g1jQ)
> Викиконспекты: [Теория графов](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2), [Кратчайшие пути](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2#.D0.9A.D1.80.D0.B0.D1.82.D1.87.D0.B0.D0.B9.D1.88.D0.B8.D0.B5_.D0.BF.D1.83.D1.82.D0.B8_.D0.B2_.D0.B3.D1.80.D0.B0.D1.84.D0.B0.D1.85), [Остовные деревья](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2#.D0.9E.D1.81.D1.82.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D1.8C.D1.8F)

### 🔄 4. Задачи комбинаторной оптимизации: о максимальном потоке, о паросочетании, о потоке минимальной стоимости.

> Билеты: [3.04](https://yadi.sk/i/CCIZmlXBDG7mdA)
> Викиконспекты: [Задача о максимальном потоке](http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D0.BC.D0.B0.D0.BA.D1.81.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D0.BC_.D0.BF.D0.BE.D1.82.D0.BE.D0.BA.D0.B5), [Задача о паросочетании](http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D0.BF.D0.B0.D1.80.D0.BE.D1.81.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D0.B8), [Задача о потоке минимальной стоимости](http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D0.BF.D0.BE.D1.82.D0.BE.D0.BA.D0.B5_.D0.BC.D0.B8.D0.BD.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D0.B9_.D1.81.D1.82.D0.BE.D0.B8.D0.BC.D0.BE.D1.81.D1.82.D0.B8)

### 🔄 5. Вычислительная геометрия на плоскости. Уравнения точек, прямых, окружностей. Выпуклые оболочки, алгоритмы построения. Алгоритмы триангуляции. Задачи регионального поиска.

> Билеты: [3.05](https://yadi.sk/d/rldn4K_3KhTnHg)
> Викиконспекты: [Предикат "левый поворот"](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B5%D0%B4%D0%B8%D0%BA%D0%B0%D1%82_%22%D0%BB%D0%B5%D0%B2%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B2%D0%BE%D1%80%D0%BE%D1%82%22), [Выпуклые оболочки](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%82%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%B2%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D1%8B%D0%B5_%D0%BE%D0%B1%D0%BE%D0%BB%D0%BE%D1%87%D0%BA%D0%B8:_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81,_%D0%93%D1%80%D1%8D%D1%85%D0%B5%D0%BC,_%D0%AD%D0%BD%D0%B4%D1%80%D1%8E,_%D0%A7%D0%B5%D0%BD,_QuickHull), [Триангуляция](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D1%80%D0%B8%D0%B0%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D0%BF%D0%BE%D0%BB%D0%B8%D0%B3%D0%BE%D0%BD%D0%BE%D0%B2_(%D1%83%D1%88%D0%BD%D0%B0%D1%8F_%2B_%D0%BC%D0%BE%D0%BD%D0%BE%D1%82%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F)), [Задачи поиска](http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B3%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%8F#.D0.9F.D0.BE.D0.B8.D1.81.D0.BA)

### 🔄 6. Конечные автоматы и регулярные языки, их эквивалентность. Детерминизация и минимизация автоматов.

> Билеты: [3.06](https://yadi.sk/d/4HEIgyTCK175Jg)
> Викиконспекты: [Теория формальных языков](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2), [Основные определения](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F,_%D1%81%D0%B2%D1%8F%D0%B7%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D0%BE_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B0%D0%BC%D0%B8), [Эквивалентность автоматам](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%BE%D0%BA%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0%D0%BC)

### 🔄 7. Контекстно-свободные грамматики. Нормальная форма Хомского. Общие методы разбора.

> Билеты: [3.07](https://yadi.sk/i/DzTCoW_3sUNk3g)
> Викиконспекты: [Теория формальных языков](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2#.D0.9A.D0.BE.D0.BD.D1.82.D0.B5.D0.BA.D1.81.D1.82.D0.BD.D0.BE-.D1.81.D0.B2.D0.BE.D0.B1.D0.BE.D0.B4.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D0.B0.D1.82.D0.B8.D0.BA.D0.B8), [Контекстно-свободные грамматики](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D0%BE-%D1%81%D0%B2%D0%BE%D0%B1%D0%BE%D0%B4%D0%BD%D1%8B%D0%B5_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8,_%D0%B2%D1%8B%D0%B2%D0%BE%D0%B4,_%D0%BB%D0%B5%D0%B2%D0%BE-_%D0%B8_%D0%BF%D1%80%D0%B0%D0%B2%D0%BE%D1%81%D1%82%D0%BE%D1%80%D0%BE%D0%BD%D0%BD%D0%B8%D0%B9_%D0%B2%D1%8B%D0%B2%D0%BE%D0%B4,_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D1%80%D0%B0%D0%B7%D0%B1%D0%BE%D1%80%D0%B0), [Иерархия Хомского](http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA), [Нормальная форма Хомского](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE), [Алгоритмы разбора](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D1.8B_.D1.80.D0.B0.D0.B7.D0.B1.D0.BE.D1.80.D0.B0)

### 🔄 8. Контекстно-свободные грамматики. Эффективные методы разбора: LL и LR грамматики.

> Билеты: [3.08](https://yadi.sk/i/i1Ql6rsn1AGjcw), [3.08.1](https://yadi.sk/i/qpk8Y_v0hHcf3Q)
> Викиконспекты: [Методы трансляции](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D1%82%D1%80%D0%B0%D0%BD%D1%81%D0%BB%D1%8F%D1%86%D0%B8%D0%B8), [LL-грамматики](http://neerc.ifmo.ru/wiki/index.php?title=LL(k)-%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B8,_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_FIRST_%D0%B8_FOLLOW)

### 🔄 9. Разрешимые и перечислимые языки. Неразрешимые проблемы. Проблема останова. Теорема Райса.

> Билеты: [3.09](https://yadi.sk/i/RR9rNutPWWZrIw) (странные определения)
> Викиконспекты: [Теория вычислимости](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8), [Разрешимые языки](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D1%8B%D0%B5_(%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5)_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B8), [Перечислимые языки](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D0%B5_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B8), [Примеры неразрешимых задач](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.80.D1.8B_.D0.BD.D0.B5.D1.80.D0.B0.D0.B7.D1.80.D0.B5.D1.88.D0.B8.D0.BC.D1.8B.D1.85_.D0.B7.D0.B0.D0.B4.D0.B0.D1.87), [Теорема Успенского-Райса](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A3%D1%81%D0%BF%D0%B5%D0%BD%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D0%A0%D0%B0%D0%B9%D1%81%D0%B0)

### 🔄 10. Комбинаторная теория сложности. Временная и емкостная сложность. Сложностные классы P, NP, PS. Сведение, NP-полные задачи.

> Билеты: [3.10](https://yadi.sk/i/PgHx3eGJG4B5ZQ)
> Викиконспекты: [Теория сложности](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8), [Классы сложности](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D1%8B%D0%B5_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D1%8B), [Класс PS](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81_PS._%D0%A1%D0%B2%D1%8F%D0%B7%D1%8C_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B0_PS_%D1%81_%D0%B4%D1%80%D1%83%D0%B3%D0%B8%D0%BC%D0%B8_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B0%D0%BC%D0%B8_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8), [Сведение по Карпу](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B0_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9._%D0%A1%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%9A%D0%B0%D1%80%D0%BF%D1%83._%D0%A2%D1%80%D1%83%D0%B4%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%BF%D0%BE%D0%BB%D0%BD%D1%8B%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8), [Примеры NP-полных языков](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2)

### 🔴 11. Кооперативная и вытесняющая многозадачность. Процессы, потоки выполнения. Скалярные, супер-скалярные, векторные, SMT процессоры. Шины доступа к памяти и NUMA.

> Билеты: [3.]()
> Викиконспекты: [](), [](), [](), [](),

### 🔴 12. Потоки выполнения. Распределенные и параллельные системы, их отличия. Масштабируемость, закон Амдала.

> Билеты: [3.]()
> Викиконспекты: [Параллельное программирование](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5), [](), [](), [](),

### 🔴 13. Lock-free и wait-free программы. Задача о консенсусе, способы решения. Универсальные операции. Конструкция Херлихи для реализации lock-free и wait-free структур данных. Базовый формализм Лампорта.

> Билеты: [3.]()
> Викиконспекты: [Параллельное программирование](http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5), [](), [](), [](),

### 🔴 14. Планирование выполнения процессов. Алгоритмы (карусельные, учитывающие приоритеты, учитывающие взаимодействие с ресурсами). Real-time планирование. Планирование на нескольких вычислительных узлах, хищение и добровольная миграция процессов. Синдром инверсии приоритетов и методы его избежания.

> Билеты: [3.]()
> Викиконспекты: [](), [](), [](), [](),
> Есть в Таненбауме, но очень много

### 🔴 15. Планирование ввода-вывода. Алгоритмы (лифтовые, с очередями и задержками, предсказывающие, абсолютно честное планирование). Особенности для различных типов устройств (лента, HDD, SSD, виртуальные устройства в памяти). Синдром инверсии приоритетов при вводе-выводе, методы его избежания. Latency и производительность.

> Билеты: [3.]()
> Викиконспекты: [](), [](), [](), [](),
> Почти полность написано в книжке [Linux Kernel Development](http://www.iakovlev.org/zip/RobertLove.pdf), Robert Love, 13 глава во втором издании

### 🔴 16. Обучение с учителем. Задача классификации. Линейный перцептрон. Логистическая регрессия. Нейронные сети. Метод опорных векторов. Ядра. Использование ядер в методе опорных векторов.

> Билеты: [3.]()
> Викиконспекты: [](), [](), [](), [](),
> MachineLearning: [Обучение с учителем](http://www.machinelearning.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D1%83%D1%87%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%BC), [Классификация](http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%86%D0%B8%D1%8F), [Однослойный персептрон](http://www.machinelearning.ru/wiki/index.php?title=%D0%9E%D0%B4%D0%BD%D0%BE%D1%81%D0%BB%D0%BE%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BF%D0%B5%D1%80%D1%81%D0%B5%D0%BF%D1%82%D1%80%D0%BE%D0%BD), [Логистическая регрессия](http://www.machinelearning.ru/wiki/index.php?title=%D0%9B%D0%BE%D0%B3%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F), [Нейронная сеть](http://www.machinelearning.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%B5%D1%82%D1%8C), [Машина опорных векторов](http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%BE%D0%BF%D0%BE%D1%80%D0%BD%D1%8B%D1%85_%D0%B2%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BE%D0%B2)

### 🔴 17. Кластеризация. Метод k ближайших соседей. Метод k-средних. Иерархическая кластеризация. Графовая кластеризация. Спектральная кластеризация. FOREL.

> Билеты: [3.]()
> Викиконспекты: [](), [](), [](), [](),
> MachineLearning: [Кластеризация](http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F), [FOREL](http://www.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%9E%D0%A0%D0%95%D0%9B%D0%AC)
> Википедия: [Метод k-ближайших соседей](https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_k-%D0%B1%D0%BB%D0%B8%D0%B6%D0%B0%D0%B9%D1%88%D0%B8%D1%85_%D1%81%D0%BE%D1%81%D0%B5%D0%B4%D0%B5%D0%B9), [Метод k-средних](https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_k-%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D0%B8%D1%85)
> А также: [ВКР по кластеризации](https://nsu.ru/xmlui/bitstream/handle/nsu/463/Text_MachulskisSV.pdf)

### 🔴 18. Информация. Сжатие информации. Оптимальное сжатие информации. Алгоритмы Хаффмана, LZ*, LZW, арифметическое сжатие.

> Билеты: [3.]()
> Викиконспекты: [](), [](), [](), [](),

### 🔴 19. Справедливые комбинаторные игры. Ретроспективный анализ. Теория Шпрага-Гранди. Теория Смита.

> Билеты: [3.]()
> Викиконспекты: [](), [](), [](), [](),
> А также: [Статья на Arxiv](https://arxiv.org/pdf/math/0410026)

### 🔴 20. Антагонистические игры. Значение игры, ситуация равновесия. Смешанное расширение игры. Вполне смешанные игры.

> Билеты: [3.]()
> Викиконспекты: [](), [](), [](), [](),

### 🔴 21. Неантагонистические игры. Равновесие по Нэшу, Парето, Штакельбергу. Сильное равновесие. Совместные смешанные стратегии. Арбитражная схема Нэша.

> Билеты: [3.]()
> Викиконспекты: [](), [](), [](), [](),

### 🔴 22. Признаковое описание объектов, задачи машинного обучения и понятие переобучения. Минимизация эмпирического риска, алгоритмы линейной классификации. Вероятностная поставнока задачи машинного обучения и байесовская классификация.

> Билеты: [3.]()
> Викиконспекты: [](), [](), [](), [](),
> MachineLearning: [Признаковое описание](http://www.machinelearning.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D0%BA%D0%BE%D0%B2%D0%BE%D0%B5_%D0%BE%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B5), [Переобучение](http://www.machinelearning.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D0%B5%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5), [Минимизация эмпирического риска](http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%8D%D0%BC%D0%BF%D0%B8%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D1%80%D0%B8%D1%81%D0%BA%D0%B0), [Линейный классификатор](http://www.machinelearning.ru/wiki/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%82%D0%BE%D1%80), [Байесовский классификатор](http://www.machinelearning.ru/wiki/index.php?title=%D0%91%D0%B0%D0%B9%D0%B5%D1%81%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%82%D0%BE%D1%80)

## Программирование и вычислительная техника

### 🔴 1. Структурное программирование. Структурные конструкции. Теорема о структурировании.

> А также: [Доказательство теоремы о структурировании](https://cs.stackexchange.com/questions/14983/how-to-prove-the-structured-program-theorem)

### 🔴 2. Процедурное программирование. Процедуры и функции. Побочные эффекты. Вложенные функции и окружения. Непосредственная и косвенная рекурсия.

### 🔴 3. Инкапсуляция. Абстрактные типы данных. Модули. Полиморфизм. Параметрический и ad-hoc полиморфизм. Наследование. Принцип подстановки Лисков. Полиморфизм подтипов. Объектно-ориентированное программирование.

> А также: [Книга "Паттерны проектирования"](https://vk.com/doc25651989_437513397?hash=8cebc0bcb1835219e7&dl=f0168e88a9ca6abb24)

### 🔴 4. Метапрограммирование. Шаблоны и Generics. Частичная специализация шаблонов.

> Викиконспекты: [Generics](http://neerc.ifmo.ru/wiki/index.php?title=Generics), [Вопросы на экзамен по C++](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%82%D0%B0%D1%80%D1%8B%D0%B5_%D0%B2%D0%BE%D0%BF%D1%80%D0%BE%D1%81%D1%8B_%D0%BD%D0%B0_%D1%8D%D0%BA%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD_%D0%BF%D0%BE_C%2B%2B)

### 🔴 5. Процессоры общего назначения. Архитектуры CISC и RISC. Конвейер. Суперскалярность. Кэширование команд и данных.

### 🔴 6. Оперативная память. Способы адресации. Реальный и защищенный режим работы процессора. Виртуальная память. Страничная организация памяти. Файлы подкачки, алгоритмы выгрузки страниц.

### 🔴 7. Ядра операционных систем. Процессы пространства пользователя. Системные вызовы. Классификации типов ядер операционных систем. Экзоядра и их взгляд на ресурсы системы. Неклассические модели процессов (контекст исполнения + частично общие ресурсы, деление исполняемого кода на "прелюдию" и "тело").

> ...
> А также: [План курса Яна Малаховски](https://oxij.org/activity/itmo/os/plan/)

### 🔴 8. Форматы исполняемых файлов (a.out, COFF, PE, ELF). ABI. Компиляция, линковка, динамическая загрузка. Типы линковки. Методы релокации кода. Ленивая динамическая загрузка.

> ...
> А также: [Конспект Яна Малаховски](https://github.com/oxij/unix-notes-ru/blob/master/compiled/main.pdf)

### 🔴 9. Интерфейс пользователя. Интерфейсы командной строки. Текстовые интерфейсы. Графические интерфейсы (WIMP-интерфейсы), оконные менеджеры. Реализация интерфейсов пользователя.

### 🔴 10. Машинные языки. Структура инструкций. Типы инструкций. Языки низкого уровня. Ассемблеры и их применение.

### 🔴 11. Шины передачи данных. Параллельные и последовательные шины. Шины ISA, PCI, PCI-Express, USB. Управление внешними устройствами.

### 🔴 12. Типы баз данных. Реляционные БД. Нормальные формы РБД. Язык SQL.

### 🔴 13. Реализация реляционных СУБД. Индексы, применение индексов. Транзакции, свойства транзакций. Блокировки, типы блокировок.

> kgeorgiy: [Хранение данных и индексирование](http://www.kgeorgiy.info/courses/dbms/slides/indexing.xhtml#(1)), [Транзакции](http://www.kgeorgiy.info/courses/dbms/slides/transactions.xhtml#(1))

### 🔴 14. Автоматное программирование. Отличие от абстрактных автоматов. Связь с машиной Тьюринга.

### 🔴 15. Файловые системы, их типы. Реализация файловых систем, структуры данных. Журналирование, log stuctured, copy-on-write, транзакции, indirect block allocation, extent allocation, delayed allocation. Сетевые и распределенные ФС. Примеры: FAT, NTFS, tmpfs, Ext*, XFS, ReiserFS, ZFS, Btrfs. Особенности для различных типов устройств (HDD, SSD, виртуальные устройства в памяти). RAID, логическое управление томами. Device pool, multiple roots.

### 🔴 16. Компьютерные сети. Модель OSI. Устройства коммутации и маршрутизации. Протоколы Ethernet, IP, TCP, UDP.

### 🔴 17. Разработка через тестирование. Типичный цикл разработки через тестирование. Преимущества и недостатки разработки через тестирование. Инструменты, поддерживающие разработку через тестирование.

### 🔴 18. Шаблоны проектирования, их применение. Классификация шаблонов проектирования. Примеры шаблонов проектирования.

### 🔴 19. Индексирование документов. Предварительная обработка и морфологический анализ. Структура индекса, его построение и обновление. Сжатые индексы. Распределенное индексирование.

### 🔴 20. Ранжирование документов. Метаинформация и зонирование документов. Tf-idf и его модификации. Векторные пространства и поиск в них. Модели языка и их применение.