====== Вопросы теоретического анализа ======
В разделе приведены вопросы, используемые на полном экзамене.
При распределении вопросов студент получает номера вопросов из данных списков.

===== Блок "Удовлетворительно" =====
  - Дайте формальное математическое определение O- и Ω-нотаций.
  - Дайте формальное математическое определение O- и Θ-нотаций.
  - Дайте формальное математическое определение Θ- и Ω-нотаций.
  - Объясните разницу между худшим случаем и лучшим случаем (O- и Ω-нотация) на примере алгоритма быстрой сортировки.
  - Объясните разницу между средним случаем и лучшим случаем (Θ- и Ω-нотация) на примере алгоритма сортировки вставками.
  - В чем разница между абстрактным типом данных и структурой данных? Приведите пример для очереди и деки.
  - Перечислите преимущества и недостатки односвязного списка по сравнению со статическим массивом.
  - Перечислите преимущества и недостатки двунаправленного списка по сравнению с динамическим массивом.
  - Обоснуйте, почему вставка в середину связного списка формально занимает O(1), а на практике работает гораздо медленнее?
  - Опишите алгоритм сортировки подсчетом. В каких случаях она эффективна?
  - Почему сортировка пузырьком считается неэффективной? Назовите ее сложность.
  - Опишите алгоритм BFS (поиск в ширину). Какую структуру данных он использует и почему?
  - Опишите алгоритм DFS (поиск в глубину). Какую структуру данных он использует и почему?
  - Опишите алгоритм Дейкстры с точки зрения жадных алгоритмов.
  - Опишите алгоритм Дейкстры с использованием матрицы смежности.
  - Что такое хэш-фукнция и коллизия?
  - Что такое коллизия в хеш-таблице и какие есть способа борьбы с ней?
  - Что такое коэффициент заполнения, где и как он применяется? Для чего нужно перехеширование?
  - Перечислите преимущества и недостатки сбалансированного дерево поиска по сравнению с несбалансированным?
  - Что такое высота дерева? Докажите оценку высоты АВЛ и красно-черного дерева из n элементов.

===== Блок "Хорошо / Отлично" =====
  - Приведите пример алгоритма, где O, Θ и Ω-оценки различаются. Объясните, почему на практике важнее знать О-оценку, хотя она «пессимистична».
  - Объясните идею метода потенциалов для амортизационного анализа на примере динамического массива (при переполнении массив удваивается).
  - Сравните методы бухгалтерского учета и агрегирования. Какой из них понятнее для программиста и почему?
  - Проанализируйте, как выбор реализации очереди на массиве (кольцевой буфер) против реализации на связном списке влияет на кэш-эффективность и сложность операций.
  - Почему в развернутом связном списке размер блока (k) выбирают фиксированным (16-64), а не вычисляют как √n?
  - Для сценария «частые вставки/удаления в начале и последовательный обход» выберите оптимальную структуру из: массив, односвязный список, двусвязный список, развернутый список. Обоснуйте.
  - Для сценария «частые случайные доступы по индексу, редкие модификации» выберите оптимальную структуру из: массив, односвязный список, двусвязный список, развернутый список. Обоснуйте.
  - Для сценария «непредсказуемый паттерн доступа с преобладанием операций в середине структуры» выберите оптимальную структуру из: массив, односвязный список, двусвязный список, развернутый список. Обоснуйте.
  - Опишите идею XOR-связного списка, почему он не получил широкого распространения, несмотря на экономию памяти?
  - Объясните влияние выбора последовательности шагов (последовательность Шелла, последовательность Седжвика) на сложность сортировки Шелла.
  - Докажите, что TimSort работает за O(n log n) в худшем случае. Для чего нужен режим «галопа»?
  - Докажите корректность LSD-сортировки методом математической индукции.
  - Почему Radix sort может работать быстрее, чем O(n log n), и не противоречит ли это теореме о нижней оценке для сортировок сравнениями?
  - Проведите амортизационный анализ методом бухгалтерского учета операции вставки и удаление в хеш-таблицу с цепочками при динамическом перехешировании.
  - Докажите, что BFS гарантированно находит кратчайший путь в невзвешенном графе.
  - Сравните временную сложность BFS для графа, представленного матрицей смежности и списками смежности. Почему списки предпочтительнее?
  - Обоснуйте выбор между реализацией алгоритма Дейкстры на массиве O(n²) и на двоичной куче O((n+m)log n).
  - Докажите теорему о том, что высота АВЛ-дерева не превышает 1.44 * log2(n).
  - Сравните АВЛ и красно-черные деревья: какое из них обеспечивает более жесткую балансировку, а какое — более быстрые вставки/удаления и почему?
  - Обоснуйте преимущества B+-деревьев (классические B-деревья) для баз данных, особенно в контексте блочного ввода-вывода.
  - Как выбор параметра t (порядка/минимальной степени) B-дерева влияет на производительность в системах с жесткими дисками (HDD/SSD)?
  - Для структуры данных Rope докажите, что высота дерева остается O(log n) при использовании АВЛ-балансировки.


==== Старые вопросы (не актуально)====
=== Вопрос №1 ===
Сделайте сравнительный анализ O, Ω и Θ-нотаций, включая их формальные математические определения.
Объясните, почему в практике программирования и при проектировании систем наибольшее распространение получила O-нотация, несмотря на её «пессимистичность».
Проиллюстрируйте свой ответ примером алгоритма, для которого O, Ω и Θ-оценки различны, и объясните, какие практические выводы для разработчика из этого следуют.

