Алгоритмы и структуры данных. Подгруппа 101-1 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Результаты контрольной)
(→‎Текущие результаты)
 
(не показаны 54 промежуточные версии 2 участников)
Строка 7: Строка 7:
 
# Динамическое программирование
 
# Динамическое программирование
 
# Контекстно-свободные грамматики
 
# Контекстно-свободные грамматики
−
 
+
# Симплекс-метод
−
Планы на будущее:
+
# Потоки, динамические деревья, splay-деревья
 +
# Хеширование
 +
# Жадные алгоритмы
 +
# Вероятностные алгоритмы
 
# Конечные автоматы
 
# Конечные автоматы
 +
# Компиляторы
  
 
=== Введение ===
 
=== Введение ===
Строка 54: Строка 58:
 
Ссылка на контест:<br>
 
Ссылка на контест:<br>
 
https://official.contest.yandex.ru/contest/1085/<br>
 
https://official.contest.yandex.ru/contest/1085/<br>
−
Вновь половину балов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.<br>
+
Вновь половину баллов вы получите за сдачу задач в контест, а вторую половину - за прохождение ревью.<br>
 
Не затягивайте с ним, потому что я физически не успею проверить вас всех в конце семестра!<br>
 
Не затягивайте с ним, потому что я физически не успею проверить вас всех в конце семестра!<br>
  
 
Всего решить надо три задачи: 1-2 (количество путей), 2-2 (maze) и 3 (segments).
 
Всего решить надо три задачи: 1-2 (количество путей), 2-2 (maze) и 3 (segments).
 +
 +
=== Третье домашнее задание ===
 +
Сроки проведения: с 23:00 19 апреля по 23:00 4 мая.<br>
 +
Сроки сдачи ревью: c 23:00 4 мая по 23:00 23 мая.<br>
 +
Ваш номер варианта - это номер в алфавите третьей буквы вашей фамилии, взятый по модулю два и увеличенный на 1. Например, у меня фамилия меЛьничук - 13-я буква, значит, у меня второй вариант.<br>
 +
Третью задачу необходимо снабдить доказательством корректности алгоритма. Коммитить его надо вместе с кодом в svn.<br>
 +
Ссылка на контест:<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/6 || 3/3 || || ||  || || ||
+
| 2 || Деркач || Денис || Анатольевич || 5/5 || 3/3 || 4/4 || 2/2 || 1/0 || 7 || 7 || 7
 
|-
 
|-
−
| 3 || Исхаков || Тимур || Рашидович || 6/6 || 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/6 без ревью ||  || ||  || || || ||
+
| 5 || Мельниченко || Пётр || Валерьевич || 4/0 ||  || 2/2 ||  || 2/0 || 4 || 8 || 5
 
|-
 
|-
−
| 6 || Носков || Степан || Алексеевич || 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 || ||  ||  || || ||
+
| 8 || Пролеев || Лев || Николаевич || 6/6 || 3/3 || 4/4 || 3/3 || 2/0 || 9 || 10 || 9
 
|-
 
|-
−
| 9 || Рябушев || Антон || Федорович || 6/6 || 3/3 без ревью  || || ||  || || ||
+
| 9 || Рябушев || Антон || Федорович || 6/6 || 3/2 || 3/0 || 1/0 || 1.5/0 || 6 || 9 || 7
 
|-
 
|-
−
| 10 || Сайранов || Айдар || Дамирович || 6/6 без ревью || 3/3 без ревью  ||  ||  ||  || || ||   
+
| 10 || Сайранов || Айдар || Дамирович || 6/0 || 3/1 || 4/4 ||  || 1/0 || 6 || неявка ||   
 
|-
 
|-
−
| 11 || Святокум || Полина || Олеговна || 6/6 без ревью || 3/3 || || ||  || || ||
+
| 11 || Святокум || Полина || Олеговна || 6/6 || 3/3 || 3/3 || 2/1 || 2/0 || 8 || 8 || 8
 
|-
 
|-
−
| 12 || Султанов || Арсен || Русланович || 6/6 без ревью ||  || || ||  || || ||
+
| 12 || Султанов || Арсен || Русланович || 6/0 ||  || 1/0 || 1/1 || 1.5/0 || 2 || 4 || 3
 
|-
 
