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

===== Система оценивания =====
<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 минут

Темы вопросов: структуры данных и АТД, сортировки, хэш-таблицы, деревья (в том числе БТД и Rope), жадные алгоритмы.

<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 минут

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

За **два дня** до экзамена* студенту, изъявившему желание писать полный экзамен, случайным образом выдаются **6 вопросов** по теоретическому материалу дисциплины: 3 вопроса из блока "Удовлетворительно" и 3 вопроса из блока "Хорошо / Отлично"

  * Студент самостоятельно готовится по данным вопросам, чтобы **на экзамене** предоставить **максимально полные ответы** по ним
      * На экзамене для написания ответов отводится 60 минут
  * Вопросы блока "Удовлетворительно"
      * **Обязательны для написания**
      * Оцениваются бинарно - 0/1 (максимум 3 балла за весь блок)
          * Если дан неполный ответ или ответ с ошибками, он считается неверным и оценивается как 0
      * Если за вопросы данного блока получено
          * <2 баллов - ставится оценка **"Неудовлетворительно"**.
          * >=2 баллов - студент может претендовать на оценку не выше "Удовлетворительно".
  * Вопросы блока "Хорошо/Отлично"
      * Обязательны для написания только если студент претендует на оценку "Хорошо" или "Отлично"
      * Оцениваются бинарно - 0/1 (максимум 3 балла за весь блок)
          * Если дан неполный ответ или ответ с ошибками, он считается неверным и оценивается как 0
      * Если за вопросы данного блока получено
          * <2 баллов - блок считается несданным, а оценка за экзамен ограничивается по правилам блока "Удовлетворительно"
          * >=2 баллов - блок считается сданным, ограничений на оценку за экзамен нет.

Результаты данного этапа могут (и будут) влиять на итоговую оценку за экзамен в спорных и иных случаях.

//Краткая сводка//:
  * если студент претендует на оценку "Удовлетворительно" - ему достаточно написать не менее 2х вопросов из блока "Удовлетворительно"
  * если студент претендует на оценку "Хорошо / Отлично" - ему требуется написать блок "Удовлетворительно" И блок "Хорошо / Отлично"
  * если студент не сдает блок "Удовлетворительно" - ставится оценка "Неудовлетворительно" (вне зависимости от ответов на следующий блок вопросов) 


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

===== Пример компонентов экзаменационного билета =====
<WRAP left round box 80%>
==== Теоретический анализ ====
Полный список вопросов приведен на странице [[.:exam:theor_analysis|]].

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

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

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

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

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

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