Дискретная математика 2MIT осень 2017 — различия между версиями
(→Практика Богомолов) |
(→Практика Подгузов) |
||
| (не показана 51 промежуточная версия 5 участников) | |||
| Строка 2: | Строка 2: | ||
== Лекции == | == Лекции == | ||
Преподаватель: Омельченко А. В. | Преподаватель: Омельченко А. В. | ||
| + | |||
| + | [https://docs.google.com/spreadsheets/d/1YyH-pWc9qeDoVxMoJTY2nnRggXjO1ih-8jgjNtEkbic/edit?usp=sharing Результаты] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/6/6b/Cw_dm_202.pdf Контрольная] | ||
== Практика Подгузов == | == Практика Подгузов == | ||
| + | |||
| + | В сентябре практику заменяет Иосиф Гордон. | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/5/54/%282%29_list_1.pdf Практика 08.09] [http://mit.spbau.ru/sewiki/images/4/48/Hw_1_kirchhoff.pdf Домашнее задание до 22.09] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/a/a3/%282%29_list_2.pdf Практика 15.09] [http://mit.spbau.ru/sewiki/images/e/ee/Hw_2_euler.pdf Домашнее задание до 29.09] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/2/2f/%282%29_list_3.pdf Практика 22.09] [http://mit.spbau.ru/sewiki/images/7/7f/Hw_3_hamilton.pdf Домашнее задание до 06.10] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/8/8b/%282%29_list_4.pdf Практика 29.09] [http://mit.spbau.ru/sewiki/images/1/1a/Hw_4_splits.pdf Домашнее задание до 13.10] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/8/80/Practice_171006.pdf Практика 06.10] [http://mit.spbau.ru/sewiki/images/5/57/Hw_171006.pdf Домашнее задание до 20.10] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/2/22/Practice_171013.pdf Практика 13.10] [http://mit.spbau.ru/sewiki/images/a/ac/Hw_171013.pdf Домашнее задание до 27.10] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/6/65/Practice_171020.pdf Практика 20.10] [http://mit.spbau.ru/sewiki/images/d/dc/Hw_171020.pdf Домашнее задание до 10.11] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/9/99/Practice_171027.pdf Практика 27.10] [http://mit.spbau.ru/sewiki/images/a/a0/Hw_171027.pdf Домашнее задание до 17.11] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/c/ca/Practice_171110.pdf Практика 10.11] [http://mit.spbau.ru/sewiki/images/a/a2/Hw_171110.pdf Домашнее задание до 24.11] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/b/be/Practice_171117.pdf Практика 17.11] [http://mit.spbau.ru/sewiki/images/b/b7/Hw_171117.pdf Домашнее задание до 01.12] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/6/60/Practice_171124.pdf Практика 24.11] [http://mit.spbau.ru/sewiki/images/7/7f/Hw_171124.pdf Домашнее задание до 08.12] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/5/53/Practice_171201.pdf Практика 01.12] [http://mit.spbau.ru/sewiki/images/c/cd/Hw_171201.pdf Домашнее задание до 15.12] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/c/ce/Practice_171208.pdf Практика 08.12] [http://mit.spbau.ru/sewiki/images/5/5e/Hw_171208.pdf Домашнее задание до 19.12] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/b/b4/Practice_171215.pdf Практика 15.12] [http://mit.spbau.ru/sewiki/images/4/48/Hw_171215.pdf Домашнее задание до 22.12] [http://mit.spbau.ru/sewiki/images/3/39/Hw_171215_solution.pdf Разбор задачи 1] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/d/dd/Pratice_171229.pdf Дополнительное задание] | ||
| + | |||
| + | Посылать домашние задания нужно в электронном виде (google docs тоже подойдет) на [mailto:npodguzov@yandex.ru npodguzov@yandex.ru]. Также по этому адресу можно обращаться со всеми вопросами. | ||
| + | |||
| + | Если вы сдаете хотя бы на указанное количество баллов, вы получаете зачет по теме (вам не придется ее сдавать на зачете в конце семестра). | ||
== Практика Богомолов == | == Практика Богомолов == | ||
| Строка 9: | Строка 49: | ||
В сентябре практику заменяет Алексей Палецких. | В сентябре практику заменяет Алексей Палецких. | ||
| − | + | [http://mit.spbau.ru/sewiki/images/1/15/AU_cw_2_1.pdf Практика 8 сентября] | |
| − | http://mit.spbau.ru/sewiki/images/ | + | [http://mit.spbau.ru/sewiki/images/f/f4/AU_hw_2_1.pdf Домашнее задание от 8 сентября] Крайний срок: 21 сентября 23:59. |
| − | Практика 8 сентября | + | |
| − | http://mit.spbau.ru/sewiki/images/ | + | |
| − | + | [http://mit.spbau.ru/sewiki/images/2/25/AU_cw_2_2.pdf Практика 15 сентября] | |
| + | [http://mit.spbau.ru/sewiki/images/2/2b/AU_hw_2_2.pdf Домашнее задание от 15 сентября] Крайний срок: 28 сентября 23:59. | ||
| − | Обязательно сдать хоть что-то, если вы сдаете хотя бы на указанное количество баллов, вы получаете зачет по теме | + | [http://mit.spbau.ru/sewiki/images/2/22/AU_cw_2_3.pdf Практика 22 сентября] |
| + | [http://mit.spbau.ru/sewiki/images/2/2f/AU_hw_2_3.pdf Домашнее задание от 22 сентября] Крайний срок: 5 октября 23:59 | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/8/8b/%282%29_list_4.pdf Практика 29 сентября] | ||
| + | [http://mit.spbau.ru/sewiki/images/4/43/Hw_4_dm_202_2.pdf Домашнее задание от 29 сентября] Крайний срок: 12 октября 23:59 | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/8/80/Practice_171006.pdf Практика 6 октября] | ||
| + | [http://mit.spbau.ru/sewiki/images/0/0d/Hw_5_dm_202_2.pdf Домашнее задание от 6 октября] Крайний срок: 19 октября 23:59 | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/5/57/Practice_students_05.pdf Практика 13 октября] | ||
| + | [http://mit.spbau.ru/sewiki/images/c/c7/HW_06_dm_202_2.pdf Домашнее задание от 13 октября] Крайний срок: 26 октября 23:59 | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/c/c6/Practice_students_06.pdf Практика 20 октября] | ||
| + | [http://mit.spbau.ru/sewiki/images/5/5d/HW_07_dm_202_2.pdf.pdf Домашнее задание от 20 октября] Крайний срок: из-за коллоквиумов дедлайн сдвигается на неделю, 9 ноября 23:59 | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/6/61/Practice_students.pdf Практика 27 октября] | ||
| + | [http://mit.spbau.ru/sewiki/images/8/81/Hw07_202_2.pdf Домашнее задание от 27 октября] Крайний срок: 16 ноября 23:59 | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/e/ea/Practice_students_08_202_02.pdf Практика 10 ноября] | ||
| + | [http://mit.spbau.ru/sewiki/images/6/6c/Hw08_202_02.pdf Домашнее задание от 10 ноября] Крайний срок: 23 ноября 23:59 | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/2/2a/Practice_students_09_202_2.pdf Практика 17 ноября] | ||
| + | [http://mit.spbau.ru/sewiki/images/5/57/Hw09_202_2.pdf Домашнее задание от 17 ноября] Крайний срок: 30 ноября 23:59 | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/c/cd/Practice_students_202_2.pdf Практика 24 ноября] | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/6/6e/Practice_students_10_202_2.pdf Практика 1 декабря] | ||
| + | [http://mit.spbau.ru/sewiki/images/0/0a/Hw10_202_2.pdf Домашнее задание от 1 декабря] Крайний срок: 7 декабря 23:59 | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/b/bd/Practice_students_202_2_12.pdf Практика 8 декабря] | ||
| + | [http://mit.spbau.ru/sewiki/images/2/22/Hw11_202_2.pdf Домашнее задание от 8 декабря] Крайний срок: 14 декабря 23:59 | ||
| + | |||
| + | [http://mit.spbau.ru/sewiki/images/c/cd/Practice_students_202_2.pdf Практика 15 декабря] | ||
| + | [http://mit.spbau.ru/sewiki/images/5/53/Hw12_202_2.pdf Домашнее задание от 15 декабря] Крайний срок: 21 декабря 23:59. Задание обязательно сдавать тем, у кого есть долги по предыдущим темам. | ||
| + | |||
| + | Сдавать можно лично (на листочке) или на электронную почту [mailto:msicar.ot.on.yas@gmail.com msicar.ot.on.yas@gmail.com]. Также по этому адресу обращаться со всеми вопросами. | ||
| + | |||
| + | Обязательно сдать хоть что-то, если вы сдаете хотя бы на указанное количество баллов, вы получаете зачет по теме. Если по какому-то домашнему заданию нет зачета, то 22 декабря нужно будет решить какие-то задания по несданным темам. | ||
== Практика Лабутин == | == Практика Лабутин == | ||
| Строка 22: | Строка 98: | ||
Дедлайны: | Дедлайны: | ||
| − | * мягкий дедлайн: | + | * мягкий дедлайн: 8 дней (дедлайн в пятницу в 23:59) |
* жесткий дедлайн: 14 дней (дедлайн в четверг в 23:59) | * жесткий дедлайн: 14 дней (дедлайн в четверг в 23:59) | ||
| − | После мягкого дедлайна баллы за каждую задачу умножаются на 0.5. | + | После мягкого дедлайна баллы за каждую задачу из обязательной части умножаются на 0.5. |
| − | Сдавать в tex-е. | + | Сдавать лучше в tex-е. За решения не в tex-е полученные баллы будут умножаться на 0.9. |
| + | |||
| + | Если сдавать не прямо перед дедлайном, то будет фидбек и можно все исправлять без понижения балла. | ||
| + | |||
| + | Если задача стоимости x не решается за >x часов, можно написать мне и попросить подсказку. | ||
Для зачета нужно набрать хотя бы 50% от обязательной части в каждой домашке и хотя бы 75% в сумме по всем домашкам. | Для зачета нужно набрать хотя бы 50% от обязательной части в каждой домашке и хотя бы 75% в сумме по всем домашкам. | ||
| + | |||
| + | Если за какую-то домашку получилось меньше 50%, то потом ее надо будет полностью досдать и на зачетной неделе сделать еще что-то по этой теме. | ||
Задания: | Задания: | ||
* '''8 сентября''' Подсчет остовных деревьев в графе. Матричная теорема о деревьях. [[Медиа:dm-17-09-08-practice_01.pdf|практика]] [[Медиа:dm-17-09-08-hw_01.pdf|домашка]] | * '''8 сентября''' Подсчет остовных деревьев в графе. Матричная теорема о деревьях. [[Медиа:dm-17-09-08-practice_01.pdf|практика]] [[Медиа:dm-17-09-08-hw_01.pdf|домашка]] | ||
| + | * '''15 сентября''' Эйлеровы и гамильтоновы циклы. [[Медиа:dm-17-09-15-practice_02.pdf|практика]] [[Медиа:dm-17-09-15-hw_02.pdf|домашка]] | ||
| + | * '''22 сентября''' Гамильтоновы циклы. [[Медиа:dm-17-09-22-practice_03.pdf|практика]] [[Медиа:dm-17-09-22-hw_03.pdf|домашка]] | ||
| + | * '''29 сентября''' Линейное пространство ребер. Циклы и разрезы. [[Медиа:dm-17-09-29-practice_04.pdf|практика]] [[Медиа:dm-17-09-29-hw_04.pdf|домашка]] | ||
| + | * '''6 октября''' Циркуляции и напряжения. Электрические сети. [[Медиа:dm-17-10-06-practice_05.pdf|практика]] [[Медиа:dm-17-10-06-hw_05.pdf|домашка]] | ||
| + | * '''13 октября''' Вершинная и реберная связность графа. [[Медиа:dm-17-10-14-practice_06.pdf|практика]] [[Медиа:dm-17-10-14-hw_06.pdf|домашка]] | ||
| + | * '''20 октября''' k-связные графы. Теорема Менгера. [[Медиа:dm-17-10-20-practice_07.pdf|практика]] [[Медиа:dm-17-10-20-hw_07.pdf|домашка]] Дедлайн 3 ноября в 23:59. | ||
| + | * '''27 октября''' Теорема Форда-Фалкерсона. [[Медиа:dm-17-10-27-practice_08.pdf|практика]] [[Медиа:dm-17-10-27-hw_08.pdf|домашка]] Начиная с этой домашки -- только один дедлайн, 2 недели, до четверга 23:59 | ||
| + | * '''10 ноября''' Паросочетания в графах. [[Медиа:dm-17-11-10-practice_09.pdf|практика]] [[Медиа:dm-17-11-10-hw_09.pdf|домашка]] | ||
| + | * '''17 ноября''' Совершенные паросочетания в произвольном графе. [[Медиа:dm-17-11-17-practice_10.pdf|практика]] [[Медиа:dm-17-11-17-hw_10.pdf|домашка]] | ||
| + | * '''24 ноября''' Совершенные паросочетания в произвольном графе. Теорема Татта, формула Татта-Бержа. [[Медиа:dm-17-11-24-hw_11.pdf|домашка]] | ||
| + | * '''1 декабря''' k-раскрашиваемые графы. Теорема Брукса. [[Медиа:dm-17-12-01-practice_12.pdf|практика]] [[Медиа:dm-17-12-01-hw_12.pdf|домашка]] | ||
| + | * '''8 декабря''' Нижние оценки на хроматическое число. Теорема Турана. Совершенные графы. [[Медиа:dm-17-12-09-practice_13.pdf|практика]] [[Медиа:dm-17-12-09-hw_13.pdf|домашка]] | ||
| + | * '''15 декабря''' Реберная раскраска графов. [[Медиа:dm-17-12-15-practice_14.pdf|практика]] [[Медиа:dm-17-12-15-hw_14.pdf|домашка]] | ||
Текущая версия на 22:05, 27 декабря 2017
Лекции
Преподаватель: Омельченко А. В.
Практика Подгузов
В сентябре практику заменяет Иосиф Гордон.
Практика 08.09 Домашнее задание до 22.09
Практика 15.09 Домашнее задание до 29.09
Практика 22.09 Домашнее задание до 06.10
Практика 29.09 Домашнее задание до 13.10
Практика 06.10 Домашнее задание до 20.10
Практика 13.10 Домашнее задание до 27.10
Практика 20.10 Домашнее задание до 10.11
Практика 27.10 Домашнее задание до 17.11
Практика 10.11 Домашнее задание до 24.11
Практика 17.11 Домашнее задание до 01.12
Практика 24.11 Домашнее задание до 08.12
Практика 01.12 Домашнее задание до 15.12
Практика 08.12 Домашнее задание до 19.12
Практика 15.12 Домашнее задание до 22.12 Разбор задачи 1
Посылать домашние задания нужно в электронном виде (google docs тоже подойдет) на npodguzov@yandex.ru. Также по этому адресу можно обращаться со всеми вопросами.
Если вы сдаете хотя бы на указанное количество баллов, вы получаете зачет по теме (вам не придется ее сдавать на зачете в конце семестра).
Практика Богомолов
В сентябре практику заменяет Алексей Палецких.
Практика 8 сентября Домашнее задание от 8 сентября Крайний срок: 21 сентября 23:59.
Практика 15 сентября Домашнее задание от 15 сентября Крайний срок: 28 сентября 23:59.
Практика 22 сентября Домашнее задание от 22 сентября Крайний срок: 5 октября 23:59
Практика 29 сентября Домашнее задание от 29 сентября Крайний срок: 12 октября 23:59
Практика 6 октября Домашнее задание от 6 октября Крайний срок: 19 октября 23:59
Практика 13 октября Домашнее задание от 13 октября Крайний срок: 26 октября 23:59
Практика 20 октября Домашнее задание от 20 октября Крайний срок: из-за коллоквиумов дедлайн сдвигается на неделю, 9 ноября 23:59
Практика 27 октября Домашнее задание от 27 октября Крайний срок: 16 ноября 23:59
Практика 10 ноября Домашнее задание от 10 ноября Крайний срок: 23 ноября 23:59
Практика 17 ноября Домашнее задание от 17 ноября Крайний срок: 30 ноября 23:59
Практика 1 декабря Домашнее задание от 1 декабря Крайний срок: 7 декабря 23:59
Практика 8 декабря Домашнее задание от 8 декабря Крайний срок: 14 декабря 23:59
Практика 15 декабря Домашнее задание от 15 декабря Крайний срок: 21 декабря 23:59. Задание обязательно сдавать тем, у кого есть долги по предыдущим темам.
Сдавать можно лично (на листочке) или на электронную почту msicar.ot.on.yas@gmail.com. Также по этому адресу обращаться со всеми вопросами.
Обязательно сдать хоть что-то, если вы сдаете хотя бы на указанное количество баллов, вы получаете зачет по теме. Если по какому-то домашнему заданию нет зачета, то 22 декабря нужно будет решить какие-то задания по несданным темам.
Практика Лабутин
Практик: Лабутин Игорь (labutin.igorl@gmail.com, vk.com/labutinigor)
Дедлайны:
- мягкий дедлайн: 8 дней (дедлайн в пятницу в 23:59)
- жесткий дедлайн: 14 дней (дедлайн в четверг в 23:59)
После мягкого дедлайна баллы за каждую задачу из обязательной части умножаются на 0.5.
Сдавать лучше в tex-е. За решения не в tex-е полученные баллы будут умножаться на 0.9.
Если сдавать не прямо перед дедлайном, то будет фидбек и можно все исправлять без понижения балла.
Если задача стоимости x не решается за >x часов, можно написать мне и попросить подсказку.
Для зачета нужно набрать хотя бы 50% от обязательной части в каждой домашке и хотя бы 75% в сумме по всем домашкам.
Если за какую-то домашку получилось меньше 50%, то потом ее надо будет полностью досдать и на зачетной неделе сделать еще что-то по этой теме.
Задания:
- 8 сентября Подсчет остовных деревьев в графе. Матричная теорема о деревьях. практика домашка
- 15 сентября Эйлеровы и гамильтоновы циклы. практика домашка
- 22 сентября Гамильтоновы циклы. практика домашка
- 29 сентября Линейное пространство ребер. Циклы и разрезы. практика домашка
- 6 октября Циркуляции и напряжения. Электрические сети. практика домашка
- 13 октября Вершинная и реберная связность графа. практика домашка
- 20 октября k-связные графы. Теорема Менгера. практика домашка Дедлайн 3 ноября в 23:59.
- 27 октября Теорема Форда-Фалкерсона. практика домашка Начиная с этой домашки -- только один дедлайн, 2 недели, до четверга 23:59
- 10 ноября Паросочетания в графах. практика домашка
- 17 ноября Совершенные паросочетания в произвольном графе. практика домашка
- 24 ноября Совершенные паросочетания в произвольном графе. Теорема Татта, формула Татта-Бержа. домашка
- 1 декабря k-раскрашиваемые графы. Теорема Брукса. практика домашка
- 8 декабря Нижние оценки на хроматическое число. Теорема Турана. Совершенные графы. практика домашка
- 15 декабря Реберная раскраска графов. практика домашка
