Вопросы к устному зачёту

Процедура приёма зачёта

Оценка по информатике ставится в результате устного ответа на дифференцированном зачёте. Преподаватель учебной группы имеет право в одной учебной группе поставить одному студенту "автомат".

Сдача происходит по билетам. В билете содержится два вопроса из основного списка и задача. На подготовку студенту отводится не более 20 минут. Преподаватель слушает ответы на вопросы в билете, а также может задать дополнительные вопросы, как из основного списка, так и любых других по программе курса.

Использование на зачёте любых посторонних цифровых и бумажных носителей информации студентом недопустимо! Допустимы только ручка, чистая бумага.

Список вопросов

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

Доп. вопросы

  1. Ассинхронное программирование
  2. Многопоточное программирование, библиотека threading
  3. Параллельное программирование, библиотека multiprocessing