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

Версия 20:57, 18 марта 2016

Содержание

1 Семинары
2 Домашние задания

Семинары

12 января

Ханойские башни

15 января

Сложность алгоритмов и стратегия "разделяй и властвуй"

19 января

Контест на сортировки (до 1 февраля)

22 января

Задачи на O-символику, подсчет числа инверсий, поиск максимума в унимодальном массиве и поиск в двоичном дереве поиска

26 января

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

29 января

Задачи на дом

2 февраля

Семинар перенесен на 8 февраля 10:30 – 11:50 (ауд. 505)

5 февраля

Контест на динамическое программирование (до 15 февраля)

9 февраля

Задачи на динамическое программирование

12 февраля

Наибольшая возрастающая подпоследовательность и оптимальное двоичное дерево поиска

16 февраля

Число кратчайших путей между двумя вершинами неориентированного графа без весов, см. контест (до 29 февраля)

19 февраля

Задачи A, B и C на графы из контеста (до 4 марта)

Домашние задания

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

Первое домашнее задание стоит из двух частей.

Крайний срок выполнения первой части — 15 февраля 10:30. Нужно решить три задачи на асимптотику (две — из пункта 1 и одну — из пункта 2) и две задачи на рекуррентные соотношения (одну — из пункта 1 и одну — из пункта 2). Решения нужно прислать по электронной почте преподавателю и учебному ассистенту. Также нужно быть готовым устно рассказать свое решение на консультации 15 февраля в 10:30 – 11:50 (в ауд. 511).

К 20 февраля нужно решить две задачи из контеста (одну — типа A и одну — типа B). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности.

Распределение задач:

Студенты	Асимптотика – 1	Асимптотика – 2	Асимптотика – 3	Рекуррентности – 1	Рекуррентности – 2	Контест – A	Контест – B
Иван Аустер	1.1	1.7	2.1	1.1	2.2	A1	B1
Валерий Батурин	1.2	1.8	2.2	1.8	2.3	A2	B1
Сергей Горбачев	1.3	1.1	2.3	1.7	2.4	A1	B1
Хетаг Купеев	1.4	1.2	2.4	1.6	2.5	A2	B1
Евгений Мещеряков	1.5	1.3	2.1	1.5	2.6	A1	B1
Екатерина Минеева	1.6	1.4	2.2	1.4	2.7	A2	B1
Антон Наумов	1.7	1.5	2.3	1.3	2.8	A1	B1
Никита Нестеров	1.8	1.6	2.4	1.2	2.7	A2	B2
Олег Николаев	1.1	1.8	2.3	1.3	2.6	A1	B2
Евгений Правда	1.2	1.1	2.2	1.4	2.5	A2	B2
Александр Рудь	1.3	1.2	2.1	1.5	2.4	A1	B2
Михаил Флоринский	1.4	1.3	2.4	1.6	2.3	A2	B2
Александр Чернявский	1.5	1.4	2.3	1.7	2.2	A1	B2
Антон Чернявский	1.6	1.5	2.2	1.8	2.1	A2	B2

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

Ко 2 марта (!) нужно решить две задачи из контеста (одну — типа A и одну — типа B). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности. Начало контеста — 22 февраля, 20:00.

К 15 марта (!) нужно решить две задачи из контеста (одну — типа A и одну — типа B). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности. Начало контеста — 4 марта, 20:00.

Распределение задач:

Студенты	Контест – A	Контест – B	Контест – A	Контест – B
Иван Аустер	A1	B1	A1	B2
Валерий Батурин	A2	B1	A1	B1
Сергей Горбачев	A1	B1	A2	B1
Евгений Мещеряков	A2	B1	A2	B2
Екатерина Минеева	A1	B1	A1	B2
Антон Наумов	A2	B1	A1	B1
Никита Нестеров	A1	B2	A2	B1
Олег Николаев	A2	B2	A2	B2
Евгений Правда	A1	B2	A1	B2
Александр Рудь	A2	B2	A1	B1
Михаил Флоринский	A1	B2	A2	B1
Александр Чернявский	A2	B2	A2	B2
Антон Чернявский	A1	B2	A1	B2

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

К 3 апреля нужно решить две задачи из контеста (одну — типа A и одну — типа B). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности.

Распределение задач типа B:

Студенты	Задача B
Иван Аустер	B1
Валерий Батурин	B1
Сергей Горбачев	B1
Евгений Мещеряков	B2
Екатерина Минеева	B2
Антон Наумов	B2
Никита Нестеров	B1
Олег Николаев	B1
Евгений Правда	B1
Александр Рудь	B2
Михаил Флоринский	B2
Александр Чернявский	B2
Антон Чернявский	B1

@@ Строка 45: / Строка 45: @@
 Крайний срок выполнения первой части —  15 февраля 10:30. Нужно решить три задачи на [https://www.dropbox.com/s/j82mgmhcrcbq4ra/asymptotic_homework.pdf?dl=0 асимптотику] (две — из пункта 1 и одну — из пункта 2) и две задачи на [https://www.dropbox.com/s/gwxvf34gg6nt4fe/recurrent_homework.pdf?dl=0 рекуррентные соотношения] (одну — из пункта 1 и одну — из пункта 2). Решения нужно прислать по электронной почте преподавателю и учебному ассистенту. Также нужно быть готовым устно рассказать свое решение на консультации 15 февраля в 10:30 – 11:50 (в ауд. 511).
-К 20 февраля нужно решить две задачи из [https://official.contest.yandex.ru/contest/2183 контеста] (одну типа A и одну — типа B). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности.
+К 20 февраля нужно решить две задачи из [https://official.contest.yandex.ru/contest/2183 контеста] (одну — типа A и одну — типа B). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности.
 Распределение задач: