Вопросы к коллоквиуму по курсу "Информатика"

111--113 гр., осенний семестр 2002 г.

  1. Равнодоступная адресная машина. Алгоритм. Массовая задача. Время работы алгоритма и используемая память.
  2. Основные структуры данных (массив, файл, очередь, стек, список, хеш-таблица, skip-list, дерево поиска) и операции над ними (без доказательств).
  3. Рекурсивные процедуры. Реализация рекурсии в компьютере. Динамическое программирование (на примере задачи о рюкзаке).
  4. HeapSort.
  5. QuickSort.
  6. Поиск k-го элемента в массиве.
  7. Сортировка на четырех лентах.
  8. Лексикографическая сортировка.
  9. АВЛ-деревья. Реализация операций над ними.
  10. 2-3-4-деревья. Реализация операций над ними. B-деревья, B+-деревья.
  11. Способы представления графа в машине.
  12. Поиск в глубину.
  13. Топологическая сортировка.
  14. Разбиение графа на компоненты сильной связности.
  15. Построение минимального остовного дерева.
  16. Нахождение кратчайших путей: алгоритмы Дейкстры и Беллмана-Форда.
  17. Полилогарифмический по памяти алгоритм для определения длины кратчайшего пути.
  18. Нахождение кратчайших путей между всеми парами вершин: алгоритм Флойда-Уоршолла.
  19. Изоморфизм деревьев (без алгоритма лексикографической сортировки).
  20. Задача о максимальном потоке. Лемма о максимальном потоке и минимальном сечении. Общая схема алгоритма Форда-Фалкерсона.
  21. Варианты реализации алгоритма Форда-Фалкерсона: случай целочисленных пропускных способностей; алгоритм Эдмондса-Карпа.
  22. Применение алгоритма Форда-Фалкерсона для нахождения максимального паросочетания в двудольном графе.
  23. Рисование планарного графа.
  24. Сложность рекурсивных алгоритмов.
  25. Алгоритм Штрассена для умножения матриц. Умножение булевых матриц.
  26. Вероятностная проверка умножения матриц.
  27. Нахождение пары ближайших точек на плоскости.
  28. Нахождение пары пересекающихся отрезков на плоскости.
  29. Построение выпуклой оболочки на плоскости.
Back