Задания

 
  • Задание 1       Cеминар 1   
  • Задание 2       Cеминар 2   
  • Задание 3       Cеминар 3   
  • Задание 4       Cеминар 4   
  • Задание 5       Cеминар 5   
  • Задание 6       Cеминар 6   
  • Задание 7       Cеминар 7   
  • Задание 8       Cеминар 8    (дедлайн по домашнему заданию — неделя после нерабочей)
  • Задание 9       Cеминар 9   
  • Задание 10     Cеминар 10 
  • Задание 11     Cеминар 11 
  • Задание 12     Cеминар 12 
  • Cеминар 13   
  • Cеминар 14   
  • Задание 13-14   (статус задания определяет семинарист)

Материалы курса

  • План-конспект лекций   (последнее обновление 10 марта)
  • Заметки и примеры к лекциям   (последнее обновление 25 февраля)
  • Программа курса доступна по ссылке .
  • Группа на Codeforces с контестами по темам курса (дополнительный материал)

Записи онлайн-занятий

  • Семинар 7 , блокнот 
  • Лекция 8 , Красно-чёрные деревья , Хэширование , Амортизационный анализ 
  • Семинар 8 , блокнот 
  • Лекция 9  (исправленная! Отдельное исправление ), блокнот 
  • Семинар 9 , блокнот 
  • Лекция 10 , блокнот 
  • Семинар 10 , блокнот 
  • Лекция 11 , блокнот 
  • Семинар 11 , блокнот 
  • Лекция 12 , блокнот 
  • Семинар 12 , блокнот 
  • Лекция 13 , блокнот 
  • Семинар 13 , блокнот 
  • Лекция 14 , блокнот 
 

Пересдача-2


24 Сентября 2020

Пересдача состоится в пятницу 2 октября, 13:55, 907 КПМ. Формат пересдачи — письменный тест, в котором будут в том числе и задачи на построение алгоритмов, и задачи, требующие обоснованных ответов.

 

Результаты пересдачи


18 Сентября 2020

Тест пересдачи переведён в режим показа результатов. Пересдача сдана на удовл(3), если набрано не менее 4,5 баллов. Все вопросы, кроме второго оцениваются в 0 или 1; за второй вопрос можно получить 0,5 балла, если выбраны только ответы 1 и 4. Оценка удовл(4) ставится начиная с 7,5 баллов. Если остались сомнения по полученной оценке, задавайте вопросы мне ВКонтакте или по почте. Внимание! В система считаются только полные баллы, наличие +0,5 балла проверьте самостоятельно.

 

Пересдача 18.09


14 Сентября 2020

Пересдача в пятницу 18.09 начнётся в 17:00. Она будет проходить с использованием системы прокторинга в тестирующей системе. Продолжительность пересдачи 1 час. Токены разосланы по почте на адреса, которые  я получил от кафедры. Если вы не получили письмо с токеном — сообщите мне об этом. Инструкции по работе с прокторингом аналогичны тем, что были на семестровой контрольной с поправкой на время (см. их ниже, например «Инструкция по прохождению теста посредством системы прокторинга»).

UPD:  На сайте  https://exams.mipt.ru/  нужно зайти в экзамен «Пересдача зачёта по дисциплине «Основные алгоритмы» (ФУПМ, бывший 1 курс)» и нажать кнопку «Начать экзамен».

 

Пересдача


29 Августа 2020

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

 

Пересдачи


21 Июля 2020

Пересдачи будут только в новом семестре (скорее всего с сентября). В конце августа пересдач не планируется.

 

Результаты теста


17 Мая 2020

Доступны результаты теста. Для их просмотра, введите свой токен (с двойкой на конце) на странице тестирующей системы

Если что-то пошло не так и вы отправили ответы в дополнительное время, то эти результаты можно посмотреть, приписав к своему токену суффикс "_late". Что делать с этими результатами — решает семинарист.

