Внес пару исправлений в условие задачи 6, с целью убрать искушение решать ее без графов. Срок сдачи 20.12 в связи с коллоквиумом.
В связи с правками, выкладываю на мудл модификацию того решения, что мы обсуждали на лабораторной.
Для тех, кто уже сдал задачу и ему нечем заняться, или просто считает, что задача слишком простая, - challenge (на тему взятия различных условий с потолка):
Что будет, если подобавлять к текущей формулировке различных ограничений? (ограничения под разными номерами - вводятся независимо).
- Пусть разрешен неограниченный обмен французов друг с другом:
- Дает ли простое (допустимое в самой начальной постановке задачи) жадное решение, если его слегка модифицировать, точное решение?
- А точно ли дает? (рассмотреть специфический случай. Подсказка - кое-где стоят нули). Указать, какое допущение должно быть сделано в исходном условии.
- Пусть разрешен ограниченный обмен французов друг с другом: общее количество обменов всех французов <= R;
- Привести модифицированную сеть, решающую задачу.
- Обосновать допустимость решения с помощью такой сети.
- А точно ли решает? (Подсказка: рассмотреть тот же случай, что и 1.2). Также указать необходимое допущение.
- HARD: Пусть для каждого француза ограничено число обменов с другими французами.
(Пояснение: если cf1 и cf2 - количество обменов, которые уже совершили французы f1 и f2, то, если между ними происходит очередной обмен, увеличиваются оба счетчика. Ограничение имеет вид: cfj <= R для всех j).
- Решить каким угодно образом за полиномиальное от k, n и |Flow| время. Либо показать, что все плохо.
Для 1 и 2 есть правильные ответы. Для 3 - есть мнение, что все плохо 
Расписание на ближайшее время. Указывайте свою фамилию в строке, соответственно таймслоту, чтобы зарезервировать время. Принимать задачи буду в 320. Прошу впустую время не бронировать!
Переписывание коллоквиума 25.12 в 8:30 в 322 ауд.
Внимание! В расписании прошу указывать количество задач уже готовых к сдаче. Если Ваших в планах есть доделывание и сдача задачи, то это не надо вносить в расписание. Только по факту. Задача готова, пошел(а) и записался.
Прошу всех кто уже записан на 24-25.12 указать кол-во задач. При этом можно записать 2 человека на одно время по 1 графовой задаче каждый.
PS: Это условие связано с тем, что есть люди с готовыми задачами, которым нет место в расписании. Это неправильно.
Только что закончил проверять и выставил. Ибрагимов получает ачивку единственного кто ни разу не ответил ошибочно, жаль что два вопроса пропущено.
Бротский, Бурховецкий, Кокшаров, Попова, Салион показывают мне конспекты в четверг или пятницу. Иначе -1 балл.
Все у кого меньше 10 баллов переписывают в пятницу 25.12.15 в 8:30 в 322 ауд.
И в заключении, хочу выразить свое презрение всем списунам.
Тем временем, представлен новый алгоритм для решения задачи изоморфизма графов: http://habrahabr.ru/post/273231/
Не знаю, рассказывал ли @RS об этом.
Я уже в курсе этой статьи. Еще не прочел, но очень заинтересован.
Результаты переписывания означают, что я зря его проводил. Только один человек перешагнул порог в 10 баллов. @gotdjent поздравляю.
Остальные велкам на пересдачи по расписанию.
Роман Борисович, будет ли тень по графам, и если будет, то когда?
Только с направлениями из деканата, естественно. Если найдутся те, кому деканат разрешит, пишите мне в личку.
UPD: Все у кого есть направления из деканата на теневую сессию, завтра подходим в 320 ауд к 10:00. Направление иметь при себе обязательно. Если опоздаете, будете нас искать.
Добор баллов состоится 18.02. Сдача задач: 14:30-15:30. Переписывание коллоквиума: 15:30-16:30. Аудитория предположительно 320.
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021