Алгоритмы и структуры данных семинары 152-2 — различия между версиями
.obj (обсуждение | вклад) (→Аудиторная работа) |
.obj (обсуждение | вклад) (→Оценки) |
||
(не показаны 22 промежуточные версии этого же участника) | |||
Строка 155: | Строка 155: | ||
|} | |} | ||
+ | К 26 апреля нужно решить две задачи из [https://official.contest.yandex.ru/contest/2370/enter/ контеста] (одну типа A и одну — типа B). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности. | ||
+ | |||
+ | Обратите внимание, что, начиная с этого контеста, за неудачные посылки вы будете получать штраф. Изначально задача стоит 10 баллов, каждая из первых девяти неудачных попыток дает -1 балл. Посылки с ошибками компиляции или не прошедшие проверку стиля не штрафуются. Также не штрафуются посылки, не прошедшие тест из условия. Тщательно тестируйте свои решения, чтобы не получать штраф. | ||
+ | |||
+ | Распределение задач типа A: | ||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | ! Студенты !! Задача A | ||
+ | |- | ||
+ | | Иван Аустер || A2 | ||
+ | |- | ||
+ | | Валерий Батурин || A2 | ||
+ | |- | ||
+ | | Сергей Горбачев || A2 | ||
+ | |- | ||
+ | | Евгений Мещеряков || A2 | ||
+ | |- | ||
+ | | Екатерина Минеева || A2 | ||
+ | |- | ||
+ | | Антон Наумов || A2 | ||
+ | |- | ||
+ | | Никита Нестеров || A1 | ||
+ | |- | ||
+ | | Олег Николаев || A1 | ||
+ | |- | ||
+ | | Евгений Правда || A1 | ||
+ | |- | ||
+ | | Александр Рудь || A1 | ||
+ | |- | ||
+ | | Михаил Флоринский || A1 | ||
+ | |- | ||
+ | | Александр Чернявский || A1 | ||
+ | |- | ||
+ | | Антон Чернявский || A2 | ||
+ | |} | ||
+ | |||
+ | === Четвертое домашнее задание === | ||
+ | |||
+ | К 22 мая нужно решить задачи из [https://official.contest.yandex.ru/contest/2473 контеста] (по одной каждого типа). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности. | ||
+ | |||
+ | Распределение задач типа B: | ||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | ! Студенты !! Задача B | ||
+ | |- | ||
+ | | Иван Аустер || B2 | ||
+ | |- | ||
+ | | Валерий Батурин || B2 | ||
+ | |- | ||
+ | | Сергей Горбачев || B2 | ||
+ | |- | ||
+ | | Евгений Мещеряков || B1 | ||
+ | |- | ||
+ | | Екатерина Минеева || B2 | ||
+ | |- | ||
+ | | Антон Наумов || B2 | ||
+ | |- | ||
+ | | Никита Нестеров || B1 | ||
+ | |- | ||
+ | | Олег Николаев || B1 | ||
+ | |- | ||
+ | | Евгений Правда || B2 | ||
+ | |- | ||
+ | | Александр Рудь || B2 | ||
+ | |- | ||
+ | | Михаил Флоринский || B1 | ||
+ | |- | ||
+ | | Александр Чернявский || B1 | ||
+ | |- | ||
+ | | Антон Чернявский || B1 | ||
+ | |} | ||
+ | |||
+ | === Пятое домашнее задание === | ||
+ | |||
+ | К 6 (!) июня нужно решить четыре задачи на [https://www.dropbox.com/s/eo688wfmq9qg8a3/dfa.pdf?dl=0 конечные автоматы] (по одной из каждого пункта), к 8 июня — одну задачу из [https://official.contest.yandex.ru/contest/2511 контеста], а к 16 июня — еще одну из другого [https://official.contest.yandex.ru/contest/2512 контеста]. | ||
+ | |||
+ | Распределение теоретических задач из первых двух пунктов и задач из контеста: | ||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | ! Студенты !! Задача 1 !! Задача 2 !! Задача из [https://official.contest.yandex.ru/contest/2511 первого контеста] !! Задача из [https://official.contest.yandex.ru/contest/2512 второго контеста] | ||
+ | |- | ||
+ | | Иван Аустер || a || c || A || B | ||
+ | |- | ||
+ | | Валерий Батурин || b || a || B || B | ||
+ | |- | ||
+ | | Сергей Горбачев || c || d || A || A | ||
+ | |- | ||
+ | | Евгений Мещеряков || d || c || B || B | ||
+ | |- | ||
+ | | Екатерина Минеева || e || b || A || A | ||
+ | |- | ||
+ | | Антон Наумов || f || a || B || B | ||
+ | |- | ||
+ | | Никита Нестеров || a || d || A || A | ||
+ | |- | ||
+ | | Олег Николаев || b || c || B || A | ||
+ | |- | ||
+ | | Евгений Правда || c || b || A || B | ||
+ | |- | ||
+ | | Александр Рудь || d || a || B || A | ||
+ | |- | ||
+ | | Михаил Флоринский || e || d || A || A | ||
+ | |- | ||
+ | | Александр Чернявский || f || c || B || B | ||
+ | |- | ||
+ | | Антон Чернявский || a || b || A || A | ||
+ | |} | ||
== Оценки == | == Оценки == | ||
− | |||
{| class="wikitable" style="text-align: right" | {| class="wikitable" style="text-align: right" | ||
|- | |- | ||
− | ! Студенты !! Первое домашнее задание | + | ! Студенты !! Первое домашнее задание !! Второе домашнее задание !! Третье домашнее задание !! Четвертое домашнее задание !! Пятое домашнее задание !! Аудиторная работа !! Контрольная работа !! Накопленная оценка |
|- | |- | ||
− | | Иван Аустер || 9 | + | | Иван Аустер || 9 || 6 || 5 || 3 || 2 || 6 || 8 || 6 |
|- | |- | ||
− | | Валерий Батурин || 10 | + | | Валерий Батурин || 10 || 6 || 4 || 5 || 5 || 6 || 3 || 5 |
|- | |- | ||
− | | Сергей Горбачев || 8 | + | | Сергей Горбачев || 8 || 6 || 9 || 7 || 8 || 10 || 10 || 9 |
|- | |- | ||
− | | Евгений Мещеряков || 0 | + | | Евгений Мещеряков || 0 || 0 || 0 || 0 || 0 || 2 || 0 || 1 |
|- | |- | ||
− | | Екатерина Минеева || 10 | + | | Екатерина Минеева || 10 || 10 || 5 || 8 || 10 || 10 || 10 || 9 |
|- | |- | ||
− | | Антон Наумов || 10 | + | | Антон Наумов || 10 || 5 || 2 || 3 || 0 || 5 || 0 || 3 |
|- | |- | ||
− | | Никита Нестеров || 7 | + | | Никита Нестеров || 7 || 3 || 3 || 0 || 2 || 7 || 10 || 5 |
|- | |- | ||
− | | Олег Николаев || 5 | + | | Олег Николаев || 5 || 0 || 0 || 0 || 0 || 2 || 0 || 1 |
|- | |- | ||
− | | Евгений Правда || 10 | + | | Евгений Правда || 10 || 10 || 10 || 9 || 10 || 10 || 10 || 10 |
|- | |- | ||
− | | Александр Рудь || 7 | + | | Александр Рудь || 7 || 5 || 0 || 2 || 0 || 2 || 0 || 2 |
|- | |- | ||
− | | Михаил Флоринский || 9 | + | | Михаил Флоринский || 9 || 9 || 5 || 5 || 3 || 6 || 10 || 7 |
|- | |- | ||
− | | Александр Чернявский || 10 | + | | Александр Чернявский || 10 || 10 || 7 || 8 || 9 || 10 || 10 || 9 |
|- | |- | ||
− | | Антон Чернявский || 10 | + | | Антон Чернявский || 10 || 10 || 8 || 8 || 9 || 10 || 7 || 9 |
|} | |} | ||
Строка 193: | Строка 299: | ||
{| class="wikitable" style="text-align: right" | {| class="wikitable" style="text-align: right" | ||
|- | |- | ||
− | ! Студенты !! [https://official.contest.yandex.ru/contest/2007/enter/ Сортировки] !! [https://official.contest.yandex.ru/contest/2185/enter/ Динамическое программирование] !! [https://official.contest.yandex.ru/contest/2210/enter/ Число кратчайших путей] !! [https://official.contest.yandex.ru/contest/2218/enter/ Графы] | + | ! Студенты !! [https://official.contest.yandex.ru/contest/2007/enter/ Сортировки] !! [https://official.contest.yandex.ru/contest/2185/enter/ Динамическое программирование] !! [https://official.contest.yandex.ru/contest/2210/enter/ Число кратчайших путей] !! [https://official.contest.yandex.ru/contest/2218/enter/ Графы] !! Апрельский тест |
|- | |- | ||
− | | Иван Аустер || 5/6 || 2/2 || 0/1 || 2/3 | + | | Иван Аустер || 5/6 || 2/2 || 0/1 || 2/3 || 3 |
|- | |- | ||
− | | Валерий Батурин || 6/6 || 0/2 || 1/1 || 1/3 | + | | Валерий Батурин || 6/6 || 0/2 || 1/1 || 1/3 || 2 |
|- | |- | ||
− | | Сергей Горбачев || 5/6 || 2/2 || 1/1 || 3/3 | + | | Сергей Горбачев || 5/6 || 2/2 || 1/1 || 3/3 || 9,5 |
|- | |- | ||
− | | Евгений Мещеряков || 3/6 || 0/2 || 0/1 || 0/3 | + | | Евгений Мещеряков || 3/6 || 0/2 || 0/1 || 0/3 || 1 |
|- | |- | ||
− | | Екатерина Минеева || 6/6 || 2/2 || 1/1 || 3/3 | + | | Екатерина Минеева || 6/6 || 2/2 || 1/1 || 3/3 || 7 |
|- | |- | ||
− | | Антон Наумов || 6/6 || 1/2 || 0/1 || 0/3 | + | | Антон Наумов || 6/6 || 1/2 || 0/1 || 0/3 || 10 |
|- | |- | ||
− | | Никита Нестеров || 4/6 || 0/2 || 1/1 || 2/3 | + | | Никита Нестеров || 4/6 || 0/2 || 1/1 || 2/3 || 9 |
|- | |- | ||
− | | Олег Николаев || 2/6 || 0/2 || 0/1 || 0/3 | + | | Олег Николаев || 2/6 || 0/2 || 0/1 || 0/3 || 6 |
|- | |- | ||
− | | Евгений Правда || 6/6 || 2/2 || 1/1 || 5/3 | + | | Евгений Правда || 6/6 || 2/2 || 1/1 || 5/3 || 8 |
|- | |- | ||
− | | Александр Рудь || 5/6 || 0/2 || 0/1 || 0/3 | + | | Александр Рудь || 5/6 || 0/2 || 0/1 || 0/3 || 3,5 |
|- | |- | ||
− | | Михаил Флоринский || 5/6 || 1/2 || 0/1 || 1/3 | + | | Михаил Флоринский || 5/6 || 1/2 || 0/1 || 1/3 || 7,5 |
|- | |- | ||
− | | Александр Чернявский || 6/6 || 2/2 || 1/1 || 4/3 | + | | Александр Чернявский || 6/6 || 2/2 || 1/1 || 4/3 || 9,5 |
|- | |- | ||
− | | Антон Чернявский || 5/6 || 2/2 || 1/1 || 4/3 | + | | Антон Чернявский || 5/6 || 2/2 || 1/1 || 4/3 || 7,5 |
|} | |} |
Текущая версия на 10:46, 22 июня 2016
Содержание
Семинары
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 |
К 26 апреля нужно решить две задачи из контеста (одну типа A и одну — типа B). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности.
Обратите внимание, что, начиная с этого контеста, за неудачные посылки вы будете получать штраф. Изначально задача стоит 10 баллов, каждая из первых девяти неудачных попыток дает -1 балл. Посылки с ошибками компиляции или не прошедшие проверку стиля не штрафуются. Также не штрафуются посылки, не прошедшие тест из условия. Тщательно тестируйте свои решения, чтобы не получать штраф.
Распределение задач типа A:
Студенты | Задача A |
---|---|
Иван Аустер | A2 |
Валерий Батурин | A2 |
Сергей Горбачев | A2 |
Евгений Мещеряков | A2 |
Екатерина Минеева | A2 |
Антон Наумов | A2 |
Никита Нестеров | A1 |
Олег Николаев | A1 |
Евгений Правда | A1 |
Александр Рудь | A1 |
Михаил Флоринский | A1 |
Александр Чернявский | A1 |
Антон Чернявский | A2 |
Четвертое домашнее задание
К 22 мая нужно решить задачи из контеста (по одной каждого типа). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности.
Распределение задач типа B:
Студенты | Задача B |
---|---|
Иван Аустер | B2 |
Валерий Батурин | B2 |
Сергей Горбачев | B2 |
Евгений Мещеряков | B1 |
Екатерина Минеева | B2 |
Антон Наумов | B2 |
Никита Нестеров | B1 |
Олег Николаев | B1 |
Евгений Правда | B2 |
Александр Рудь | B2 |
Михаил Флоринский | B1 |
Александр Чернявский | B1 |
Антон Чернявский | B1 |
Пятое домашнее задание
К 6 (!) июня нужно решить четыре задачи на конечные автоматы (по одной из каждого пункта), к 8 июня — одну задачу из контеста, а к 16 июня — еще одну из другого контеста.
Распределение теоретических задач из первых двух пунктов и задач из контеста:
Студенты | Задача 1 | Задача 2 | Задача из первого контеста | Задача из второго контеста |
---|---|---|---|---|
Иван Аустер | a | c | A | B |
Валерий Батурин | b | a | B | B |
Сергей Горбачев | c | d | A | A |
Евгений Мещеряков | d | c | B | B |
Екатерина Минеева | e | b | A | A |
Антон Наумов | f | a | B | B |
Никита Нестеров | a | d | A | A |
Олег Николаев | b | c | B | A |
Евгений Правда | c | b | A | B |
Александр Рудь | d | a | B | A |
Михаил Флоринский | e | d | A | A |
Александр Чернявский | f | c | B | B |
Антон Чернявский | a | b | A | A |
Оценки
Студенты | Первое домашнее задание | Второе домашнее задание | Третье домашнее задание | Четвертое домашнее задание | Пятое домашнее задание | Аудиторная работа | Контрольная работа | Накопленная оценка |
---|---|---|---|---|---|---|---|---|
Иван Аустер | 9 | 6 | 5 | 3 | 2 | 6 | 8 | 6 |
Валерий Батурин | 10 | 6 | 4 | 5 | 5 | 6 | 3 | 5 |
Сергей Горбачев | 8 | 6 | 9 | 7 | 8 | 10 | 10 | 9 |
Евгений Мещеряков | 0 | 0 | 0 | 0 | 0 | 2 | 0 | 1 |
Екатерина Минеева | 10 | 10 | 5 | 8 | 10 | 10 | 10 | 9 |
Антон Наумов | 10 | 5 | 2 | 3 | 0 | 5 | 0 | 3 |
Никита Нестеров | 7 | 3 | 3 | 0 | 2 | 7 | 10 | 5 |
Олег Николаев | 5 | 0 | 0 | 0 | 0 | 2 | 0 | 1 |
Евгений Правда | 10 | 10 | 10 | 9 | 10 | 10 | 10 | 10 |
Александр Рудь | 7 | 5 | 0 | 2 | 0 | 2 | 0 | 2 |
Михаил Флоринский | 9 | 9 | 5 | 5 | 3 | 6 | 10 | 7 |
Александр Чернявский | 10 | 10 | 7 | 8 | 9 | 10 | 10 | 9 |
Антон Чернявский | 10 | 10 | 8 | 8 | 9 | 10 | 7 | 9 |
Аудиторная работа
Студенты | Сортировки | Динамическое программирование | Число кратчайших путей | Графы | Апрельский тест |
---|---|---|---|---|---|
Иван Аустер | 5/6 | 2/2 | 0/1 | 2/3 | 3 |
Валерий Батурин | 6/6 | 0/2 | 1/1 | 1/3 | 2 |
Сергей Горбачев | 5/6 | 2/2 | 1/1 | 3/3 | 9,5 |
Евгений Мещеряков | 3/6 | 0/2 | 0/1 | 0/3 | 1 |
Екатерина Минеева | 6/6 | 2/2 | 1/1 | 3/3 | 7 |
Антон Наумов | 6/6 | 1/2 | 0/1 | 0/3 | 10 |
Никита Нестеров | 4/6 | 0/2 | 1/1 | 2/3 | 9 |
Олег Николаев | 2/6 | 0/2 | 0/1 | 0/3 | 6 |
Евгений Правда | 6/6 | 2/2 | 1/1 | 5/3 | 8 |
Александр Рудь | 5/6 | 0/2 | 0/1 | 0/3 | 3,5 |
Михаил Флоринский | 5/6 | 1/2 | 0/1 | 1/3 | 7,5 |
Александр Чернявский | 6/6 | 2/2 | 1/1 | 4/3 | 9,5 |
Антон Чернявский | 5/6 | 2/2 | 1/1 | 4/3 | 7,5 |