Алгоритмы и структуры данных, семинар группы 158-2 — различия между версиями
(Перенес решения A14.01 на github) |
(A19.01) |
||
Строка 1: | Строка 1: | ||
Последний семинар был посвящен | Последний семинар был посвящен | ||
− | [http://wiki.cs.hse.ru/Алгоритмы_и_структуры_данных,_семинар_группы_158-2#.D0.A1.D0.B5.D0.BC.D0.B8.D0.BD.D0.B0.D1. | + | [http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных,_семинар_группы_158-2#.D0.A1.D0.B5.D0.BC.D0.B8.D0.BD.D0.B0.D1.80_A19.01 сортировкам], |
текущие результаты могут быть найдены | текущие результаты могут быть найдены | ||
[https://docs.google.com/spreadsheets/d/1Zv-qcOHHZyPKgA3AfpbQaxmTXiHF9FD9kiGb4aJNIaI/edit?usp=sharing здесь]. | [https://docs.google.com/spreadsheets/d/1Zv-qcOHHZyPKgA3AfpbQaxmTXiHF9FD9kiGb4aJNIaI/edit?usp=sharing здесь]. | ||
+ | |||
+ | '''События:''' | ||
+ | |||
+ | '''18 янв.''' Пробный [https://contest.yandex.ru/contest/2007/enter/ контест], посвященный сортировкам. | ||
==Правила игры== | ==Правила игры== | ||
Строка 132: | Строка 136: | ||
<hr> | <hr> | ||
:'''Re:''' Для решения используйте задачу разобранную на семинре. Стержни можно смоделировать с помощью [http://en.cppreference.com/w/cpp/container/vector вектора]. | :'''Re:''' Для решения используйте задачу разобранную на семинре. Стержни можно смоделировать с помощью [http://en.cppreference.com/w/cpp/container/vector вектора]. | ||
+ | |||
+ | ===Семинар A19.01=== | ||
+ | # [https://en.wikipedia.org/wiki/Insertion_sort Insertion sort] | ||
+ | # [https://en.wikipedia.org/wiki/Merge_sort Merge sort] | ||
+ | # In-place merge sort (описание появится чуть позже) | ||
+ | |||
+ | Дедлайн сдачи упражнений: 26 января, 9:00. | ||
+ | |||
+ | ====Insertion sort==== | ||
+ | Реализуйте сортировку вставками. | ||
+ | <div align="right">[Решение Смбата]</div> | ||
+ | <hr> | ||
+ | |||
+ | ====External sorting (упражнение)==== | ||
+ | У студента Никиты есть компьютер, оперативная память которого может хранить M чисел и имеет небольшой буфер. На диске у этого компьютера хранится массив размером 100M чисел и имеется еще куча свободного места. Предложите Никите алгоритм, с помощью которого он мог бы отсортировать свой массив. | ||
+ | <div align="right">[Решение]</div> | ||
+ | <hr> | ||
+ | :'''Re:''' Подумайте, какие из известных видов сортировки можно использовать для решения задачи, если весь массив не помещается в память. | ||
+ | |||
+ | ====Merge sort (упражнение)==== | ||
+ | Реализуйте сортировку слиянием. | ||
+ | <div align="right">[Решение]</div> | ||
+ | <hr> | ||
+ | :'''Re:''' Для зачета вы должны пройти все тесты в [https://contest.yandex.ru/contest/2007 контесте]. За задачу вы получите два плюсика, реализовав функцию [https://contest.yandex.ru/contest/2007/problems/C/ merge] и функцию [https://contest.yandex.ru/contest/2007/problems/D/ merge_sort]. Сначала присылайте семинарситу первую часть решение, а затем уже только саму сортировку. | ||
+ | |||
+ | ====In-place merge sort (упражнение)==== | ||
+ | Студентка Таня очень любит читать Хабр. В одном из постов она натолкнулся на описание алгоритма (описание появится чуть позже), который позволяет применять сортировку слиянием без использования дополнительной памяти. Помогите Тане доказать правильность работы алгоритма и оценить его сложность работы. | ||
+ | <div align="right">[Решение]</div> | ||
+ | <hr> | ||
+ | :'''Re:''' Задача стоит 3 плюсика. Доказательство правильности работы алгоритма (1 плюсик) и оценка сложности (2 плюсика). |
Версия 09:36, 20 января 2016
Последний семинар был посвящен сортировкам, текущие результаты могут быть найдены здесь.
События:
18 янв. Пробный контест, посвященный сортировкам.
Правила игры
В основном все общение будет происходить с семинаристом курса, однако к проверке работы также будет привлекаться и учебный ассистент. Если у студента есть некоторые разногласия с ассистентом, то он всегда может обратиться к семинаристу, чтобы разрешить конфликт.
Семинарист: Симагин Денис, 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
- Знакомство с группой.
- Рассмотрение примеров использования рекурсии.
Факториал
Предложить рекурсивный вариант вычисления факториала.
- Re: Очевидно, что предложенная рекурсивная реализация факториала не является хвостовой рекурсией, однако существует итерационная версия алгоритма. Поэтому наличие хвостовой рекурсии является достаточным, но не обходимым условием наличия итерационного алгоритма с использованием константной памяти.
Фибоначчи
Предложить рекурсивный вариант вычисления чисел Фибоначчи.
- Re: Показан пример сведения множественной рекурсии к одиночной.
Степень
Предложить рекурсивный алгоритм вычисления неотрицательной степени числа.
Разворот списка (упражнение)
Реализовать рекурсивную функцию reverse, которая обращает связи односвязанного списка в противоположную сторону. Таким образом последний элемент списка становится первым, предпоследний вторым, и т.д. Пусть список имеет вид [1, 2, 3, 4, 5], тогда после применения функции reverse он должен выглядеть, как [5, 4, 3, 2, 1].
- Re: Кстати, кроме рекурсивных функций принято еще выделять и рекурсивные структуры данных, к примеру списки и деревья.
Семинар A14.01
- Множественная и одиночная рекурсии.
- Стек и куча.
- Мемоизация.
- Хвостовая рекурсия.
- Особенности реализации рекурсий.
- Принцип разделяй и властвуй.
- Бинарный поиск.
01 строки
Предложить рекурсивный алгоритм, выводящий всевозможные строки длины n из 0 и 1 в лексикографическом порядке.
- Re: В решении продемонстрированы все основные особенности реализации рекурсивных функций.
Бинарный поиск
Предложить рекурсивный алгоритм, производящий бинарный поиск элемента в отсортированном массиве.
- Re: Метод олицетворят подход разделяй и властвуй.
Ханойская башня - 1
Предложить рекурсивную функцию, печатающую последовательность перемещений (в формате (x, y), где x и y — номера стержней, с которого и на который перемещается диск), являющуюся решением задачи о Ханойской башне.
Алгоритм Евклида (упражнение)
Реализовать рекурсивную версию алгоритма Евклида для нахождения наибольшего общего делителя.
- Re: При правильном решении вы должны получить хвостовую рекурсию.
Ханойская башня - 2 (упражнение)
Реализовать рекурсивную функцию, получающую на вход число дисков Ханойской башни и выводящую состояние башень после каждого перемещения в оптимальном решении. Пример, n = 3, все диски на первом стержне:
- [3, 2, 1]
- []
- []
Состояние после перемещения верхнего диска на 3 стержень:
- [3, 2]
- []
- [1]
- Re: Для решения используйте задачу разобранную на семинре. Стержни можно смоделировать с помощью вектора.
Семинар A19.01
- Insertion sort
- Merge sort
- In-place merge sort (описание появится чуть позже)
Дедлайн сдачи упражнений: 26 января, 9:00.
Insertion sort
Реализуйте сортировку вставками.
External sorting (упражнение)
У студента Никиты есть компьютер, оперативная память которого может хранить M чисел и имеет небольшой буфер. На диске у этого компьютера хранится массив размером 100M чисел и имеется еще куча свободного места. Предложите Никите алгоритм, с помощью которого он мог бы отсортировать свой массив.
- Re: Подумайте, какие из известных видов сортировки можно использовать для решения задачи, если весь массив не помещается в память.
Merge sort (упражнение)
Реализуйте сортировку слиянием.
- Re: Для зачета вы должны пройти все тесты в контесте. За задачу вы получите два плюсика, реализовав функцию merge и функцию merge_sort. Сначала присылайте семинарситу первую часть решение, а затем уже только саму сортировку.
In-place merge sort (упражнение)
Студентка Таня очень любит читать Хабр. В одном из постов она натолкнулся на описание алгоритма (описание появится чуть позже), который позволяет применять сортировку слиянием без использования дополнительной памяти. Помогите Тане доказать правильность работы алгоритма и оценить его сложность работы.
- Re: Задача стоит 3 плюсика. Доказательство правильности работы алгоритма (1 плюсик) и оценка сложности (2 плюсика).