imported>Melnichuk: /* Контрольная работа */

2016-06-19T22:18:07Z

Контрольная работа

Новая страница

===Первый семинар 11.01.2016===
Рекурсия и ханойские башни.
Другие применения рекурсии.
Анализ сложности алгоритмов.

===Второй семинар 13.01.2016===
Основы амортизационного анализа: банковский метод, метод потенциалов.
k-битовый счетчик.
Вектор или массив переменного размера.

===Третий семинар 18.01.2016===
Понятие асимптотики. О-исчисление.
Решение теоретических задач.

===Четвертый семинар 20.01.2016===
Merge, сортировка слиянием, partition, быстрая сортировка.
Практика. Реализация сортировок.
https://official.contest.yandex.ru/contest/2007/

===Пятый семинар 25.01.2016===
Порядковые статистики. Алгоритм и анализ сложности.
Практика. Реализация сортировок.
https://official.contest.yandex.ru/contest/2007/

===Шестой семинар 27.01.2016===
Основная теорема о рекуррентных асимптотических соотношениях.
Маленькая самостоятельная работа на асимптотики.

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

===Восьмой семинар 03.02.2016===
Динамическое программирование.
Типы динамики: одномерная и многомерная, восходящая и нисходящая, ленивая и явная.
Решение задачи максимального пути по таблице всеми возможными способами.

===Девятый семинар 08.02.2016===
Динамическое программирование.
Общий подход к решению задач методом динамического программирования.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2185/

===Десятый семинар 10.02.2016===
Динамическое программирование.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2185/

===Одиннадцатый семинар 15.02.2016===
Графы.
Представление графов в памяти: матрицы смежности, списки смежности, список ребер.
Виды графов: ориентированные и нет, с петлями и без них, с кратными ребрами и без них.
Обходы графов.
Обход в глубину. Реализация обхода в глубину. Связность графа. Число компонент связности.

===Двенадцатый семинар 17.02.2016===
Графы.
Обход в глубину. Топологическая сортировка.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2218/

===Тринадцатый семинар 22.02.2016===
Графы.
Обход в ширину. Поиск кратчайших расстояний в невзвешенных графах.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2243/

===Четырнадцатый семинар 24.02.2016===
Обход в ширину.
0-kBFS.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2243/

===Пятнадцатый семинар 29.02.2016===
Алгоритм Деикстры.
Описание, обоснование корректности.
Оценка времени работы.
Реализация с кучей и без кучи.

===Шестнадцатый семинар 02.03.2016===
Алгоритм Деикстры.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2270/

===Семнадцатый семинар 09.03.2016===
Алгоритмы Форда-Беллмана и Флойда.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2270/

===Восемнадцатый семинар 14.03.2016===
Алгоритмы Форда-Беллмана и Флойда.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2270/

===Девятнадцатый семинар 16.03.2016===
vector, stack, stack_max, queue, queue_max - построение и амортизационный анализ сложности работы.
Методы амортизационного анализа - прямой подсчет и банковский метод.

===Двадцатый семинар 21.03.2016===
Хеш-функции, хеш-таблицы, метод разрешения коллизий методом цепочек.
https://official.contest.yandex.ru/contest/2333/

===Двадцать первый семинар 04.04.2016===
Тест по материалам первого модуля.
https://yadi.sk/i/t-lK2on5qn53L

===Двадцать второй семинар 06.04.2016===
Разбор теста. Разбор домашнего задания.
Классические деревья поиска, типичная Си реализация.
https://yadi.sk/d/MbRJhW2xqn4jH

===Двадцать третий семинар 11.04.2016===
Юнит-тестирование деревьев поиска.
Красно-черное дерево.
Свойства красно-черного дерева.
Один из случаев вставки в красно-черное дерево.
https://yadi.sk/d/DVuJlkT8qtqV3

===Двадцать четвертый семинар 13.04.2016===
Вставка в красно-черное дерево.
Проверка дерева на красно-черность.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2381/

===Двадцать пятый семинар 18.04.2016===
Практика по решению задач. https://official.contest.yandex.ru/contest/2381/

===Двадцать шестой семинар 20.04.2016===
RMQ, RSQ, реализация на дереве отрезков.
Рекурсивная реализация дерева отрезков на основе массива.
Ленивые вычисления.
Ленивое присвоение в дереве отрезков.

===Двадцать седьмой семинар 25.04.2016===
Минимальные остовные деревья.
Алгоритм Крускала.
Генерация лабиринтов.

===Двадцать восьмой семинар 27.04.2016===
DSU. Интерфейс, реализация, эвристика сжатия путей, ранговая эвристика.
Применение в минимальных оставных деревьях.
Генерация лабиринтов.

===Двадцать девятый семинар 13.05.2016===
Разбор задачи про хеширование чисел Фиббоначчи.
Минимальные остовные деревья.
Алгоритм Прима.
Приближенное решение задачи коммивояжера.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2464/

===Тридцатый семинар 16.05.2016===
Жадные алгоритмы.
Решение теоретических задач.