Если что-то пошло сильно не так, и вы не сдали тест по техническим причином (истечение времени на таймере и как следствие закрытие теста — не техническая причина), мы сможем восстановить ваши ответы с помощью видеозаписи с прокторинга — обращайтесь к семинаристу.

P.S. Если пересмотрев запись с прокторинга, мы обнаружим нарушения (списывание, шпаргалки и т.п.), тест будет анулирован. Если мы как-то ещё обнаружим факт списывания или покушение на списывание — тоже. Тоже самое может случиться, если мы обнаружим, что кто-то решил воспользоваться открытием системы тестирования для вбивания ответов после дедлайна (перед тем как это сделать, я сделал бэкап базы данных, в которой были сохранены все ответы, сданные вовремя). 

 

Тест


16 Мая 2020

Для того, чтобы приступить к тесту, зайдите в тестирующую систему и введите старый токен с приписанной в конец цифрой 2. Нажмите «начать тест» и ознакомьтесь с инструкцией.

 

Тест в субботу


15 Мая 2020

Напоминаю, что тест по алгоритмам завтра (в субботу) начнётся в 12:00! Не опаздывайте, при себе имейте разосланные токены, чистую бумагу и ничего запрещённого (шпаргалки и телефоны). Более подробные инструкции появятся в скором времени на этой странице.

P.S. Изучите инструкции ниже!

 

Результаты пробного теста


14 Мая 2020

Для просмотров результатов пробного теста зайдите в тестирующую систему по своему токену. Сохраните токен — он понадобится для входа в тест в субботу. Никому не передавайте свой токен! Если вдруг вы уже это сделали, напишите мне и я поменяю ваш токен.

P.S. В случае неверного ответа на вопрос зелёным отмечены правильные выделения/не выделения, а красным неправильные.

 

Доступ в тестирующую систему


14 Мая 2020

Инструкции по доступу к тестирующей системе разосланы на почту, указанную в форме. Если Вы не получили письмо, проверьте папку Спам.

 

Инструкция по прохождению теста посредством системы прокторинга


13 Мая 2020

Публикую инструкцию от ответственного за прокторинг. Следуйте ей, чтобы получить доступ к системе прокторинга МФТИ (необходимо для прохождения теста!).  Пожалуйста, ознакомьтесь также с подробной инструкцией (для наших нужд потребуется только её часть). Для доступа к тесту требуется заполнить форму; система прокторинга будет использоваться только для контроля за самостоятельным выполнением теста и возможности связи студент-пеподаватель, сам тест будет на этом сайте (ссылка будет опубликована позже). 

Инструкция

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

За несколько дней до экзамена (как только увидите инструкцию):

  1. Открываем сайт https://exams.mipt.ru/
  2. Регистрируем учетную запись, если ее еще нет (учетная запись Abitu.net подойдет) Если после регистрации вы заходите на https://exams.mipt.ru/ и не видите списка разных экзаменов, значит вы указали не всю необходимую информацию в профиле. Дозаполняем ориентируясь на красные звездочки. 

  3. Находим на главной странице мероприятие с названием «ID 32699 ТЕСТИРОВАНИЕ СИСТЕМЫ ПРОКТОРИНГА ПЕРЕД КОНТРОЛЬНОЙ РАБОТОЙ ПО ОСНОВНЫМ АЛГОРИТМАМ» (проще через Ctrl + F). Нажимаем «Зарегистрироваться». Начинается процедура проверки. Выдаем все разрешения. Делимся всем экраном. Если во время проверки есть какие-либо красные предупреждения, пишем в группу в телеграм. https://t.me/genalgorithms

  4. Аналогично находим мероприятие «ID 32700 КОНТРОЛЬНАЯ РАБОТА ПО ДИСЦИПЛИНЕ «ОСНОВНЫЕ АЛГОРИТМЫ» (ФУПМ, 1 КУРС)». Регистрируемся проходим проверку. В случае проблем пишем в чат.

