====== Регламент экзамена ======

<WRAP center round info 60%>
**[[https://docs.google.com/document/d/1B4kddOn0Z4fqdMen5JIITkqIrZhbm4mwwlAKAKCMSF4/edit?tab=t.0|FAQ об экзамене]]**
</WRAP>

===== Система оценивания =====
<WRAP left round box 80%>
Полученные в рамках семестра баллы за компоненты курса, описанные в рейтинговой системе, конвертируется в оценку за экзамен по следующим правилам:
<WRAP left round box 50%>
Таблица 1. Границы баллов для перевода в экзаменационную оценку.
^ Оценка             ^ Граница баллов  ^
| Удовлетворительно  | >=55            |
| Хорошо             | >=75            |
| Отлично            | >=95            |
</WRAP>

<WRAP left round important 80%>
==== Подтверждение оценки ====
Любая оценка за экзамен, получаемая по рейтингу, кроме "Неудовлетворительно", требует подтверждения на экзамене.
  * **Отказ от подтверждения оценки** соответствует **отказу от оценки по рейтингу**, т.е. решение полного билета.
</WRAP>

<WRAP left round info 80%>
==== Повышение оценки ====
Если студента не удовлетворяет оценка по итогам работы в семестре (на основании баллов), он может отказаться от нее и сдать экзамен
  * накопленная за семестр оценка **теряется без возможности отката**
  * экзамен представляет из себя полный экзаменационный билет по темам дисциплины

</WRAP>

</WRAP>


===== Допсессии, комиссии, дни качества и прочее =====
==== Допсессия и комиссия ====
Для студентов, **несдавших экзамен в рамках основной сессии** (т.е. получивших "Неудовлетворительно" при сдаче экзамена):
  * накопленная за семестр **оценка обнуляется** (поскольку студент не смог её подтвердить на экзамене)
  * экзамен проводится **по правилам полного экзамена**

Для студентов, недопущенных до экзамена (например, несдача курсовой работы) или пропустивших экзамен **по уважительной причине**:
  * накопленная за семестр **оценка сохранятся**
  * экзамен проводится по стандартным правилам:
      * все положительные оценки требуют подтверждения путём решения упрощенного экзаменационного билета
      * в случае оценки "Неудовлетворительно" по рейтингу или повышения оценки - решение полного экзаменационного билета

==== День качества ====
=== Курсовая работа ===
Повышение оценки за курсовую происходит путём выполнения нового варианта курсовой на соответствующую оценку.
  * Для получения нового варианта необходимо написать своему преподавателю.

=== Экзамен ===
Повышение оценки в рамках дня качества соответствует правилам, описанным в разделе [[courses:algorithms_structures:exam#повышение_оценки|"Повышение оценки"]]


===== Экзаменационные билеты =====
<WRAP left round box 80%>
В данном разделе описаны виды и составлящие экзаменационных билетов. Примеры билетов приведены в конце страницы.

<WRAP left round important 80%>
Каждый компонент билета выполняется студентов **самостоятельно без использования каких-либо сторонних ресурсов и материалов**.
</WRAP>

==== Упрощенный билет ====
Подтверждение оценок на экзамене предполагает упрощенный экзаминационный билет, состоящий из теоретического минимума и практических задач, и беседу с преподавателем.
  * Оценивание решений теор. минимума и задач проводится до или во время беседы с преподавателем.
  * Беседа с преподавателем не даёт возможности исправить/изменить решения практических задач или получить время на доработку

=== Теоретический минимум ===
  * является **первым и обязательным этапом экзамена** для подтверждения любой оценки
  * представляет из себя тест из 20 вопросов (с выбором ответа или свободным ответом)
  * выполняется в течение 15 минут

<WRAP left round important 80%>
Если результат студента по теоретическому минимуму меньше 50% - **оценка за экзамен снижается на 1 балл**
  * При подтверждении оценки "Удовлетворительно" в случае несдачи теор. минимума студент получает "Неудовлетворительно" 
</WRAP>

=== Практические задачи ===
  * Подтверждение оценки "Удовлетворительно" - решение одной практической задачи 
  * Подтверждение оценки "Хорошо" - решение двух практических задач
  * Подтверждение оценки "Отлично" - решение двух практических задач

<WRAP left round important 80%>
**Подтверждение более высокой оценки автоматически включает задачи более низких оценок.**
Таким образом, для подтверждения оценки "Отлично" требуется решить 5 задач, для "Хорошо" - 3 задачи.
</WRAP>

<WRAP left round info 80%>
**Время, отведенное на решение практических задач, зависит от подтверждаемой оценки** (т.е. от кол-ва задач) - 30/60/90 минут для оценок "Удовлетворительно"/"Хорошо"/"Отлично" соответственно.
</WRAP>

==== Полный билет ====
Полный билет содержит
  * теоретический анализ
  * расширенный теоретический минимум (30 вопросов со свободным ответом на 30 минут)
      * //Примечание от 14.01: вопросы со свободным ответом заменены на утверждения, которые нужно отметить как верные / неверные - время на компоненту снижено до 25 минут.//  
  * практические задачи - по 2 задачи на каждую оценку (Удовлетворительно/Хорошо/Отлично)
      * более высокая оценка автоматически включает задачи более низких оценок (т.е. на оценку "Отлично" нужно решить 6 задач, на "Хорошо" - 4 задачи)
      * на решение всех задач (независимо от желаемой оценки) отводится 90 минут

=== Теоретический анализ ===
За **два дня** до экзамена* студенту, изъявившему желание писать полный экзамен, случайным образом выдаются **3 вопроса** по теоретическому материалу дисциплины:
  * Кол-во вопросов может быть снижено до 2, если студент не претендует на оценку выше "Удовлетворительно"
      * На оценку "Хорошо" или "Отлично" количество вопросов = 3
  * Студент самостоятельно готовится по данным вопросам, чтобы **на экзамене** предоставить **максимально полные ответы** по ним
      * На экзамене для написания ответов отводится 40 минут
  * Если на экзамене дано корректных ответов менее, чем на 1.5 вопроса - ставится оценка **"Неудовлетворительно"**.
      * В остальных случах студент допускается до следующих этапов экзамена.
      * Результаты данного этапа могут (и будут) влиять на итоговую оценку за экзамен в спорных и иных случаях.

Полный список вопросов теор. анализа приведен на странице [[.:exam:theor_analysis|]].

=== Теоретический минимум и практические задачи ===
Аналогично разделу "Подтверждение оценки", отличие только в количестве вопросов / задач (описаны ранее).
</WRAP>

===== Пример компонентов экзаменационного билета =====
<WRAP left round box 80%>
==== Теоретический анализ ====

  - (вопрос №1) Сделайте сравнительный анализ O и Θ-нотаций, включая их формальные математические определения.
      * Объясните, почему в практике программирования и при проектировании систем наибольшее распространение получила O-нотация, несмотря на её «пессимистичность».
      * Проиллюстрируйте свой ответ примером алгоритма, для которого O, Ω и Θ-оценки различны, и объясните, какие практические выводы для разработчика из этого следуют.
  - (вопрос №2) Проведите детальный сравнительный анализ временной и пространственной сложности для односвязных, двусвязных и развернутых списков.
      * Для каждой структуры данных: постройте таблицу сложности операций (доступ по индексу, поиск, вставка/удаление в начало/середину/конец) с указанием лучшего, худшего и среднего случаев. 
      * На основе анализа предложите оптимальную структуру данных для каждого из сценариев:
          * Частые случайные доступы по индексу, последовательный обход
          * Непредсказуемый паттерн доступа с преобладанием операций в середине структуры.
  - (вопрос №3) Развернутый связный список представляет собой гибридную структуру, сочетающую преимущества массивов и связных списков. Дайте строгое математическое доказательство теоремы об оптимальном размере блока k = Θ(√n), включая анализ функции f(k) = n/k + k и нахождение её минимума.
      * Объясните, почему на практике выбирают фиксированные значения k = 16-64, а не вычисляют √n динамически. Какие архитектурные особенности современных процессоров влияют на этот выбор?
      * Предложите модификацию развернутого списка, которая сохраняла бы асимптотику O(√n) для операций, но улучшала производительность для паттерна доступа "частое добавление в начало". Обоснуйте эффективность вашего решения.
  - (вопрос №4) На примере сортировки Шелла и TimSort
      * представьте анализ сложности сортировки Шелла, включая: формальную запись теоремы Ханта о среднем числе инверсий в h-упорядоченной перестановке.
      * для TimSort дайте строгое обоснование выбора параметра minrun и его оптимизации в диапазоне [32, 64]. Алгоритма балансировки слияния подмассивов с поддержанием инвариантов стека.
      * Сравните практическую эффективность этих алгоритмов для различных типов данных
  - (вопрос №5) Проведите сравнительный анализ трех классических жадных алгоритмов
      * Для дробного рюкзака докажите оптимальность стратегии удельной стоимости, используя выпуклость целевой функции и линейность ограничений
      * Для кодирования Хаффмана докажите оптимальность через индукцию по размеру алфавита, обосновав, что объединение двух наименее вероятных символов сохраняет оптимальность.


==== Теоретический минимум ====
  * Какова временная сложность поиска элемента в отсортированном массиве с использованием двоичного поиска?
  * Какую структуру данных лучше всего использовать для реализации очереди и почему?
  * Приведите примеры устойчивых сортировок?
  * Для какого случая хеш-таблицы эффективны?
  * Что означает "балансировка" в АВЛ-дереве?
  * Какова разница между обходом дерева в глубину и в ширину? Приведите пример для объяснения.
  * Что такое хеш-функция? Каковы её основные свойства?
  * Какие проблемы могут возникнуть при использовании хеш-функций? Опишите способы их решения.
  * Какой из алгоритмов сортировки основан на подходе "Разделяй и властвуй"?
  * Что происходит при большом повороте в АВЛ-дереве?
  * Что представляет собой стек?
  * Какая из структур данных подходит для реализации алгоритма обхода дерева в ширину?
  * Приведите примеры трёх жадных алгоритмов и их критерий жадности
  * Опишите основные свойста красно-черного дерева
  * Какую временную сложность имеет операция вставки в куче?
  * Какие структуры данных не поддерживают произвольный доступ к элементам?
  * Какие преимущества имеет использование самобалансирующихся деревьев? Приведите примеры применения.
  * Опишите алгоритм работы сортировки Timsort. В чем его преимущества по сравнению с другими сортировками?

==== Практические задачи ====
Пример "билета" с набором задач на каждую оценки (более высокая оценка включает задачи более низких оценок).

Задачи выполняются строго **последовательно**.

=== Удовлетворительно ===
  - Реализуйте класс бинарного дерева Tree с использованием класса узла Node и функцию для нахождения путей от корня до листа длины в диапазоне [a, b], за один обход дерева. Проверьте работу функции на различных конфигурациях деревьев. Обоснуйте и подтвердите сложность алгоритма (график теор. и практич. времени)

=== Хорошо ===
  - Проверьте за один проход, является ли бинарное дерево 1) линейным списком с диапазоном значений [c, d]. 2) АВЛ-деревом высотой больше A и меньше B.	
  - Реализуйте модифицированный односвязный и двусвязный списки, позволяющие за О(1) получить минимальное/максимальное значение в списке, с сохранением асимптотики операций. Подтвердите сложность операций, сравнив с простыми списками

=== Отлично ===
  - Реализуйте два алгоритма сортировки: слиянием и вставками. Сравните их производительность, а также производительность встроенной сортировки, на случайных, почти отсортированных и обратно отсортированных массивах.
  - Реализуйте хеш-таблицу с методом цепочек, вместо цепочек - любой класс с методами add/remove/find (по умолчанию - односвязный список). Подберите различные конфигурации данных / хеш-функции и сравните скорость работы с использованием цепочки 1) по умолчанию 2) бинарного дерева поиска
</WRAP>