Алгоритмы на графах (осень 2015)


#62

Внес пару исправлений в условие задачи 6, с целью убрать искушение решать ее без графов. Срок сдачи 20.12 в связи с коллоквиумом.


#63

Ну, что вырастил я богатырей или нет? Кто не посрамит землю Ростовскую в честном поединке?


#64

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


#65

Для тех, кто уже сдал задачу и ему нечем заняться, или просто считает, что задача слишком простая, - challenge (на тему взятия различных условий с потолка):

Что будет, если подобавлять к текущей формулировке различных ограничений? (ограничения под разными номерами - вводятся независимо).

  1. Пусть разрешен неограниченный обмен французов друг с другом:
    1. Дает ли простое (допустимое в самой начальной постановке задачи) жадное решение, если его слегка модифицировать, точное решение?
    2. А точно ли дает? (рассмотреть специфический случай. Подсказка - кое-где стоят нули). Указать, какое допущение должно быть сделано в исходном условии.
  2. Пусть разрешен ограниченный обмен французов друг с другом: общее количество обменов всех французов <= R;
    1. Привести модифицированную сеть, решающую задачу.
    2. Обосновать допустимость решения с помощью такой сети.
    3. А точно ли решает? (Подсказка: рассмотреть тот же случай, что и 1.2). Также указать необходимое допущение.
  3. HARD: Пусть для каждого француза ограничено число обменов с другими французами. (Пояснение: если cf1 и cf2 - количество обменов, которые уже совершили французы f1 и f2, то, если между ними происходит очередной обмен, увеличиваются оба счетчика. Ограничение имеет вид: cfj <= R для всех j).
    1. Решить каким угодно образом за полиномиальное от k, n и |Flow| время. Либо показать, что все плохо.

Для 1 и 2 есть правильные ответы. Для 3 - есть мнение, что все плохо :wink:


#66

Расписание на ближайшее время. Указывайте свою фамилию в строке, соответственно таймслоту, чтобы зарезервировать время. Принимать задачи буду в 320. Прошу впустую время не бронировать!

Переписывание коллоквиума 25.12 в 8:30 в 322 ауд.


#67

Вот реальный челендж, о котором я говорил на паре.


#68

Внимание! В расписании прошу указывать количество задач уже готовых к сдаче. Если Ваших в планах есть доделывание и сдача задачи, то это не надо вносить в расписание. Только по факту. Задача готова, пошел(а) и записался.

Прошу всех кто уже записан на 24-25.12 указать кол-во задач. При этом можно записать 2 человека на одно время по 1 графовой задаче каждый.

PS: Это условие связано с тем, что есть люди с готовыми задачами, которым нет место в расписании. Это неправильно.


#69

Только что закончил проверять и выставил. Ибрагимов получает ачивку единственного кто ни разу не ответил ошибочно, жаль что два вопроса пропущено.

Бротский, Бурховецкий, Кокшаров, Попова, Салион показывают мне конспекты в четверг или пятницу. Иначе -1 балл.

Все у кого меньше 10 баллов переписывают в пятницу 25.12.15 в 8:30 в 322 ауд.

И в заключении, хочу выразить свое презрение всем списунам.


#70

Тем временем, представлен новый алгоритм для решения задачи изоморфизма графов: http://habrahabr.ru/post/273231/

Не знаю, рассказывал ли @RS об этом.


#71

Не знаю, что насчёт @RS, но @bravit очень оценит такое событие.


#72

Я уже в курсе этой статьи. Еще не прочел, но очень заинтересован.


#73

Результаты переписывания означают, что я зря его проводил. Только один человек перешагнул порог в 10 баллов. @gotdjent поздравляю.

Остальные велкам на пересдачи по расписанию.


#74

Роман Борисович, будет ли тень по графам, и если будет, то когда?


#75

Только с направлениями из деканата, естественно. Если найдутся те, кому деканат разрешит, пишите мне в личку.

UPD: Все у кого есть направления из деканата на теневую сессию, завтра подходим в 320 ауд к 10:00. Направление иметь при себе обязательно. Если опоздаете, будете нас искать.


#76

Добор баллов состоится 18.02. Сдача задач: 14:30-15:30. Переписывание коллоквиума: 15:30-16:30. Аудитория предположительно 320.