=== Вопрос №2 ===
Сравните три основных метода амортизационного анализа (агрегирования, бухгалтерский, потенциалов) на примере одной и той же структуры данных (на усмотрение студента).
Какой из методов, по вашему мнению, является наиболее универсальным и мощным инструментом доказательства, а какой — наиболее интуитивно понятным для программиста? Обоснуйте свою точку зрения.

=== Вопрос №3 ===
На примере стека, очереди и дека раскройте практическое различие между абстрактным типом данных (АТД) и конкретной структурой данных. Почему связный список считается конкретной структурой данных, а не АТД? 
Проанализируйте, как выбор между реализацией на массиве (кольцевом буфере) и на связном списке влияет на: Амортизированную сложность операций, эффективность использования памяти и локальность данных и кэш-эффективность.

=== Вопрос №4 ===
Развернутый связный список представляет собой гибридную структуру, сочетающую преимущества массивов и связных списков. Объясните, почему на практике выбирают фиксированные значения k = 16-64, а не вычисляют √n динамически.
Какие архитектурные особенности современных процессоров влияют на этот выбор? Предложите модификацию развернутого списка, которая сохраняла бы асимптотику O(√n) для операций, но улучшала производительность для паттерна доступа "частое добавление в начало". Обоснуйте эффективность вашего решения.

=== Вопрос №5 ===
Проведите детальный сравнительный анализ временной и пространственной сложности для массивов, односвязных, двусвязных списков и развернутых списков. Для каждой структуры данных: Постройте таблицу сложности операций (доступ по индексу, поиск, вставка/удаление в начало/середину/конец) с указанием лучшего, худшего и среднего случаев. 
На основе анализа предложите оптимальную структуру данных для каждого из сценариев: а) Частые случайные доступы по индексу, редкие модификации б) Частые вставки/удаления в начале, последовательный обход в) Непредсказуемый паттерн доступа с преобладанием операций в середине структуры. Для сценария (в) обоснуйте, может ли XOR-связный список быть практичной альтернативой, учитывая его особенности и ограничения.

=== Вопрос №6 ===
На примере сортировки Шелла и TimSort представьте анализ сложности сортировки Шелла. Анализ оптимальных последовательностей смещений и их асимптотической сложности. Объяснение, почему последовательность Шелла дает O(n²) в худшем случае. 
Для TimSort дайте строгое обоснование выбора параметра minrun и его оптимизации в диапазоне [32, 64]. Алгоритма балансировки слияния подмассивов с поддержанием инвариантов стека. Доказательства сложности O(n log n) с учетом режима галопа. Сравните практическую эффективность этих алгоритмов для различных типов данных

=== Вопрос №7 ===
Для несравнительных методов сортировки детально опишите алгоритм устойчивой сортировки подсчетом для сложных объектов, включая преобразование в префиксные суммы.
Докажите корректность LSD-сортировки методом индукции по разрядам. Проанализируйте, при каких условиях цифровая сортировка превосходит сравнениями-based алгоритмы(comparison-based sorting), и почему это не противоречит теореме о нижней оценке

=== Вопрос №8 ===
Проведите амортизационный анализ операции добавления в хеш-таблицу с цепочками при динамическом перехешировании: Объясните, почему порог перехеширования выбран как 4n/3
Докажите, что амортизированная стоимость операции составляет O(1), используя метод бухгалтерского учета.

=== Вопрос №9 ===
Проведите сравнительный анализ алгоритмов DFS и BFS, включая математическую модель работы каждого алгоритма. Анализ временной и пространственной сложности для различных представлений графа (матрица смежности vs списки смежности).
Объясните, почему DFS естественным образом использует стек, а BFS — очередь. Объясните, почему BFS гарантированно находит кратчайший путь в невзвешенных графах.

=== Вопрос №10 ===
Дайте обоснование корректности алгоритма Дейкстры, доказательство того, что алгоритм не работает с отрицательными весами (приведите контрпример).
Докажите, что наивная реализация с массивом имеет сложность O(n² + m) Обоснуйте, почему использование двоичной кучи дает O((n + m) log n) 

=== Вопрос №11 ===
Проведите детальный сравнительный анализ АВЛ-деревьев, красно-черных деревьев, B-деревьев, включая формальное доказательство высоты для каждого типа деревьев (теорема о высоте АВЛ-дерева, лемма о чёрной высоте для красно-черных, оценка высоты B-дерева).
Математический анализ сложности операций вставки, удаления и поиска с учётом различных сценариев балансировки.
Доказательство корректности операций балансировки (вращения в АВЛ, перекрашивания в красно-черных, разбиения/слияния в B-деревьях) 

=== Вопрос №12 ===
Для структуры данных Rope докажите, что высота дерева остается O(log n) при использовании АВЛ-балансировки.
Проведите амортизационный анализ операций конкатенации и разделения с учётом перебалансировки.
Предложите и обоснуйте модификацию Rope, которая сохраняет персистентность при сохранении асимптотики O(log n)

=== Вопрос №13 ===
Для B-деревьев дайте строгое обоснование операций докажите, что инварианты B-дерева сохраняются при разбиении узлов и слиянии.
Проанализируйте, как выбор параметра t влияет на производительность в системах с иерархической памятью.
Обоснуйте преимущества B+-деревьев перед классическими B-деревьями для систем управления базами данных.