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

Версия 13:19, 3 марта 2015

Общая информация

Семинары ведет Умнов Алексей

Часы консультаций:

• Понедельник: 15:45 - 16:30
• Среда: 18:15 - 19:00

Место: ауд. 619.

Не забывайте писать тесты к задачам (как обсуждалось на семинарах) и указывать версию компилятора/интерпретатора.

Стиль кода

Код должен соответствовать стайлгайду, принятому на курсе Основы_и_методологии_программирования.

Также есть дополнительные правила:

• Запрещено использовать глобальные переменные.
• Весь содержательный (с точки зрения алгоритмов) код нужно выносить в отдельные функции. В функции main (или в глобальном пространстве имен для питона) можно только считывать и печатать данные, делать преобразования их формата и вызывать содержательные функции.

Тестирование программ

Для тестирования своих программ перед отправкой в контест можно пользоваться программой.

Как работать с программой и как писать хорошие тесты.

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

Правила ревью

Алгоритм сдачи задачи такой:

1. Сдайте задачу в контест.

2. Отправьте исходный код (в точности тот, что был в контесте) на ревью с помощью rb.cs.hse.ru.

В заголовке ревью (Summary) напишите "Дз<номер>.<буква/номер задачи> <подгруппа> <Фамилия Имя>", например "Дз1.A 123-1 Умнов Алексей". Ревьювером укажите "alexeyum". В поле Description можно написать что угодно.

Не забудьте нажать "Publish", чтобы отправить запрос на ревью.

3. Дождитесь ответа на ревью. Если ответа нет в течение 5 дней, то пишите об этом на alexeyum@gmail.com.

4. Если вы получили "Ship It", значит задача сдана. Если нет, то необходимо сделать все указанные в ревью исправления.

5. Сдайте исправленный код в контест, а потом загрузите его на ревью. Перейдите к шагу 3.

6. Когда задача сдана и вопросов больше нет, нужно закрыть ревью ("Close" в правом верхнем углу).

Для ревью открыли новый контест. Новые задачи туда сдавать нельзя.

Если вы ни разу не заходили на rb.cs.hse.ru, то нужно использовать логин из контеста и следующий пароль: "BEdp84laNx". После входа нужно сразу же поменять пароль на новый.

Задание 1

Помимо сдачи задания в контест (см. главную страницу), необходимо также пройти ревью по всем задачам.

Решение можно писать на C++ или на Python. Код должен соответствовать стайлгайду, принятому на курсе Основы_и_методологии_программирования.

За каждую задачу в задании можно получить до 10/6 баллов. Для этого нужно сдать решение в контест и пройти полное ревью. Если ревью пройдено частично, то за задачу будет начислен неполный балл.

Итоговая сумма будет округляться вверх.

Ревью нужно прислать не позже 19.02 и сделать все исправления в течение недели с первого ответа. Если у вас неверно работает задача F (после добавления новых тестов), то ее нужно исправить до 22.02.

Задание 2

Для допуска к этому заданию необходимо

• сдать одну задачу в контест и пройти ревью.
• на семинаре сдать задачу про сильную связность

Контест.

Если вы пишите программы на питоне, то может быть удобным воспользоваться функцией setrecursionlimit из модуля sys для установки максимально допустимой глубины рекурсии. По умолчанию она довольно маленькая для этих задач и может привести к ошибкам.

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

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

Решение можно писать на C++ или на Python. Код должен соответствовать стайлгайду.

Ревью по этому домашнему заданию будет проходить по почте, без использования rb.cs.hse.ru. (Если вы уже прислали задачу на rb.cs.hse.ru, то ничего страшного, проверим через нее.)

При отправке задачи на ревью в теме письма пишите:

"АиСД - Дз<Номер дз>.<номер задачи> - <Подгруппа> <Фамилия> <Имя>".

Пример: "АиСД - Дз2.1 - 123-1 Умнов Алексей".

Для задачи на динамическое программирование пишите вместо номера задачи "ДП1" или "ДП2".

В письме укажите номер последней успешной посылки в контест и прикрепите файл с кодом этой посылки.

Письмо отправляйте на адрес вашего проверяющего. Распределение проверяющих. Распределение будет сделано в ближайшее время.

Семинары

Решения задач с семинаров

Код для задач по программированию можно присылать на адрес alexeyum@gmail.com.

Тему письма оформляйте по такому шаблону (иначе письмо может потеряться):

"АиСД - <Номер семинара>.<номер задачи> - <Подгруппа> <Фамилия> <Имя>".

Пример: "АиСД - 2.1 - 123-1 Умнов Алексей".

Семинар 0 (12.01). Ханойские башни.

Разбиралась задача о Ханойских башнях, ее рекурсивное решение, подсчитывалось время работы и доказывалась оптимальность. Также предлагалось запрограммировать этот алгоритм на любом языке.

Семинар 1 (14.01 и 15.01). Сортировка слиянием.

Разбирался алгоритм сортировки слиянием и были предложены задачи.

Семинар 2 (19.01). Двоичный поиск. O-символика.

Разбирались O-обозначения, были предложены задачи.

Семинар 3 (21.01 и 22.01). O-символика. Разные задачи

Разбирался алгоритм быстрой сортировки. Были предложены задачи.

Семинар 4 (26.01). Рекуррентные соотношения

Разбиралась основная теорема о рекуррентных соотношениях и примеры ее применения. Были предложены задачи.

Семинар 5 (28.01 и 29.01).

Разбирались задачи с прошлых семинаров.

Семинар 6 (02.02)

Разбирался алгоритм выбора порядковой статистики и алгоритм быстрого возведения в степень. Также разбирались задачи с прошлых семинаров.

Семинар 7 (04.02 и 05.02). Динамическое программирование.

Разбиралась задача о взвешенных интервалах и были предложены задачи.

Семинар 8 (09.02). Динамическое программирование 2.

Были предложены задачи.

Семинар 9 (11.02 и 12.02).

Было подробно разобрано тестирование программ и несколько старых задач.

Контест с заданиями для допуска (нужно решить хотя бы одну задачу).

Семинар 10 (16.02)

Разбирались задачи с прошлых семинаров (динамическое программирование), работу с графами, поиск в глубину. Упражнения на дом: написать программу, выполняющую поиск в глубину и программу, выполняющую поиск в ширину.

Семинар 11 (18.02 и 19.02)

Разбирался алгоритм поиска в ширину, алгоритмы проверки связности.

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

Задачи семинара: ссылка.

Семинар 12 (26.02 и 27.02)

Происходила сдача задания для допуска к дз 2. Разбирался алгоритм топологической сортировки и некоторые старые задачи.

Семинар 13 (02.03)

Разбирали алгоритм поиска компонент сильной связности в ориентированном графе и алгоритм Беллмана-Форда