Цель заброшена
Автор не отписывался в цели 8 лет 5 месяцев 24 дня
Пройти курс "Основы теории графов"
Всем доброго времени суток!
Теория графов довольно полезная и нужная штука, особенно для программистов (которые специалисты, профессионалы, мастера своего дела и т.д. и т.п.). Знаний у меня в ней очень-очень мало, а очень бы хотелось иметь их чуть больше.
Каким-то образом напал на курс "Основы теории графов". Когда я его нашел, он ещё не начался. Так как эта тема мне интересна, знаний мало, а хотелось бы "углубить и расширить" ©, не долго думая подписался на курс. И начал ждать начала.
Начало сего действия было назначено на 12 сентября, т.е. четыре дня назад, на понедельник. Само собой разумеется, мне пришло оповещение. Я зашел, потыкался, прошел самое начало самого начала и из-за загруженности по работе больше туда не заходил.
Но так же нельзя! И поэтому я создаю эту цель и буду двигаться к её окончания прилагая все возможные усилия.
"Наши цели ясны, задачи определены! За работу, товарищи!" ©
P.S. Чуть позже дополню, возможно, описание. А может и нет.
P.P.S. "Please, dear God, don't let me fuck up" ©
Критерий завершения
Курс успешно завершен
Личные ресурсы
целеустремленность, упертость/упоротость, желание учиться
Экологичность цели
Графы очень полезная штука в разработке ПО. И понимание хотя бы основ, IMHO, строго обязательна для любого разработчика, который хочет называть себя профессионалом
-
Основные понятия теории графов - I
Баллы: 22.3 / 25
Задания: 23 / 23
Краткое описание:
Понятие графа. Неориентированный граф. Отношение инцидентности. Петли и мультиребра. Степень вершины. Первая теорема теории графов. Простые графы. Полный и пустой графы. Ориентированный граф. Смежность вершин. Представление графа с помощью структур данных.
Маршрут. Путь. Простой путь. Понятие связности. Компоненты связности. Связность в ориентированном графе. Замкнутый маршрут. Простой цикл. Длина цикла. Обхват графа. Понятие дерева. Двудольные графы. Раскраска вершин графа. Ациклические графы. Топологическая сортировка вершин.
Подграфы. Операции над графами. Удаление ребра. Удаление вершины. Остовный подграф. Индуцированное подмножество вершин. k-фактор. Понятие совершенного паросочетание. Остовный цикл. Мост. Точка сочленения. Операция стягивания ребра. Объединение, пересечение и симметрическая разность графов.
Количество графов на n вершинах. Изоморфизм графа. Непомеченный граф и помеченный граф. Классы эквивалентности. Автоморфизм.
-
Основные понятия и определения
-
Маршруты, пути, циклы. Понятие связности. Двудольные графы.
-
Подграфы. Основные операции над графами
-
Изоморфизм и автоморфизм графов
-
-
Основные понятия теории графов - II
Баллы: 18 / 24
Задания: 14 / 16
Краткое описание:
Определение дерева. Алгоритм поиска в глубину. Корневое дерево. Уровень и высота дерева. Частично упорядоченное множество. Сравнимые вершины. Нормальное дерево. Перекрестные ребра. Алгоритм поиска в ширину.
Эйлеров путь и цикл. Условия существования эйлерова цикла.
Паросочетание в графе. Совершенное паросочетание. Максимальное паросочетание. Наибольшее по включению паросочетание. "Жадный" алгоритм поиска парасочетания. M-чередующийся путь. M-дополняющий путь. Необходимое и достаточное условие максимальности паросочетания. Теорема Бержа. Поиск паросочетания в двудольном графе. Теорема Холла.
-
Деревья
-
Эйлеровы графы
-
Паросочетания. Теорема Холла
-
-
Циклы в графах
Баллы: 6.7 / 14
Задания: 8 / 10
Краткое содержание:
Гамильтонов цикл и путь.Формула количества гамильтоновых путей. Теорема Оре. Теорема Дирака.
Графы де Брёйна. Последовательность де Брёйна. Алгоритм построения графа де Брёйна. Гамильтоновы и эйлеровы цикла в графах де Брёйна.
-
Гамильтоновы циклы
-
Графы Де Брейна
-
-
Связность в графах - 1
Баллы: 16 / 16
Задания: 10 / 10
Краткое содержание:
Вершинная связность. Вершинное разделяющее множество. Вершинно k-связный граф. Реберная связность. Реберное разделяющее множество. Реберно k-связный граф. Реберный разрез.
Похожесть в графе. Компоненты похожести. Построение дерева блоков и точек сочленения 1-связного графа. Вершинный кактус. Реберный кактус. Алгоритм Хопкрофта-Тарьяна.
-
Вершинная и реберная связность
-
Структура двусвязных графов
-
-
Связность в графах - 2
-
k-связные графы
-
Потоки и сети
-
-
Паросочетания в графах
-
Независимые множества и покрытия графа
-
Паросочетания в произвольных графах
-
-
Раскраска графов
-
k-раскрашиваемые графы. Теорема Брукса
-
Нижние оценки на хроматическое число
-
Хроматический многочлен графа
-
-
Планарные графы - 1
-
Основные свойства планарных графов
-
Формула Эйлера. Карты на поверхностях
-
аскраска планарных графов
-
-
Планарные графы - 2
-
Критерии планарности графов
-
Карты на поверхностях
-
Дневник цели
Не отписывался тут уже почти месяц. Сегодня решил, что больше оттягивать нельзя и нужно обязательно что-нибудь черкануть и как бы подвести черту.
В этот понедельник (17 октября) я закрыл четвертую часть: Связность в графах - 1. Это вторая лекция, которую я закрыл полностью т.е. выполнив все-все задания из неё. И первая лекция, где я получил все баллы:
- Основные понятия теории графов - I:22.3 из 25
- Основные понятия теории графов - II: 18 из 24
- Циклы в графах: 6.7 из 14
- Связность в графах - 1: 16 из 16
С лекцией 3 вышел вообще полный провал (и это видно по полученным баллам). Я начал делать её уже после того, как закончился мягкий deadline, а это значит что с самого начал не мог претендовать на больше чем 7 баллов (половину из возможных).
В лекции 2 и 3 у меня остались не выполненные задания (до сих пор висят): во второй - одно доказательство и одна задача на реализацию алгоритма (shame on me); в третей - два доказательства.
По мере прохождения лекций я очень на долго завис сначала на автоморфизме графов, а потом на гамильтоновых циклах. У меня крайне плохо получается доказывать не совсем очевидные вещи. Кто может посоветовать что-нибудь для улучшения этого полезного в математике навыка (я про доказательство)??
Самые интересные места лекций - приложения. Теоретизировать я не очень люблю. Лекция про последовательности де Брёйна и их применения мне понравилась больше всего.
И да, к этому моменту я уже исписал в моем конспекте 96 страниц. Давно так много не писал. Это должно быть полезно - мелкая моторика и вот это всё...
По какой причине я так запустил вторую и третью лекции? Из-за не правильного планирования и потому, что оставлял всё до последних дней. Сейчас стараюсь распределить нагрузку на всю неделю, выделяя по часу в день на просмотр и усвоение материала. Сегодня прослушал заново первую из лекций о связности в графах - сложились в голове некоторые доказательства, не понятые мною при при первых проходах.
Постараюсь в воскресенье закончить очередную лекцию, подтянуть хвосты и отписаться сюда.
Не успел пройти первую лекцию до мягкого дедлайна. Отчасти из-за недостатка свободного времени и частично по причине лени. Последний модуль первой лекции закончил только сегодня. Из-за достижения мягкого дедлайна за задания давали половину обычного балла. Не знаю на что влияет итоговое количество баллов, но обидно - во всех остальных модулях (с первого по третий) заработал все баллы, а за последний только половину возможного.
В последнем модуле возникли проблемы с пониманием автоморфизма. Само понятие мне понятно (извините за каламбур), а вот отдельные части ускользнули.
По ходу прохождения первой лекции стало понятно, что у меня огромное количество пробелов в дискретной математике, теории множеств, комбинаторике и умении формулировать правильные и емкие доказательства. Так что эти темы замечательные кандидаты на изучение в будущем. По части из тем на этом же сайте есть лекции.
Остатки конспекта по первой лекции я так и не закончил составлять. А из-за болезни (я сейчас лежу, болею и набираю этот текст с планшета) его написание откладывается на несколько дней.
Сейчас начинаю слушать вторую лекцию: Основные понятия теории графов - II. И мне нужно поторопиться - мягкий дедлайн для этой лекции наступает 3 октября, а это совсем скоро.
Только сегодня смог найти время (ну и заставить себя ) пройти до конца следующий подпункт (да-да, тот самый который обещал закончить ещё четыре дня назад). Составил конспект и вроде понял всё из того, что объясняли. Хочу заметить, что стало чуть-чуть сложнее (самую малость).
Постараюсь сегодня закончить остальные два подпункта и закрыть первую часть курса - меня поджимает мягкий дедлайн (он уже завтра)
Вчера на было времени, но сегодня я с утра пересмотрел лекции и составил конспект по ним.
Сегодня нужно прослушать следующий этап: Маршруты, пути, циклы. Понятие связности. Двудольные графы, а завтра по нему составлю конспект
Прослушал вечером (вчера) "Основные понятия и определения" из первого этапа и прошел задания, которые там были. Вроде пока всё понятно.
Завел себе тетрадь для ведения конспекта. Сегодня ещё раз прослушаю эту часть, законспектирую и отмечу этот подпункт выполненным.