Четверг 14.05 в 18:35

  1. Открываем сайт https://exams.mipt.ru/ Находим на главной странице мероприятие с названием «ID 32699 ТЕСТИРОВАНИЕ СИСТЕМЫ ПРОКТОРИНГА ПЕРЕД КОНТРОЛЬНОЙ РАБОТОЙ ПО ОСНОВНЫМ АЛГОРИТМАМ» (проще через Ctrl + F). Нажимаем преступить к решению. Если зайдете в систему раньше, чем в 18:35, в контрольную вас перекинет автоматически в момент его начала.
  2. Приготовили зачетку (или паспорт) и ждем дальнейших указаний преподавателя. Не нажимаем «завершить экзамен» без разрешения преподавателя. 

Суббота 16.05 в 12:00

  1. Открываем сайт https://exams.mipt.ru/ Находим на главной странице мероприятие с названием «ID 32700 КОНТРОЛЬНАЯ РАБОТА ПО ДИСЦИПЛИНЕ «ОСНОВНЫЕ АЛГОРИТМЫ» (ФУПМ, 1 КУРС)» (проще через Ctrl + F). Нажимаем преступить к решению. Если зайдете в систему раньше, чем в 12:00, в контрольную вас перекинет автоматически в момент его начала.
  2. Приготовили зачетку (или паспорт) и ждем дальнейших указаний преподавателя. Не нажимаем «завершить экзамен» без разрешения преподавателя. 
 

О тесте


12 Мая 2020

В этой записи я отвечу на некоторые часто задаваемые вопросы о тесте и приведу пример нескольких тестовых вопросов.

Этот тест будет похож на прошлогодние контрольные? Задачи будут того же уровня?

 Нет, этот тест не будет похож на прошлогодние контрольные. В контрольных были содержательные задачи, требующие развёрнутого ответа, а в тесте будут вопросы с выборами вариантов ответа. Для прохождения теста достаточно иметь базовые знания по курсу. При этом для выбора ответа возможно придётся что-то простое решить на бумаге.

В четверг будет пробный тест? Будет ли пробный вариант? Как подготовиться?

 Нет, в четверг будет не пробный тест, а знакомство с системой прокторинга и тестирующей системой, цель этого события — устранить технические проблемы, чтобы они не случились в момент начала теста. Пробного варианта не будет, поскольку тест будет состоять из достаточно элементарных вопросов, а если мы зададим заранее 10-15 элементарных вопросов, то мы второй раз эти вопросы или близкие к ним задавать не будем, поскольку основная цель теста — проверка уровня тройки и несколько последних вопросов будут содержательными и призваны проверить знания на «хорошо».

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

Можно ли пользоваться литературой?

 Нет, на тесте нельзя будет ничем пользоваться. Только чистой бумагой и ручкой (воду и перекус взять, конечно, можно); тест будет длиться до полутора часов.

Как оценивается тест?

 Каждый семинарист учитывает результаты теста по своему усмотрению. Итоговую оценку в этом учебном году каждый семинарист выставляет на основе собственной системы текущего контроля.

Я живу в одной комнате с другими первокурсниками. В требованиях к прокторингу сказано, что никого, кроме меня, не должно быть в комнате. Как быть?

 Это требование справедливо для пересдач и (возможно экзаменов). У нас контрольная работа и мы таких требований не накладываем. Тем не менее, если у вас есть возможность писать тест в отдельных комнатах, пожалуйста, воспользуйтесь ей. Если вы уехали домой, требуется, чтобы в комнате кроме вас никого не было.

 

Примеры вопросов 

1. Отметьте все справедливые асимптотические оценки для (детерминированного) алгоритма быстрой сортировки (опорным элементом выбирается последний).

$O(n^3)$
 
$O(n^2)$
 
$O(n\log n)$
 
$O(n)$
 
$\Omega(n^3)$
 
$\Omega(n^2)$
 
$\Omega(n\log n)$
 
$\Omega(n)$
 
$\Theta(n^3)$
 