|-
−
| 13 || Трофимов || Иван || Андреевич || 6/6 без ревью ||  || || ||  || || ||   
+
| 13 || Трофимов || Иван || Андреевич || 6/0 ||  || 3/0 || 2/0 ||  || 4 || неявка ||   
 
|}
 
|}
  
Строка 96: Строка 128:
 
! !!Фамилия !! Имя !! Отчество !! 1 !! 2 !! 3 !! 4 !! 5
 
! !!Фамилия !! Имя !! Отчество !! 1 !! 2 !! 3 !! 4 !! 5
 
|-
 
|-
−
| 1 || Гущенко-Чеверда || Иван || Ильич || || || || ||
+
| 1 || Гущенко-Чеверда || Иван || Ильич || + || + || + || + || +
 
|-
 
|-
−
| 2 || Деркач || Денис || Анатольевич || || || || ||   
+
| 2 || Деркач || Денис || Анатольевич || - || + || +- || + || +    
 
|-
 
|-
−
| 3 || Исхаков || Тимур || Рашидович || || || || ||  
+
| 3 || Исхаков || Тимур || Рашидович || + || - || + || + || + 
 
|-
 
|-
−
| 4 || Кузнецов || Георгий || Алексеевич || || || || ||   
+
| 4 || Кузнецов || Георгий || Алексеевич || - || - || - || + || +-    
 
|-
 
|-
−
| 5 || Мельниченко || Пётр || Валерьевич || || || || ||  
+
| 5 || Мельниченко || Пётр || Валерьевич || + || + || + || + || - 
 
|-
 
|-
 
| 6 || Носков || Степан || Алексеевич || - || + || + || + ||   
 
| 6 || Носков || Степан || Алексеевич || - || + || + || + ||   
 
|-
 
|-
−
| 7 || Пособин || Глеб || Игоревич || || || || ||  
+
| 7 || Пособин || Глеб || Игоревич || + || + || + || + || + 
 
|-
 
|-
−
| 8 || Пролеев || Лев || Николаевич || || || || ||  
+
| 8 || Пролеев || Лев || Николаевич || + || + || + || + || +- 
 
|-
 
|-
−
| 9 || Рябушев || Антон || Федорович || || || || ||   
+
| 9 || Рябушев || Антон || Федорович || - || + || + || + ||   
 
|-
 
|-
−
| 10 || Сайранов || Айдар || Дамирович || || || || ||
+
| 10 || Сайранов || Айдар || Дамирович || + || + || + || + || +
 
|-
 
|-
 
| 11 || Святокум || Полина || Олеговна || + || + || + || + ||   
 
| 11 || Святокум || Полина || Олеговна || + || + || + || + ||   
Строка 120: Строка 152:
 
| 12 || Султанов || Арсен || Русланович || ||  ||  ||  ||  
 
| 12 || Султанов || Арсен || Русланович || ||  ||  ||  ||  
 
|-
 
|-
−
| 13 || Трофимов || Иван || Андреевич || || || || ||  
+
| 13 || Трофимов || Иван || Андреевич || + || +- || +- || + || +
 
|}
 
|}
  
Строка 127: Строка 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. Сортировки и гарантированный n log n для qsort
  4. Метод ветвей и границ и общее понятие метрики качества
  5. Быстрое преобразование Фурье
  6. Динамическое программирование
  7. Контекстно-свободные грамматики
  8. Симплекс-метод
  9. Потоки, динамические деревья, splay-деревья
  10. Хеширование
  11. Жадные алгоритмы
  12. Вероятностные алгоритмы
  13. Конечные автоматы
  14. Компиляторы

Введение

В течение семестра мы будем обсуждать алгоритмы решения различных задач.
Начнем мы с совсем простой задачи на сортировку про футбольную команду.
На ее примере мы научимся

  1. Работать с системой контроля версий
  2. Писать тесты к вашим программам

Очередность сдачи задач

  1. Алгоритм, обоснование корректности, оценки времени и памяти на почту finisterra@yandex.ru
  2. Сдача задачи в Яндекс.Контест
  3. Правка интерфейса по результатам ревью
  4. Правка кода по результатам ревью

Теория

Теорию необходимо отправлять в 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 баллов экзамена.

Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных._Подгруппа_101-1&oldid=16818»