Алгоритмы и структуры данных, семинар группы 158-2 — различия между версиями

Версия 13:53, 14 января 2016

Правила игры

В основном все общение будет происходить с семинаристом курса, однако к проверке работы также будет привлекаться и учебный ассистент. Если у студент есть некоторые разногласия с ассистентом, то он всегда может обратиться к семинаристу, чтобы разрешить конфликт.

Семинарист: Симагин Денис, simagin.mail@yandex.ru
Ассистент: Владимир Гончаров, dev.zelta@gmail.com

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

Структура курса

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

Семинары

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

Упражнения стоит присылать на почту семинаристу, при этом тема письма должна строго удовлетворять формату. К примеру, меня зовут Симагин Денис и я хочу отправить задачу с первого семинар, тогда заголовок письма должен иметь вид

   A12.01: Разворот списка - Симагин Денис

Формула оценки

Оценка за семинары вычисляется следующим образом

   OСеминар = Сн·N/Nmax

   N – количество набранных плюсов
   Nmax – максимальное количество плюсов
   Сн – нормирующий коэффициент (будет объявлен в конце семестра)

Оценка за домашние работы вычисляется как среднее за все 5 сданных работ. За работу в течении семестра студент получает накопленную оценку

   OНакопленная =  0.2·ОКонтрольная + 0.6·ОДомашние задания + 0.2·ОСеминары

Итоговая оценка складывается из накопленной оценки и экзамена

   OИтоговая =  0.3·ОЭкзамена + 0.7·ОНакопленная

Семинары

Семинар A12.01

Разворот списка

Реализовать рекурсивную функцию reverse, которая обращает связи односвязанного списка в противоположную сторону. Таким образом последний элемент списка становится первым, предпоследний вторым, и т.д. Пусть список имеет вид [1, 2, 3, 4, 5], тогда после применения функции reverse он должен выглядеть, как [5, 4, 3, 2, 1]. В качестве подсказки воспользуйтесь итеративной версией функции, предложенной ниже.

   Re: Кроме рекурсивных функций принято еще выделять и рекурсивные структуры данных, к примеру списки и деревья.

Семинар A14.01

01 строки

Бинарный поиск

Ханойская башня - 1

Алгоритм Евклида

Реализовать рекурсивную версию алгоритма Евклида для нахождения наибольшего общего делителя.

   Re: При правильном решении вы должны получить хвостовую рекурсию.

Ханойская башня - 2

Реализовать рекурсивную функцию, получающую на вход число дисков Ханойской башни и выводящую состояние башень после каждого перемещения в оптимальном решении. Пример, n = 3, все диски на первом стержне:

1. [3, 2, 1]
2. []
3. []

Состояние после перемещения верхнего диска на 3 стержень:

1. [3, 2]
2. []
3. [1]

   Re: Для решения используйте задачу разобранную на семинре. Стержни можно смоделировать с помощью  стека.