Алгоритмы и структуры данных 2 2019/2020 — различия между версиями
.obj (обсуждение | вклад) (→Аудиторная работа) |
.obj (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
# [https://www.dropbox.com/s/bkdp3xtfpxt3j21/algo2-3-npc.pdf?dl=0 9 сентября.] NP-полные задачи. | # [https://www.dropbox.com/s/bkdp3xtfpxt3j21/algo2-3-npc.pdf?dl=0 9 сентября.] NP-полные задачи. | ||
# [https://www.dropbox.com/s/gsesd7hw978wn0w/algo2-4-nph.pdf?dl=0 13 сентября.] Точные алгоритмы решения NP-трудных задач. | # [https://www.dropbox.com/s/gsesd7hw978wn0w/algo2-4-nph.pdf?dl=0 13 сентября.] Точные алгоритмы решения NP-трудных задач. | ||
| + | |||
= Домашние задания = | = Домашние задания = | ||
| Строка 28: | Строка 29: | ||
Второе домашнее задание: 27 сентября — 15 октября. | Второе домашнее задание: 27 сентября — 15 октября. | ||
| + | |||
= Аудиторная работа = | = Аудиторная работа = | ||
| Строка 38: | Строка 40: | ||
==Задания на программирование== | ==Задания на программирование== | ||
# [https://www.dropbox.com/s/6u8sflhq3w1ilxh/statement.pdf?dl=0 Описание задания] и [https://www.dropbox.com/s/ty7ouwnx86g2sdq/tests.zip?dl=0 тесты] к нему. Срок сдачи — 20 сентября. Срок сдачи может быть продлен по согласованию с преподавателем. Задание состоит из двух частей. За выполнение первой части моно получить один балл, за выполнение обеих частей — два балла. Дробные оценки не предусмотрены. | # [https://www.dropbox.com/s/6u8sflhq3w1ilxh/statement.pdf?dl=0 Описание задания] и [https://www.dropbox.com/s/ty7ouwnx86g2sdq/tests.zip?dl=0 тесты] к нему. Срок сдачи — 20 сентября. Срок сдачи может быть продлен по согласованию с преподавателем. Задание состоит из двух частей. За выполнение первой части моно получить один балл, за выполнение обеих частей — два балла. Дробные оценки не предусмотрены. | ||
| + | |||
= Оценки = | = Оценки = | ||
Версия 13:17, 15 сентября 2019
Лектор: С. Объедков
Расписание лекций:
понедельник 12:10 – 13:30, ауд. R304
пятница 10:30 – 11:50, ауд. R401
Консультации:
понедельник 18:00 – 20:00, к. T915
четверг 16:30 – 18:00, к. T915
Ассистенты:
Группы 182 и 184 — Александра Латышева.
Группы 185 и 186 — Мария Полякова.
Группы 187 и 188 — Агзамходжа Турсунходжаев.
Содержание
Лекции
- 2 сентября. Класс P: определение, примеры задач.
- 6 сентября. Класс NP: определение, примеры задач. Класс coNP. Возможное соотношение классов. Полиномиальные сведения.
- 9 сентября. NP-полные задачи.
- 13 сентября. Точные алгоритмы решения NP-трудных задач.
Домашние задания
Первое домашнее задание: 13 – 29 сентября.
Второе домашнее задание: 27 сентября — 15 октября.
Аудиторная работа
Оценка за аудиторную работу складывается из следующих частей: 3 балла за письменный тест (ориентировочно 1 октября), по 1 баллу за каждый из трех наборов задач, по 1 или 2 балла за каждое из трех заданий на программирование. Дробные оценки не предусмотрены. Если в сумме получается более десяти баллов, оценка за аудиторную работу равна десяти баллам.
Наборы задач
- P и NP До 16 сентября можно сдавать задачи устно (каждый студент сдает все задачи). Срок сдачи может быть продлен по согласованию с преподавателем. Те, кто не успевает, сдают письменно в течение следующей недели и в течение еще одной недели рассказывают решения некоторых задач преподавателю или (по согласованию с преподавателем) учебному ассистенту. Чтобы получить балл за набор задач, нужно решить все задачи. Дробные оценки не предусмотрены.
Задания на программирование
- Описание задания и тесты к нему. Срок сдачи — 20 сентября. Срок сдачи может быть продлен по согласованию с преподавателем. Задание состоит из двух частей. За выполнение первой части моно получить один балл, за выполнение обеих частей — два балла. Дробные оценки не предусмотрены.
Оценки
Итоговая оценка: 0,15 · оценка за первое домашнее задание + 0,15 · оценка за второе домашнее задание + 0,3 · оценка за аудиторную работу + 0,4 · оценка за письменный экзамен.
Необходимым условием получения итоговой оценки автоматом является наличие трех баллов (из трех возможных) за решение наборов задач и по крайней мере двух баллов (из трех возможных) — за письменный тест.