===Тридцать первый семинар 18.05.2016===
Матроид. Жадные алгоритмы на матроиде.
Решение теоретических задач.

===Тридцать второй семинар 23.05.2016===
Конечный автомат.
Способы задания конечного автомата.
Разница ДКА и НКА.

===Тридцать третий семинар 30.05.2016===
НКА, сведение к ДКА.
Алгоритм построения минимального ДКА, эквивалентного данному.

===Тридцать четвертый семинар 01.06.2016===
Контекстно-свободные грамматики, нормальная форма Хомского.

===Тридцать пятый семинар 06.06.2016===
Сети, потоки, максимальный поток.
Практика по решению задач.
https://official.contest.yandex.ru/contest/2531/

===Первое домашнее задание===

Распределение задач:
{| class="wikitable"
|-
! Студенты !! Сортировка-1 !! Сортировка-2 !! Асимптотика – 1 !! Асимптотика – 2 !! Асимптотика – 3 !! Рекуррентности – 1 !! Рекуррентности – 2
|-
| Артемьев Максим || Перевертыш || Гармония || 2 || 4 || 1 || 7 || 8
|-
| Богдашевская Мария || Коллекционер Диего || Маляры || 4 || 1 || 2 || 7 || 6
|-
| Бочкарева Мария || Коллекционер Диего || Маляры || 3 || 8 || 4 || 3 || 1
|-
| Додихудоев Бехзод || Перевертыш || Гармония || 2 || 8 || 4 || 5 || 6
|-
| Дурдыева Кумуш || Коллекционер Диего || Гармония || 3 || 5 || 1 || 5 || 1
|-
| Журавлев Виталий || Коллекционер Диего || Гармония || 7 || 3 || 4 || 7 || 2
|-
| Маркович Александр || Коллекционер Диего || Маляры || 4 || 2 || 3 || 7 || 3
|-
| Салимов Фирдавс || Перевертыш || Маляры || 3 || 1 || 4 || 7 || 8
|-
| Сердюков Иннокентий || Перевертыш || Маляры || 1 || 5 || 1 || 4 || 1
|-
| Соловьев Алексей || Перевертыш || Гармония || 7 || 1 || 4 || 8 || 5
|-
| Старков Александр || Перевертыш || Маляры || 8 || 5 || 1 || 7 || 3
|-
| Тарасов Денис || Коллекционер Диего || Гармония || 3 || 6 || 4 || 3 || 5
|-
| Третьяков Александр || Перевертыш || Гармония || 5 || 2 || 4 || 8 || 4
|-
| Тумашова Анна || Коллекционер Диего || Маляры || 7 || 1 || 3 || 8 || 4
|-
| Шибанкова Екатерина || Перевертыш || Маляры || 2 || 6 || 1 || 2 || 6
|-
|}
О второй части домашнего задания будет сообщено дополнительно.

Сдавать домашние задания необходимо в AnyTask. Курс и задачи в нем вскоре появятся.
Сдача происходит в формате PDF, так что изучайте основы LaTeX, они вам еще много раз пригодятся.
Делайн по теории - 15 февраля.

Контест с дополнительными задачами: https://official.contest.yandex.ru/contest/2187/

===Второе домашнее задание===

Распределение задач:
{| class="wikitable"
|-
! Студенты !! Динамика-1 !! Динамика-2 !! Графы-1 !! Графы-2
|-
| Артемьев Максим || 1 || 2 || 1 || 1
|-
| Богдашевская Мария || 2 || 1 || 1 || 1
|-
| Бочкарева Мария || 1 || 1 || 2 || 1
|-
| Додихудоев Бехзод || 2 || 2 || 2 || 2
|-
| Дурдыева Кумуш || 1 || 1 || 2 || 1
|-
| Журавлев Виталий || 1 || 2 || 2 || 2
|-
| Маркович Александр || 2 || 2 || 1 || 1
|-
| Салимов Фирдавс || 2 || 1 || 2 || 1
|-
| Сердюков Иннокентий || 2 || 1 || 2 || 1
|-
| Соловьев Алексей || 1 || 2 || 2 || 2
|-
| Старков Александр || 1 || 2 || 1 || 1
|-
| Тарасов Денис || 1 || 2 || 1 || 1
|-
| Третьяков Александр || 1 || 1 || 1 || 2
|-
| Тумашова Анна || 1 || 1 || 1 || 1
|-
| Шибанкова Екатерина || 2 || 1 || 2 || 2
|-
|}
О второй части домашнего задания будет сообщено дополнительно.

Сдавать домашние задания необходимо в AnyTask, теория сдается в PDF.
Делайн - 29 февраля.
Дедлайн по второй части - 14 марта.

===Третье домашнее задание===

