Пересдача состоится в пятницу 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
Инструкции по доступу к тестирующей системе разосланы на почту, указанную в форме. Если Вы не получили письмо, проверьте папку Спам.
Инструкция по прохождению теста посредством системы прокторинга
12 Мая 2020
Публикую инструкцию от ответственного за прокторинг. Следуйте ей, чтобы получить доступ к системе прокторинга МФТИ (необходимо для прохождения теста!). Пожалуйста, ознакомьтесь также с подробной инструкцией (для наших нужд потребуется только её часть). Для доступа к тесту требуется заполнить форму; система прокторинга будет использоваться только для контроля за самостоятельным выполнением теста и возможности связи студент-пеподаватель, сам тест будет на этом сайте (ссылка будет опубликована позже).
Инструкция
Прежде всего настоятельно рекомендуется установить браузер Google Chrome, его установка позволяет избежать большинства типичных проблем. Также рекомендуется бегло ознакомиться с полной для студентов.
За несколько дней до экзамена (как только увидите инструкцию):
Регистрируем учетную запись, если ее еще нет (учетная запись Abitu.net подойдет) Если после регистрации вы заходите на https://exams.mipt.ru/ и не видите списка разных экзаменов, значит вы указали не всю необходимую информацию в профиле. Дозаполняем ориентируясь на красные звездочки.
Находим на главной странице мероприятие с названием «ID 32699 ТЕСТИРОВАНИЕ СИСТЕМЫ ПРОКТОРИНГА ПЕРЕД КОНТРОЛЬНОЙ РАБОТОЙ ПО ОСНОВНЫМ АЛГОРИТМАМ» (проще через Ctrl + F). Нажимаем «Зарегистрироваться». Начинается процедура проверки. Выдаем все разрешения. Делимся всем экраном. Если во время проверки есть какие-либо красные предупреждения, пишем в группу в телеграм. https://t.me/genalgorithms
Аналогично находим мероприятие «ID 32700 КОНТРОЛЬНАЯ РАБОТА ПО ДИСЦИПЛИНЕ «ОСНОВНЫЕ АЛГОРИТМЫ» (ФУПМ, 1 КУРС)». Регистрируемся проходим проверку. В случае проблем пишем в чат.
Четверг 14.05 в 18:35
Открываем сайт https://exams.mipt.ru/ Находим на главной странице мероприятие с названием «ID 32699 ТЕСТИРОВАНИЕ СИСТЕМЫ ПРОКТОРИНГА ПЕРЕД КОНТРОЛЬНОЙ РАБОТОЙ ПО ОСНОВНЫМ АЛГОРИТМАМ» (проще через Ctrl + F). Нажимаем преступить к решению. Если зайдете в систему раньше, чем в 18:35, в контрольную вас перекинет автоматически в момент его начала.
Приготовили зачетку (или паспорт) и ждем дальнейших указаний преподавателя. Не нажимаем «завершить экзамен» без разрешения преподавателя.
Суббота 16.05 в 12:00
Открываем сайт https://exams.mipt.ru/ Находим на главной странице мероприятие с названием «ID 32700 КОНТРОЛЬНАЯ РАБОТА ПО ДИСЦИПЛИНЕ «ОСНОВНЫЕ АЛГОРИТМЫ» (ФУПМ, 1 КУРС)» (проще через Ctrl + F). Нажимаем преступить к решению. Если зайдете в систему раньше, чем в 12:00, в контрольную вас перекинет автоматически в момент его начала.
Приготовили зачетку (или паспорт) и ждем дальнейших указаний преподавателя. Не нажимаем «завершить экзамен» без разрешения преподавателя.
О тесте
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 для лекций и семинаров. Ссылки на них меняться не должны, но это не точно. В этом посте будут ссылки на лекцию и семинар к девятой неделе; если дальше ссылки будут меняться, буду размещать актуальные ссылки в раздел «Записи онлайн-занятий», чтобы не захламлять блог страницы курса.
Лекция пройдёт в режиме вебинара в zoom (установите себе клиент заранее). В случае желания задать вопрос предпочтительнее нажать на кнопку "поднять руку" и когда я дам слово задать вопрос голосом или написать свой вопрос в чат для вопросов (а не общий чат) (чат для вопросов будет недоступен — пишите в общий чат). Я постараюсь следить и за общим чатом, но часто вопросы оттуда легко пропустить или заметить позже подходящего момента для ответа.
Лекция начинается по расписанию — в 17:05, я начну трансляцию в 16:55 или чуть раньше (ссылка будет в этом посте). Лучше подключитесь до 17:05, чтобы устранить технические проблемы, если они будут. Запись лекции будет выложена после её окончания.
Семинар пройдёт в режиме конференции в zoom (установите себе клиент заранее). Хочется сделать семинар живым, поэтому если у вас есть планшет с пером и программа, которая позволяет эмитировать доску — приготовьте их, чтобы в случае рассказа своего решения, я просто переключил экран на вас. Если технических средств нет, то можно будет просто фотографировать своё решение на бумаге и посылать его в чат.
Семинар начинается в 12:20, я начну трансляцию в 12:10 (ссылка будет в этом посте). Лучше подключитесь до 12:20, чтобы устранить технические проблемы, если они будут. Запись семинара будет выложена после его окончания.
Лекция 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.
