Список вопросов для подготовки к экзамену¶

На экзамене вы получаете билет с двумя вопросами. Дополнительные вопросы — на усмотрение экзаменатора.

Первые вопросы:¶

1. Принципы устройства булевых (двоичных) ЭВМ.
2. Возможности интроспекции в языке Python.
3. Поддержка различных систем счисления в языке Python.
4. Кольца вычетов и целочисленная арифметика в Python.
5. Логический тип. Логические и арифметико-логические операции. Ленивые операторы.
6. Вложенное и каскадное ветвление.
7. Цикл while и операторы управления ходом цикла.
8. Цикл for. Поддержка итерируемых объектов в Python помимо цикла for.
9. Конструктор и методы класса list. Ссылочная модель данных в Python и списки.
10. List comprehensions. Вложенная генерация объектов-контейнеров.
11. Варианты определения и использования функций. Функции как первосортные объекты в Python.
12. Стандартные функции Python для редукции итерируемых объектов.

Вторые, алгоритмические вопросы:¶

1. Примитивный тест простоты и решето Эратосфена. Что экономнее и когда?
2. Алгоритм Евклида. Факторизация числа. Сложность по времени вычислений.
3. Однопроходные алгоритмы редукции последовательности. Инициализация переменных и итерирование.
4. Постановка задачи сортировки. Когда задача некорректна. Сортировка обезьяны и сортировка дурака.
5. Три квадратичные универсальные сортировки. Сравнить и выбрать лучшую, обосновать свой выбор.
6. Алгоритм слияния упорядоченных списков. Сортировка слиянием. Чем хороша и чем плоха.
7. Алгоритм сортировки Тони Хоара. Чем хороша и чем плоха.
8. Частотный анализ и сортировка подсчётом. Алгоритмическая сложность и применимость.
9. Поразрядная сортировка. Алгоритмическая сложность и применимость.
10. Двоичный поиск в массиве/списке. Алгоритмическая сложность и применимость.
11. Рекурсия. Крайний и рекуррентный случай, ход рекурсии. Генерация комбинаторных объектов.
12. Динамичное программирование сверху. Чистые функции. Кеширование.
13. Динамичное программирование снизу. Задачи про кузнечика на числовой прямой.
14. Максимальная сумма подотрезка числовой последовательности. Однопроходный алгоритм.
15. Наидлиннейшая возрастающая подпоследовательность.
16. Длина набольшей по длине общей подпоследовательности двух последовательностей.
17. Алгоритм укладки рюкзака с дискретными массами предметов.
18. Расстояние Левенштейна. Алгоритм поиска.
19. Пи-функция строки. Алгоритм Кнута-Морриса-Пратта.
20. Очереди FIFO и LIFO. Корректность скобочного выражения с несколькими видами скобок.

Сложные дополнительные вопросы:¶

1. Реализовать перевод положительных чисел из 37-ричной системы счисления в 10-ю.
2. Реализовать без контейнеров поиск индекса первого среди равных максимальному чисел в последовательности.
3. Однопроходная реализация поиска среднеквадратического отклонения выборки.
4. С использованием О(1) дополнительной памяти вернуть список A с удаленными из него элементами, равными К.
5. Что такое устойчивость алгоритма сортировки? Пример неустойчивой сортировки. Можно ли сделать её устойчивой?
6. Реализовать восстановление самой дешёвой траектории для задачи про кузнечика на прямой с платным посещением точек.
7. Как реализовать нестандартную редукцию встроенными средствами Python?
8. Длина набольшей по длине общей подпоследовательности трёх последовательностей.
9. Восстановление траектории редакционных изменений для расстояния Левенштейна.
10. Описать вычисление выражения в обратной польской нотации.