Алгоритмы и структуры данных. Подгруппа 101-1 — различия между версиями
Tiunovas (обсуждение | вклад) |
Melnichuk (обсуждение | вклад) (→Текущие результаты) |
||
| (не показано 38 промежуточных версии 2 участников) | |||
| Строка 7: | Строка 7: | ||
# Динамическое программирование | # Динамическое программирование | ||
# Контекстно-свободные грамматики | # Контекстно-свободные грамматики | ||
| + | # Симплекс-метод | ||
| + | # Потоки, динамические деревья, splay-деревья | ||
# Хеширование | # Хеширование | ||
| − | + | # Жадные алгоритмы | |
| − | + | # Вероятностные алгоритмы | |
# Конечные автоматы | # Конечные автоматы | ||
| + | # Компиляторы | ||
=== Введение === | === Введение === | ||
| Строка 55: | Строка 58: | ||
Ссылка на контест:<br> | Ссылка на контест:<br> | ||
https://official.contest.yandex.ru/contest/1085/<br> | https://official.contest.yandex.ru/contest/1085/<br> | ||
| − | Вновь половину | + | Вновь половину баллов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.<br> |
Не затягивайте с ним, потому что я физически не успею проверить вас всех в конце семестра!<br> | Не затягивайте с ним, потому что я физически не успею проверить вас всех в конце семестра!<br> | ||
| Строка 62: | Строка 65: | ||
=== Третье домашнее задание === | === Третье домашнее задание === | ||
Сроки проведения: с 23:00 19 апреля по 23:00 4 мая.<br> | Сроки проведения: с 23:00 19 апреля по 23:00 4 мая.<br> | ||
| − | Сроки сдачи ревью: c 23:00 4 мая по 23:00 | + | Сроки сдачи ревью: c 23:00 4 мая по 23:00 23 мая.<br> |
Ваш номер варианта - это номер в алфавите третьей буквы вашей фамилии, взятый по модулю два и увеличенный на 1. Например, у меня фамилия меЛьничук - 13-я буква, значит, у меня второй вариант.<br> | Ваш номер варианта - это номер в алфавите третьей буквы вашей фамилии, взятый по модулю два и увеличенный на 1. Например, у меня фамилия меЛьничук - 13-я буква, значит, у меня второй вариант.<br> | ||
Третью задачу необходимо снабдить доказательством корректности алгоритма. Коммитить его надо вместе с кодом в svn.<br> | Третью задачу необходимо снабдить доказательством корректности алгоритма. Коммитить его надо вместе с кодом в svn.<br> | ||
Ссылка на контест:<br> | Ссылка на контест:<br> | ||
https://official.contest.yandex.ru/contest/1196/enter/<br> | https://official.contest.yandex.ru/contest/1196/enter/<br> | ||
| − | Половину | + | Половину баллов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.<br> |
| + | |||
| + | === Четвертое домашнее задание === | ||
| + | Сроки проведения: с 21:00 26 мая по 21:00 9 июня.<br> | ||
| + | Сроки сдачи ревью: с 21:00 9 июня по 21:00 23 июня (конец может поменяться из-за сессии и требований учебной части, так что проходите поскорее).<br> | ||
| + | Обязательны первые три задачи. Первые 10 человек, решившие 4-ую задачу, могут не решать одну из первых трех.<br> | ||
| + | Ссылка на контест:<br> | ||
| + | https://official.contest.yandex.ru/contest/1259/enter/<br> | ||
| + | Половину баллов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.<br> | ||
| + | |||
| + | === Пятое домашнее задание === | ||
| + | Сроки проведения: с 00:00 5 июня по 00:00 25 июня.<br> | ||
| + | Обязательны обе задачи.<br> | ||
| + | Ссылка на контест:<br> | ||
| + | https://official.contest.yandex.ru/contest/1271/enter/<br> | ||
| + | Ревью по этой работе не проводится, но я надеюсь, что читаемый код вам писать уже проще, чем олимпиадный.<br> | ||
| + | Вместо ревью вам необходимо решить и сдать набор теоретических задач<br> | ||
| + | https://yadi.sk/i/G3lLFT65h9pb8<br> | ||
=== Текущие результаты === | === Текущие результаты === | ||
| + | Число перед чертой - это число сданных задач, число после черты - число задач, по которым пройдено ревью. | ||
| + | |||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
| − | ! !!Фамилия !! Имя !! Отчество !! ДЗ-1 !! ДЗ-2 !! ДЗ-3 !! ДЗ-4 !! ДЗ-5 !! Accum !! Exam !! Sum | + | ! !!Фамилия !! Имя !! Отчество !! ДЗ-1 (6) !! ДЗ-2 (3) !! ДЗ-3 (4) !! ДЗ-4 (3) !! ДЗ-5 (2/3) !! Accum !! Exam !! Sum |
|- | |- | ||
| − | | 1 || Гущенко-Чеверда || Иван || Ильич || 6/6 || 3/3 || | + | | 1 || Гущенко-Чеверда || Иван || Ильич || 6/6 || 3/3 || 4/4 || 1/1 || 1.5/2.5 || 9 || 9 || 9 |
|- | |- | ||
| − | | 2 || Деркач || Денис || Анатольевич || 5/ | + | | 2 || Деркач || Денис || Анатольевич || 5/5 || 3/3 || 4/4 || 2/2 || 1/0 || 7 || 7 || 7 |
|- | |- | ||
| − | | 3 || Исхаков || Тимур || Рашидович || 6/6 || 3/3 || 3/3 | + | | 3 || Исхаков || Тимур || Рашидович || 6/6 || 3/3 || 3/3 || 2/2 || 2/3 || 9 || 9 || 9 |
|- | |- | ||
| − | | 4 || Кузнецов || Георгий || Алексеевич || 6/6 | + | | 4 || Кузнецов || Георгий || Алексеевич || 6/6 || 2/2 || 2/0 || || 1.5/3 || 5 || 3 || 4 |
|- | |- | ||
| − | | 5 || Мельниченко || Пётр || Валерьевич || 4/ | + | | 5 || Мельниченко || Пётр || Валерьевич || 4/0 || || 2/2 || || 2/0 || 4 || 8 || 5 |
|- | |- | ||
| − | | 6 || Носков || Степан || Алексеевич || 6/ | + | | 6 || Носков || Степан || Алексеевич || 6/0 || 3/0 || 3/0 || 1/0 || 1/0 || 4 || 7 || 5 |
|- | |- | ||
| − | | 7 || Пособин || Глеб || Игоревич || 6/6 || 3/3 || | + | | 7 || Пособин || Глеб || Игоревич || 6/6 || 3/3 || 4/4 || 3/3 || 2/3 || 10 || 10 || 10 |
|- | |- | ||
| − | | 8 || Пролеев || Лев || Николаевич || 6/6 || 3/3 || 3/3 | + | | 8 || Пролеев || Лев || Николаевич || 6/6 || 3/3 || 4/4 || 3/3 || 2/0 || 9 || 10 || 9 |
|- | |- | ||
| − | | 9 || Рябушев || Антон || Федорович || 6/6 || 3/ | + | | 9 || Рябушев || Антон || Федорович || 6/6 || 3/2 || 3/0 || 1/0 || 1.5/0 || 6 || 9 || 7 |
|- | |- | ||
| − | | 10 || Сайранов || Айдар || Дамирович || 6/ | + | | 10 || Сайранов || Айдар || Дамирович || 6/0 || 3/1 || 4/4 || || 1/0 || 6 || неявка || |
|- | |- | ||
| − | | 11 || Святокум || Полина || Олеговна || 6/6 | + | | 11 || Святокум || Полина || Олеговна || 6/6 || 3/3 || 3/3 || 2/1 || 2/0 || 8 || 8 || 8 |
|- | |- | ||
| − | | 12 || Султанов || Арсен || Русланович || 6/ | + | | 12 || Султанов || Арсен || Русланович || 6/0 || || 1/0 || 1/1 || 1.5/0 || 2 || 4 || 3 |
|- | |- | ||
| − | | 13 || Трофимов || Иван || Андреевич || 6/ | + | | 13 || Трофимов || Иван || Андреевич || 6/0 || || 3/0 || 2/0 || || 4 || неявка || |
|} | |} | ||
| Строка 137: | Строка 159: | ||
===Набор задач для подготовки к контрольной=== | ===Набор задач для подготовки к контрольной=== | ||
https://yadi.sk/i/gVo0ymT4fduLJ | https://yadi.sk/i/gVo0ymT4fduLJ | ||
| + | |||
| + | ===Текущие наработки по компилятору=== | ||
| + | https://yadi.sk/d/f-GdraEHgzcLD | ||
| + | |||
| + | ===Экзамен=== | ||
| + | Экзамен по курсу будет состоять из двух частей.<br> | ||
| + | |||
| + | Первая часть - практическая и будет проходить на последнем семинаре по курсу.<br> | ||
| + | Вам будет предложено решить одну задачу в системе Яндекс.Контест.<br> | ||
| + | За эту часть экзамена вы получаете 2 из 10 баллов экзамена.<br> | ||
| + | Тренировочный контест, настроенный так же, как и экзаменационный:<br> | ||
| + | https://official.contest.yandex.ru/contest/1282/enter/<br> | ||
| + | Контест практической части экзамена:<br> | ||
| + | https://official.contest.yandex.ru/contest/1280/enter/<br> | ||
| + | |||
| + | Вторая часть - теоретическая и будет проходить 29ого июня.<br> | ||
| + | При подготовке можно пользоваться любыми бумажными материалами.<br> | ||
| + | Электронными устройствами пользоваться запрещено.<br> | ||
| + | Билет будет состоять из вопроса по теории и задачи.<br> | ||
| + | Для получения максимальной оценки необходимо будет ответить на дополнительные вопросы.<br> | ||
| + | За эту часть экзамена вы получаете 8 из 10 баллов экзамена.<br> | ||
Текущая версия на 13:26, 2 июля 2015
Содержание
- 1 Примерный план семинаров
- 2 Введение
- 3 Очередность сдачи задач
- 4 Теория
- 5 Яндекс.Контест
- 6 Репозиторий
- 7 Первое домашнее задание
- 8 Второе домашнее задание
- 9 Третье домашнее задание
- 10 Четвертое домашнее задание
- 11 Пятое домашнее задание
- 12 Текущие результаты
- 13 Результаты контрольной
- 14 Набор задач для подготовки к контрольной
- 15 Текущие наработки по компилятору
- 16 Экзамен
Примерный план семинаров
- Основы проектирования и написание интерфейсов
- Тестирование программ
- Сортировки и гарантированный n log n для qsort
- Метод ветвей и границ и общее понятие метрики качества
- Быстрое преобразование Фурье
- Динамическое программирование
- Контекстно-свободные грамматики
- Симплекс-метод
- Потоки, динамические деревья, splay-деревья
- Хеширование
- Жадные алгоритмы
- Вероятностные алгоритмы
- Конечные автоматы
- Компиляторы
Введение
В течение семестра мы будем обсуждать алгоритмы решения различных задач.
Начнем мы с совсем простой задачи на сортировку про футбольную команду.
На ее примере мы научимся
- Работать с системой контроля версий
- Писать тесты к вашим программам
Очередность сдачи задач
- Алгоритм, обоснование корректности, оценки времени и памяти на почту finisterra@yandex.ru
- Сдача задачи в Яндекс.Контест
- Правка интерфейса по результатам ревью
- Правка кода по результатам ревью
Теория
Теорию необходимо отправлять в pdf, учитесь пользоваться ТеХом.
Яндекс.Контест
Контест доступен по адресу
https://official.contest.yandex.ru/contest/1005/
Репозиторий
Наш проект на code.google.com живет тут
https://code.google.com/p/1011-group-trunk/
Для работы с ним требуется аккаунт Google.
Посмотреть пароль к системе code.google.com можно на странице
https://code.google.com/hosting/settings
Репозиторий доступен по адресу
svn checkout https://1011-group-trunk.googlecode.com/svn/trunk/ 1011-group-trunk --username username --password password
Где вместо username надо подставить имя вашего аккаунта, а вместо password - пароль от системы code.google.com
Первое домашнее задание
Сроки проведения: с 26 января по 9 февраля.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1002/
Сдача задач состоит из двух этапов: решения задачи в системе и прохождения ревью.
Сдавать задачи надо в контест в системе Яндекс.Контест, а ревью проходится с помощью code.google.com.
Второе домашнее задание
Сроки проведения: с 17:00 24 февраля по 23:59 9 марта.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1085/
Вновь половину баллов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.
Не затягивайте с ним, потому что я физически не успею проверить вас всех в конце семестра!
Всего решить надо три задачи: 1-2 (количество путей), 2-2 (maze) и 3 (segments).
Третье домашнее задание
Сроки проведения: с 23:00 19 апреля по 23:00 4 мая.
Сроки сдачи ревью: c 23:00 4 мая по 23:00 23 мая.
Ваш номер варианта - это номер в алфавите третьей буквы вашей фамилии, взятый по модулю два и увеличенный на 1. Например, у меня фамилия меЛьничук - 13-я буква, значит, у меня второй вариант.
Третью задачу необходимо снабдить доказательством корректности алгоритма. Коммитить его надо вместе с кодом в svn.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1196/enter/
Половину баллов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.
Четвертое домашнее задание
Сроки проведения: с 21:00 26 мая по 21:00 9 июня.
Сроки сдачи ревью: с 21:00 9 июня по 21:00 23 июня (конец может поменяться из-за сессии и требований учебной части, так что проходите поскорее).
Обязательны первые три задачи. Первые 10 человек, решившие 4-ую задачу, могут не решать одну из первых трех.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1259/enter/
Половину баллов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.
Пятое домашнее задание
Сроки проведения: с 00:00 5 июня по 00:00 25 июня.
Обязательны обе задачи.
Ссылка на контест:
https://official.contest.yandex.ru/contest/1271/enter/
Ревью по этой работе не проводится, но я надеюсь, что читаемый код вам писать уже проще, чем олимпиадный.
Вместо ревью вам необходимо решить и сдать набор теоретических задач
https://yadi.sk/i/G3lLFT65h9pb8
Текущие результаты
Число перед чертой - это число сданных задач, число после черты - число задач, по которым пройдено ревью.
| Фамилия | Имя | Отчество | ДЗ-1 (6) | ДЗ-2 (3) | ДЗ-3 (4) | ДЗ-4 (3) | ДЗ-5 (2/3) | Accum | Exam | Sum | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | Гущенко-Чеверда | Иван | Ильич | 6/6 | 3/3 | 4/4 | 1/1 | 1.5/2.5 | 9 | 9 | 9 |
| 2 | Деркач | Денис | Анатольевич | 5/5 | 3/3 | 4/4 | 2/2 | 1/0 | 7 | 7 | 7 |
| 3 | Исхаков | Тимур | Рашидович | 6/6 | 3/3 | 3/3 | 2/2 | 2/3 | 9 | 9 | 9 |
| 4 | Кузнецов | Георгий | Алексеевич | 6/6 | 2/2 | 2/0 | 1.5/3 | 5 | 3 | 4 | |
| 5 | Мельниченко | Пётр | Валерьевич | 4/0 | 2/2 | 2/0 | 4 | 8 | 5 | ||
| 6 | Носков | Степан | Алексеевич | 6/0 | 3/0 | 3/0 | 1/0 | 1/0 | 4 | 7 | 5 |
| 7 | Пособин | Глеб | Игоревич | 6/6 | 3/3 | 4/4 | 3/3 | 2/3 | 10 | 10 | 10 |
| 8 | Пролеев | Лев | Николаевич | 6/6 | 3/3 | 4/4 | 3/3 | 2/0 | 9 | 10 | 9 |
| 9 | Рябушев | Антон | Федорович | 6/6 | 3/2 | 3/0 | 1/0 | 1.5/0 | 6 | 9 | 7 |
| 10 | Сайранов | Айдар | Дамирович | 6/0 | 3/1 | 4/4 | 1/0 | 6 | неявка | ||
| 11 | Святокум | Полина | Олеговна | 6/6 | 3/3 | 3/3 | 2/1 | 2/0 | 8 | 8 | 8 |
| 12 | Султанов | Арсен | Русланович | 6/0 | 1/0 | 1/1 | 1.5/0 | 2 | 4 | 3 | |
| 13 | Трофимов | Иван | Андреевич | 6/0 | 3/0 | 2/0 | 4 | неявка |
Результаты контрольной
| Фамилия | Имя | Отчество | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|---|---|
| 1 | Гущенко-Чеверда | Иван | Ильич | + | + | + | + | + |
| 2 | Деркач | Денис | Анатольевич | - | + | +- | + | + |
| 3 | Исхаков | Тимур | Рашидович | + | - | + | + | + |
| 4 | Кузнецов | Георгий | Алексеевич | - | - | - | + | +- |
| 5 | Мельниченко | Пётр | Валерьевич | + | + | + | + | - |
| 6 | Носков | Степан | Алексеевич | - | + | + | + | |
| 7 | Пособин | Глеб | Игоревич | + | + | + | + | + |
| 8 | Пролеев | Лев | Николаевич | + | + | + | + | +- |
| 9 | Рябушев | Антон | Федорович | - | + | + | + | |
| 10 | Сайранов | Айдар | Дамирович | + | + | + | + | + |
| 11 | Святокум | Полина | Олеговна | + | + | + | + | |
| 12 | Султанов | Арсен | Русланович | |||||
| 13 | Трофимов | Иван | Андреевич | + | +- | +- | + | + |
Если видите какие-то ошибки в заполнении таблицы, сообщайте, я мог что-то упустить.
Набор задач для подготовки к контрольной
https://yadi.sk/i/gVo0ymT4fduLJ
Текущие наработки по компилятору
https://yadi.sk/d/f-GdraEHgzcLD
Экзамен
Экзамен по курсу будет состоять из двух частей.
Первая часть - практическая и будет проходить на последнем семинаре по курсу.
Вам будет предложено решить одну задачу в системе Яндекс.Контест.
За эту часть экзамена вы получаете 2 из 10 баллов экзамена.
Тренировочный контест, настроенный так же, как и экзаменационный:
https://official.contest.yandex.ru/contest/1282/enter/
Контест практической части экзамена:
https://official.contest.yandex.ru/contest/1280/enter/
Вторая часть - теоретическая и будет проходить 29ого июня.
При подготовке можно пользоваться любыми бумажными материалами.
Электронными устройствами пользоваться запрещено.
Билет будет состоять из вопроса по теории и задачи.
Для получения максимальной оценки необходимо будет ответить на дополнительные вопросы.
За эту часть экзамена вы получаете 8 из 10 баллов экзамена.