$\Theta(n^2)$
 
$\Theta(n\log n)$
 
$\Theta(n)$
 

2. Отметьте все спаведливые факты про алгоритм «Поиск в ширину»

Время открытия и закрытия вершин графа образуют правильную скобочную последовательность
 
Время работы алгоритма $O(|V| + |E|)$
 
Дерево поиска в ширину — является деревом кратчайших путей
 
Дерево поиска в ширину (запущенного из вершины $s$) уникально, т.е. не зависит от порядка рассмотрения вершин
 

 

Правильные ответы на эти вопросы вы сможете узнать в четверг на тестировании системы прокторинга (начало в 18:35).  В рамках этого тестирования нужно будет просто разобраться как работает система прокторинга и устранить технические проблемы, если они будут. 

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

 

Тест


10 Мая 2020

Мы проведём тест для всех студентов курса в субботу 16 мая. Время проведения с 12:00 до 15:00; сам тест будет длиться полтора часа (временные границы выбраны с запасом в силу технических особенностей системы прокторинга и для устранения технических проблем, в случае их возникновения). Для участия в тесте необходимо заполнить форму. Пожалуйста, сделайте это как можно скорее.

Сам тест будет проходить через этот сайт — данные для входа появятся позже. Тестирование будет проходить с помощью системы прокторинга МФТИ. Мы постараемся провести пробный тест для студентов в четверг. Следите за объявлениями на сайте.

Технические требования для работы с системой прокторинга приведены на её сайте — https://exams.mipt.ru.

 

Перенос семинара (901+)


28 Апреля 2020

Семинар, который должен был пройти первого мая, перенесён на четверг 30 апреля 18:30. Ссылка на конференцию zoom появится в этом посте позже.

P.S. Домашнее задание в честь переноса можно сдать до 23:00 пятницы 1 мая.

 

Новый контест в Codeforces


28 Апреля 2020

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

 

Ссылки на занятия в zoom


06 Апреля 2020

Я сделал регулярные конференции в zoom для лекций и семинаров. Ссылки на них меняться не должны, но это не точно. В этом посте будут ссылки на лекцию и семинар к девятой неделе; если дальше ссылки будут меняться, буду размещать актуальные ссылки  в раздел «Записи онлайн-занятий», чтобы не захламлять блог страницы курса.

 

Семинар 27.03


27 Марта 2020

Ссылка на конференцию zoom: https://zoom.us/j/3103812877  и 

https://us04web.zoom.us/j/3103812877 

 

Лекция 23.03


23 Марта 2020

Ссылка на конференцию zoom —  https://zoom.us/j/26329609 

 

Лекция пройдёт в режиме вебинара в zoom (установите себе клиент заранее). В случае желания задать вопрос предпочтительнее нажать на кнопку "поднять руку" и когда я дам слово задать вопрос голосом или написать свой вопрос в чат для вопросов (а не общий чат) (чат для вопросов будет недоступен — пишите в общий чат). Я постараюсь следить и за общим чатом, но часто вопросы оттуда легко пропустить или заметить позже подходящего момента для ответа.

Лекция начинается по расписанию — в 17:05, я начну трансляцию в 16:55 или чуть раньше (ссылка будет в этом посте). Лучше подключитесь до 17:05, чтобы устранить технические проблемы, если они будут. Запись лекции будет выложена после её окончания.

 

Семинар 19.03


19 Марта 2020

Ссылка на конференцию zoom: https://zoom.us/j/3103812877  и 

https://us04web.zoom.us/j/3103812877 

 

Семинар пройдёт в режиме конференции в zoom (установите себе клиент заранее). Хочется сделать семинар живым, поэтому если у вас есть планшет с пером и программа, которая позволяет эмитировать доску — приготовьте их, чтобы в случае рассказа своего решения, я просто переключил экран на вас. Если технических средств нет, то можно будет просто фотографировать своё решение на бумаге и посылать его в чат.

