Алгоритмы и структуры данных, семинар группы 158-2

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Последний семинар был посвящен сортировкам, текущие результаты могут быть найдены здесь.

События:

18 янв. Пробный контест, посвященный сортировкам.

Правила игры

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

Семинарист: Симагин Денис, simagin.mail@yandex.ru

Ассистент: Владимир Гончаров, dev.zelta@gmail.com

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

День недели Время проведения Аудитория
Вторник
09:00 – 10:20
327
Четверг
09:00 – 10:20
505

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

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

Семинары

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

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

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

Объединять несколько решений в одном письме нельзя, это лишь создаст путаницу в обсуждении. При нарушении правил семинарист не дает гарантий, что решение будет проверено.

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

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

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

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

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

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

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

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

Семинары

Семинар A12.01

  1. Знакомство с группой.
  2. Рассмотрение примеров использования рекурсии.

Факториал

Предложить рекурсивный вариант вычисления факториала.

[Решение]
Re: Очевидно, что предложенная рекурсивная реализация факториала не является хвостовой рекурсией, однако существует итерационная версия алгоритма. Поэтому наличие хвостовой рекурсии является достаточным, но не обходимым условием наличия итерационного алгоритма с использованием константной памяти.

Фибоначчи

Предложить рекурсивный вариант вычисления чисел Фибоначчи.

[Решение]
Re: Показан пример сведения множественной рекурсии к одиночной.

Степень

Предложить рекурсивный алгоритм вычисления неотрицательной степени числа.

[Решение]

Разворот списка (упражнение)

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

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

Семинар A14.01

  1. Множественная и одиночная рекурсии.
  2. Стек и куча.
  3. Мемоизация.
  4. Хвостовая рекурсия.
  5. Особенности реализации рекурсий.
  6. Принцип разделяй и властвуй.
  7. Бинарный поиск.

01 строки

Предложить рекурсивный алгоритм, выводящий всевозможные строки длины n из 0 и 1 в лексикографическом порядке.

[Решение]
Re: В решении продемонстрированы все основные особенности реализации рекурсивных функций.

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

Предложить рекурсивный алгоритм, производящий бинарный поиск элемента в отсортированном массиве.

[Решение Тани]
Re: Метод олицетворят подход разделяй и властвуй.

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

Предложить рекурсивную функцию, печатающую последовательность перемещений (в формате (x, y), где x и y — номера стержней, с которого и на который перемещается диск), являющуюся решением задачи о Ханойской башне.

[Решение Свята]

Алгоритм Евклида (упражнение)

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

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

Ханойская башня - 2 (упражнение)

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

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

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

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

Семинар A19.01

  1. Insertion sort
  2. Merge sort
  3. In-place merge sort (материал появится 21 января, вечером)

Insertion sort

Реализуйте сортировку вставками.

[Решение Смбата]

External sorting (упражнение, 26 января)

У студента Никиты есть компьютер, оперативная память которого может хранить M чисел и имеет небольшой буфер. На диске у этого компьютера хранится массив размером 100M чисел и имеется еще куча свободного места. Предложите Никите алгоритм, с помощью которого он мог бы отсортировать свой массив.

[Решение]
Re: Подумайте, какие из известных видов сортировки можно использовать для решения задачи, если весь массив не помещается в память.

Merge sort (упражнение, 26 января)

Реализуйте сортировку слиянием.

[Решение]
Re: Для зачета вы должны пройти все тесты в контесте. За задачу вы получите два плюсика, реализовав функцию merge и функцию merge_sort. Код семинаристу стоит присылать только после того, как пройдены все тесты. Сначала присылайте первую задача, а затем уже саму сортировку.

In-place merge sort (упражнение, 28 января)

Студентка Таня очень любит читать Хабр. В одном из постов она натолкнулся на описание алгоритма (описание появится чуть позже), который позволяет применять сортировку слиянием без использования дополнительной памяти. Помогите Тане доказать правильность работы алгоритма и оценить его сложность работы.

[Решение]
Re: Задача стоит 3 плюсика. Доказательство правильности работы алгоритма (1 плюсик) и оценка сложности (2 плюсика).

Семинар A21.01

  1. Закончили разбор сортировки in-place merge (конспект появится 21 января, вечером)
  2. Поговорили о quick sort, особое внимание уделили выбору опорного элемента.
  3. Начали говорить о О-символике

В чем разница между O(f) и o(f)

Материал появится 21 января, вечером.

Quick sort (упражнение, 26 января)

Реализуйте сортировку qiuck sort.

[Решение]
Re: Для зачета вы должны пройти все тесты в контесте. За задачу вы получите два плюсика, реализовав функцию pation и функцию quick_sort. Обратите особое внимание, как вы выбору опорного элемента.выбираете опорный элемент]. Код семинаристу стоит присылать только после того, как пройдены все тесты. Сначала присылайте первую задача, а затем уже саму сортировку.

Задачи на О-нотацию (упражнение, 26 января)

Материал появится 21 января, вечером.

[Решение]
Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных,_семинар_группы_158-2&oldid=18418»