Распределение задач:
{| class="wikitable"
|-
! Студенты !! Графы-1 !! Графы-2 !! Хеш-таблицы-1 !! Хеш-таблицы-2
|-
| Артемьев Максим || 1 || 2 || 2 || 1
|-
| Богдашевская Мария || 1 || 1 || 2 || 1
|-
| Бочкарева Мария || 1 || 1 || 2 || 1
|-
| Додихудоев Бехзод || 1 || 2 || 2 || 1
|-
| Дурдыева Кумуш || 1 || 1 || 2 || 1
|-
| Журавлев Виталий || 1 || 1 || 2 || 1
|-
| Маркович Александр || 1 || 1 || 2 || 1
|-
| Салимов Фирдавс || 1 || 1 || 2 || 1
|-
| Сердюков Иннокентий || 1 || 1 || 1 || 1
|-
| Соловьев Алексей || 1 || 2 || 2 || 1
|-
| Старков Александр || 1 || 1 || 2 || 1
|-
| Тарасов Денис || 1 || 1 || 2 || 1
|-
| Третьяков Александр || 1 || 1 || 1 || 1
|-
| Тумашова Анна || 1 || 1 || 1 || 1
|-
| Шибанкова Екатерина || 1 || 2 || 2 || 1
|-
|}

Сдавать домашние задания необходимо в AnyTask, теория сдается в PDF.
Дедлайн - 3 апреля.

Дедлайн по второй части - 26 апреля. Как обычно, сдаем в anytask, теоретическую часть присылаем в pdf.

Медленное решение задачи А1 https://yadi.sk/i/xipVWP0HrgZDq

===Четвертое домашнее задание===

Распределение задач:
{| class="wikitable"
|-
! Студенты !! Ртуть !! Электросхема !! Дерево
|-
| Артемьев Максим || 1 || 2 || 1
|-
| Богдашевская Мария || 1 || 2 || 1
|-
| Бочкарева Мария || 1 || 1 || 1
|-
| Додихудоев Бехзод || 1 || 2 || 1
|-
| Дурдыева Кумуш || 1 || 1 || 1
|-
| Журавлев Виталий || 1 || 2 || 1
|-
| Маркович Александр || 1 || 1 || 1
|-
| Салимов Фирдавс || 1 || 1 || 1
|-
| Сердюков Иннокентий || 1 || 1 || 1
|-
| Соловьев Алексей || 1 || 2 || 1
|-
| Старков Александр || 1 || 1 || 1
|-
| Тарасов Денис || 1 || 1 || 1
|-
| Третьяков Александр || 1 || 1 || 1
|-
| Тумашова Анна || 1 || 2 || 1
|-
| Шибанкова Екатерина || 1 || 1 || 1
|-
|}

===Пятое домашнее задание===

Распределение задач:
{| class="wikitable"
|-
! Студенты !! 1 !! 2 !! 3 !! 4 !! Контест (автомат) !! Потоки
|-
| Артемьев Максим || 2 || 4 || 1 || 1 || 1 || 2
|-
| Богдашевская Мария || 4 || 4 || 1 || 1 || 1 || 2
|-
| Бочкарева Мария || 1 || 4 || 1 || 1 || 2 || 2
|-
| Додихудоев Бехзод || 6 || 3 || 1 || 1 || 1 || 2
|-
| Дурдыева Кумуш || 2 || 3 || 1 || 1 || 2 || 1
|-
| Журавлев Виталий || 3 || 4 || 1 || 1 || 1 || 2
|-
| Маркович Александр || 3 || 3 || 1 || 1 || 1 || 2
|-
| Салимов Фирдавс || 4 || 1 || 1 || 1 || 2 || 1
|-
| Сердюков Иннокентий || 5 || 4 || 1 || 1 || 2 || 2
|-
| Соловьев Алексей || 2 || 1 || 1 || 1 || 2 || 2
|-
| Старков Александр || 1 || 3 || 1 || 1 || 2 || 2
|-
| Тарасов Денис || 2 || 4 || 1 || 1 || 2 || 1
|-
| Третьяков Александр || 4 || 3 || 1 || 1 || 1 || 1
|-
| Тумашова Анна || 5 || 3 || 1 || 1 || 2 || 2
|-
| Шибанкова Екатерина || 3 || 2 || 1 || 1 || 1 || 2
|-
|}

===Контрольная работа===
https://official.contest.yandex.ru/contest/2558

Оценки

{| class="wikitable"
|-
! Студент !! Оценка
|-
| Артемьев Максим || 8
|-
| Богдашевская Мария ||
|-
| Бочкарева Мария || 6
|-
| Додихудоев Бехзод ||
|-
| Дурдыева Кумуш ||
|-
| Журавлев Виталий || 6
|-
| Маркович Александр || 5
|-
| Салимов Фирдавс ||
|-
| Сердюков Иннокентий || 8
|-
| Соловьев Алексей || 9
|-
| Старков Александр ||
|-
| Тарасов Денис || 3
|-
| Третьяков Александр || 9
|-
| Тумашова Анна ||
|-
| Шибанкова Екатерина || 4
|-
|}

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

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

===Итоги===
В таблице
https://docs.google.com/spreadsheets/d/1JO-tZOPb4rJupnNsx8XozAGWc5hCiWk3CEdk2MP5c9k/edit?usp=sharing

Алгоритмы и структуры данных семинары 155-2 - История изменений

imported>Melnichuk: /* Контрольная работа */