Предварительный список вопросов ко второму коллоквиуму по курсу "Информатика" (1 курс потока МО ЭВМ, весна 2006 г.)

1.	Базис Фурье пространства комплекснозначных функций, заданных на
конечном множестве. Алгоритм быстрого преобразования Фурье. Применение к
умножению многочленов.
2.	Целочисленное преобразование Фурье. Теорема о биективности
преобразования. Теорема о вычислении свертки. 
3.	Алгоритм Шёнхаге-Штрассена быстрого умножения чисел и время его
работы.

4.	Нахождение пары пересекающихся отрезков на плоскости среди n
заданных методом "заметающей прямой".
5.	Выпуклая оболочка. Нижняя оценка на выпуклую оболочку. Алгоритм
Грехема.
6.	Представление графа в машине. Поиск в глубину и ширину. Нумерации
в поиске в глубину, лемма о скобочной структуре.
7.	Топологическая сортировка. N-нумерация (нумерация, обратная к
времени выхода из рассмотрения вершины в поиске в глубину).
8.	Построение компонент сильной связности.  
9.	Потоки в графах. Поток через разрез. Теорема Форда-Фалкерсона. 
10.	Общий метод Форда-Фалкерсона для поиска максимального потока.
Случай целочисленных пропускных способностей. Алгоритм Эдмондса-Карпа. 
11.	Метод проталкивания предпотока. 
12.	Применения теоремы Форда-Фалкерсона: максимальное паросочетание
в двудольном графе, реберная теорема Менгера. 
13.	Изоморфизм деревьев (с выделенным корнем). 
14.	Минимальное остовное дерево. Корректность общей схемы
алгоритмов. Алгоритмы Прима и Краскала (без оценки на время работы),
алгоритм Борувки (с оценкой).

15.	Алгоритмы Дейкстры и Форда-Беллмана. 
16.	Быстрые реализации алгоритма Дейкстры с помощью кучи. Понятие
учетной стоимости операции.
17.	Алгоритм Флойда-Уоршолла.
18.	Задача маршрутизации. Протокол вектора расстояний. Методы
предотвращения образования ложных маршрутов. Протокол состояний каналов.
19.	Поиск длин кратчайших путей с помощью матричного умножения.
20.	Полилогарифмический по памяти алгоритм поиска кратчайшего пути.

21.	Параллельные алгоритмы. Классы параллельных алгоритмов.
Принцип Брента. Параллельный алгоритм для достижимости в графе.
22.	Параллельные алгоритмы для сложения и умножения целых чисел.
23.	Параллельный алгоритм для вычисления определителя.
24.	Приближенные алгоритмы.  Приближенный алгоритм для задачи
о рюкзаке.
25.	Приближенные алгоритмы для задачи о покрытии множествами и
наименьшей общей надпоследовательности.