Семинар начинается в 12:20, я начну трансляцию в 12:10 (ссылка будет в этом посте). Лучше подключитесь до 12:20, чтобы устранить технические проблемы, если они будут. Запись семинара будет выложена после его окончания.

 

Варианты для подготовки к семестровой контрольной


09 Марта 2020

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

 

 

Лекция 5.03


03 Марта 2020

Лекция в четверг 5.03 состоится в 18:35-20:00 в аудитории 5.17 (потоковая аудитория корпуса "Цифра"). Лекция проходит вместо лекции 9.03, которая пропадёт из-за выходного дня.

 

 

Исправление условия задачи


25 Февраля 2020

Исправлено условие задачи 6* в домашнем заданиий 3.

 

Заметки и примеры к лекциям


22 Февраля 2020

Начиная с третьей лекции подробных конспектов не будет, однако Д. Киранов и К. Чеканов будут записывать некоторые сюжеты с лекций, которые будут публиковаться в файле Заметки и примеры к лекциям.

 

Codeforces


20 Февраля 2020

Для желающих решать задачи по алгоритмам с программированием был подготовлен контест в системе codeforces. На оценку за этот курс этот контест не влияет, однако мы собираемся сделать тех. курс, в котором этот контест будет учитываться.

 

Лекция 20.02


19 Февраля 2020

Лекция 20.02 состоится в 18:35-20:00 в 110 КПМ. Лекция проходит вместо лекции 24.02, которая пропадёт из-за выходного дня.

 

Доп занятия (консультации)


18 Февраля 2020

Дополнительные занятия по курсу в формате консультаций проходят по вторникам с 18:35 до 20:00 в потоковой аудитории 4 этажа корпуса «Арктика» (кроме 03.03.2020). Консультации проводят учебные ассистенты кафедры МОУ Кирилл Чеканов и Дмитрий Киранов. Формат консультаций — ответы на вопросов, можно задовать вопросы по решению задач пройденных листков и домашних заданий, дедлайн отправки которых уже прошёл.

 

Задачи из Шеня


08 Февраля 2020

В листочках мы помечаем задачи из книги Шеня «Программирование: теоремы и задачи». В этой книге записаны решения всех задач, поэтому вы можете их изучить, но в домашнем задании стоит сначала попробовать решить задачу самостоятельно.

 

(901+): техать задачи из Шеня не нужно (если только вы не хотите, чтобы проверяющий посмотрел правильность решения).

P.S. Пометка (901+) означает, что текст относится к студентам моей группы.

 

Сдача домашних работ (901+)


08 Февраля 2020

Домашние задания нужно отправлять на адрес homework@rubtsov.su до 23:59 четверга (перед семинаром). Все задания принимаются только в формате $\TeX$. Прикрепите к письму два файла: pdf и tex-исходник. Не забудьте указать вашу фамилию и группу в pdf-файле!

Исключение можно сделать только для задания на первой неделе — его можно принести на семинар в тетради.

Почему тех? Во-первых, через пару лет вам уже предстоит написание диплома и боль- шинство дипломов так или иначе связаны с математикой, и уж точно в подавляющем большинстве из них присутствуют формулы. Tех – довольно гибкий инструмент для работы с математическими текстами, он является стандартом для публикаций в крупных журналах, не зависит от платформы и с ним довольно удобно работать. Даже в переписках в сети, уже принято записывать математические формулы в стиле теха и большинство профильных сайтов поддерживают конвертацию на лету из теха в формулы. Для знакомства с техом на примерах, можно использовать исходники заданий по курсу ТРЯП.

В качестве литературы по теху, я рекомендую книгу Львовского и статью с набором примеров Воронцова, а также wiki-учебник. Так же я нашёл видеоуроки, возможно они окажутся полезны.

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

В качестве редактора, я рекомендую использовать Texmaker. Это довольно удобный кроссплатформенный редактор. Есть также множество онлайн-редакторов — мне понравился Overleaf.