Открытое образование - бесплатный курс по теории графов

Далеко не все сторонники концепции общественной безопасности имеют хорошее математическое образование. Даже «технарями» себя считают практически единицы. Это обстоятельство не может не наложить свой отпечаток на модель восприятия текстов. Ведь в теории управления очень много «математики» пусть и прикладной. Чтобы исправить этот недостаток нужно пройти некоторое обучение. 

Самую высокую ценность, при наличии школьного образования, имеет изучение теории графов. Это особый тип структуры, близкий к способу хранения информации человеческим мозгом.  Далее идёт реклама бесплатного онлайн курса по изучению теории графов.

Записаться можно здесь: https://openedu.ru/course/mipt/GRAPHTH/

О курсе

Этот курс служит введением в современную теорию графов. Граф как математический объект оказывается полезным во многих теоретических и практических задачах. Дело, пожалуй, в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. В нашем курсе мы, конечно же, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов.

Формат
Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Информационные ресурсы
  1. В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. М.: Книжный дом «Либроком», 2009.
  2. А. А. Зыков. Теория конечных графов. Новосибирск: Наука, 1969.
  3. М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. М.: Мир, 1984.
  4. M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009.
  5. B. Bollobás. Modern Graph Theory. Springer, 1998.
  6. J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008.

Требования

Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики.
Программа курса
  1. Понятие графа и виды графов.
  2. Различные применения графов: от Кенигсберских мостов до Интернета.
  3. Связность графа, подграфы и степень вершины.
  4. Эквивалентные определения деревьев.
  5. Планарность и критерий Куратовского
  6. Формула Эйлера.
  7. Хроматическое число планарного графа.
  8. Перечисление деревьев: код Прюфера и формула Кэли.
  9. Формула для числа унициклических графов.
  10. Эйлеровы циклы и критерий эйлеровости.
  11. Гамильтоновы циклы. Критерий Дирака и критерий Хватала.
  12. Паросочетания. Теорема Холла и Кенига.
  13. Экстремальная теория графов. Теорема Турана.
  14. Аналог теоремы Турана для графов на плоскости.
  15. Теория Рамсея. Знакомства среди шести человек.
  16. Определение числа Рамсея.
  17. Нижняя и верхняя оценки чисел Рамсея.

Результаты обучения

По итогам успешного прохождения курса слушатель познакомится с понятием графа, с видами и различными характеристиками и свойствами графов. Слушатель узнает о задаче о правильных раскрасках и о возможности нарисовать данный граф на плоскости без пересечений ребер, а также научится разными способами определять деревья и перечислять их. Наконец, слушатель познакомится с понятиями эйлеровых и гамильтоновых циклов, паросочетаний и даже прикоснется к задачам экстремальной теории графов.


Записаться можно здесь: https://openedu.ru/course/mipt/GRAPHTH/
Комментарии (32)

Кстати, там я ещё обнаружил курс "Теория игр". Возможно, его прохождение поможет лучше понять, что есть игры с ненулевой суммой, на основе которых строится эксплуатация "человека человеком", об искоренении которой говорится в работах ВП СССР, как думаете, Henson?

У меня в этом смысле голова совсем испорчена. Постоянно думаю: «как можно этого не знать??» :).

Да, согласен, что образование, в том числе, по «теории игр» будет крайне полезно. Главное вовремя его получить.


Для примера, если скачать учебный план по какой-нибудь вузовской специальности, можно заметить, что порядок преподавания дисциплин выбран не просто так. Например, практически для всех математических направлений нужны знания по теории множеств. Для дифференциальных уравнений — математический анализ. Для криптографии — алгебра и т.д. В итоге выстраивается стройный учебный план, где ДОТУ в математическом изложении  можно будет проходить курсе так на третьем.


А вот с теорией графов всё интереснее. Её можно понять интуитивно, причём имея только школьное образование. Причём даже неполное. А школьникам этот курс проходить будет крайне интересно ещё и потому, что, изучив несколько простых приёмов из этой теории, вчерашние олимпиадные задачки будут решаться сами собой.
Теория графов дисциплина далеко не новая. По ней в сети можно найти много учебных материалов. например на twirpx.com. Ценность же онлайн курсов в том, что теорию рассказывает живой человек и есть возможность задать вопросы, если чего-то не понял.

Лекции обычно доступны в записи. Прямых способов скачать не видно.
Доброго времени! Что посоветуете тому  кто напрочь забыл многие слова ( местами даже и не знал)  написанные в  вашей статье? Стыдно, а что делать? Уровень моего образования в точных науках на уровне 5-6 класса, решительно всё забыл из школьной программы, полагаю ДОТУ будет сложно освоить с такими познаниями. Подскажите пожалуйста, с чего начать изучать, и понимать эти предметы?  Я больше гуманитарий, но понимаю, что без понимания точных наук  сложно будет добиться успехов в понимании сути вещей, хотелось бы организовать свою психику на новый лад, да и память свою взбодрить неплохо было бы...)

"Как тонко работает молодёжь! С душевными разговорами идёт!" (фильм "Убить дракона")

полагаю ДОТУ будет сложно освоить с такими познаниями
На самом деле это не будет являться проблемой при изучении именно ДОТУ. Потому как написана она специально в приближенном к гуманитарным дисциплинам стиле. В конце концов речь идёт про теорию управлению.

Однако при попытке разобраться в сути теории, могут возникнуть трудности. Связаны они с тем, что для понимания требуется формировать «свои» образы. Сидеть и рисовать. И вот тут у математика есть гигантское преимущество, у него есть готовые емкие и плотноупакованные образы — а точнее доступ к царству чистой математики Платона.

В любом случае эти трудности лишь удлиняют путь, но не пресекают его.
Подскажите пожалуйста, с чего начать изучать, и понимать эти предметы? 
Начинать надо с воспитания в себе чувства любви к простоте. Понимания того, что в мире математики всё и всегда очень просто, но только если этой поймёшь. Да, понять бывает сложно, но, с другой стороны, сделать это нужно всего один раз. И это очень важно, поскольку заучивание чего либо убивает всё желание учиться.

Обычно любовь к предмету призвана зародить так называемая «вводная лекция». В неё входит рассказ об истории дисциплины, как и почему люди захотели это изучать, какие задачи можно решить при помощи этих знаний и всё что у годно. на что хватит воображения лектора. А дальше идут серые будни сухого изложения теории.

Хороший преподаватель добивается понимания, плохой — старается уложиться в срок. Для примера хорошему преподавателю потребуется разобрать всего шесть задач по аналитической геометрии на плоскости, чтобы научить решать абсолютно любую задачу из этого курса. Плохой преподаватель будет прорешивать сотни задач и так ничему и не научит.

Ваша первая задача — найти автора, который зажжёт в вас интерес к математике. Неизвестно кто это будет для вас, но могу предположить что с этой ролью прекрасно справится книга Удовольствие от Х (Стивен Строгац, 2014). В ней рассказано про все важные темы математики, которые необходимо знать любому технарю, и которые нужны для понимания математических основ ДОТУ. А самое главное сделано это очень простым и понятным языком. Например, главу про теорию групп на примере матраса смогла понять даже моя восмилетняя племяшка.

Вторая задача — накопить фактические знания предмета. Если у вас есть ребёнок школьного возраста, то можно воспользоваться ситуацией и выполнять домашние задания вместе с ним. Главное не показывайте ему свои результаты. Об этом хорошо описано в работе ВП СССР «Нам нужна иная школа». Факт совместного выполнения задачи приносит пользу, получение готового решения — вред.

Если ребетёнка нет, или не хочется затягивать с восполнением знаний, самым лучшим решением будет изучение школьного курса математики самостоятельно. И вот тут очень важно выбрать правильный учебник. Ведь не просто так современные дети не могут освоить элементарных вещей. Ищите учебники Андрея Петровича Киселёва:
  1. «Элементарная геометрия»
  2. «Алгебра ч. 1»
  3. «Алгебра ч. 2»
Этих знаний будет более чем достаточно, чтобы перейти к  изучению ВУЗ-овских дисциплин.

Здесь вам будет крайне полезен ресурс: www.twirpx.com. Обязательно скачайте и держите под рукой «Конспект лекций по высшей математике» Дмитрия Письменного. Книга эта ориентирована на понимание основ, но не на их доказательство, поэтому считается «троечной».

И теперь, вооружившись всем этим, можно приступать к освоению высшей математики (правильнее было бы сказать — абстрактной). Здесь конкретного набора книг я уже не подскажу, по крайней мере сейчас это сделать сложно. Ограничусь названием теорий:
  1. Теория множеств
  2. Теория графов
  3. Теория групп
  4. Теория категорий
  5. Теория систем (теория динамических систем)
  6. Теория игр

PS: также рекомендую проходить бесплатные онлайн курсы, например, на openedu.ru


PPS: огромное спасибо за этот вопрос!
Уровень моего образования в точных науках на уровне 5-6 класса, решительно всё забыл из школьной программы, полагаю ДОТУ будет сложно освоить с такими познаниями.
Не подумайте что я отговариваю Вас от прохождения предложенного курса, сам с удовольствием его послушаю и обновлю свои знания.
Но мне почему-то кажется что в части «полагаю ДОТУ будет сложно освоить с такими познаниями» — Вы очень сильно ошибаетесь.
Мне тяжело оценить ДОТУ с точки зрения не технаря, но что-то мне подсказывает что ДОТУ != математика.

Конечно !=
Математика - это язык описания меры, частью которой является и ДОТУ.

что-то мне подсказывает что ДОТУ != математика.
ДОТУ, по заявлениям авторов, — это язык описания мироздания. Этим же статусом обладает математика. Если авторы правы, значит и «ДОТУ» и «Математика» это описание одного и того же.  Обязательно ли между ними должен быть знак равенства, думаю — нет. Однако поскольку в основе ДОТУ лежит теория систем, а если точнее обрезанная теория динамических систем, знания математики будут крайне полезны при создании «своих» образов.


Ну и почему равенства всё-таки нет. Люди знакомые с материалами концепции часто приводят в своей аргументации «за» правильност ьименно своих идей так называемую теорему Геделя о полноте. При этом не всегда понимают последствия использования именно этого аргумента в споре. Смысл этой теоремы сводится к тому, что независимо от нашего мнения об универсальности применяемого подхода, всегда найдутся утверждения, которые не попадают в сферу его действия. Другими словами «достаточно общая ТЕОРИЯ управления» не является «достаточно общей» и это доказанный математический факт.

Математика же не является теорией. Она находится над любыми теориями и описывает мироздание в и без границ. И в этом смысле полезно будет ознакомиться с идеей «Царства чистой математики» впервые озвученной Платоном.
 
Насколько реальны объекты математического мира? Некоторые считают, что ничего реального в них быть не может. Математические объекты суть просто понятия, они представляют собой мысленные идеализации, созданные математиками — часто под влиянием внешних проявлений и кажущегося порядка окружающего нас мира; но при этом они — всего лишь рожденные разумом абстракции. Могут ли они представлять собой что-либо, кроме просто произвольных конструкций, порожденных человеческим мышлением? И в то же время эти математические понятия часто выглядят глубоко реальными и эта реальность выходит далеко за пределы мыслительных процессов любого конкретного математика. Тут как будто имеет место обратное явление — человеческое мышление как бы само оказывается направляемым к некой внешней истине — истине, которая реальна сама по себе, и которая открывается каждому из нас лишь частично.
...
Что такое математика — изобретение или открытие? Процесс получения математиками результатов — что это: всего лишь построение не существующих в действительности сложных мысленных конструкций, мощь и элегантность которых способна обмануть даже их собственных изобретателей, заставив их поверить в «реальность» этих не более чем умозрительных построений? Или же математики действительно открывают истины уже где-то существующие, чья реальность в значительной степени независима от их деятельности? Я думаю, что читателю должно стать уже совершенно ясно, что я склонен придерживаться скорее второй, чем первой точки зрения, по крайней мере, в отношении таких структур, как комплексные числа или множество Мандельброта
Отрывок из книги Роджера Пенроуза «Новый ум короля» 

Вот и получается, что знание общего помогает лучше понять частности.
Позвольте не согласиться с Вашим выводом:
- «Смысл этой теоремы сводится к тому, что независимо от нашего мнения об универсальности применяемого подхода, всегда найдутся утверждения, которые не попадают в сферу его действия. Другими словами «достаточно общая ТЕОРИЯ управления» не является «достаточно общей» и это доказанный математический факт»
-- Из оного вытекает лишь то, что ДОТУ не является ОБЩЕЙ теорией, но не вытекает то, что она не является ДОСТАТОЧНО ОБЩЕЙ ( в смысле достаточной для описания процессов ).
 
И ещё. Теорема Гёделя появилась, как раз, в результате тщетных попыток доказать правильность математических аксиом математическими инструментами. Теорема Гёделя верна как в отношении математики так и в отношении ДОТУ. И в этом плане математика от ДОТУ не отличается, можно поставить =. То есть ни ДОТУ ни математика не  являются общими (универсальными, всеобъемлющими) аппаратами для описания мироздания. А только лишь ДОСТАТОЧНО общими.

//Из оного вытекает лишь то, что ДОТУ не является ОБЩЕЙ теорией, но не вытекает то, что она не является ДОСТАТОЧНО ОБЩЕЙ//
Отлично отписал!
.
//Теорема Гёделя верна как в отношении математики так и в отношении ДОТУ. И в этом плане математика от ДОТУ не отличается, можно поставить =.//
Ого-го! Значит в школах уже давно и всю дорогу преподают ДОТУ!? (ну, если математика=ДОТУ) А мы то и не знали....
А в знаке "=" заложена ли информация, что это равенство лишь некое относительно чего-то другого, а не строго равно? Нет? Ну так тогда это "равенство" не равенство, т.к. зависит от каких-то ещё сторонних рассуждений.
Пример такой логики: 2 и 7 - оба больше 10, значит 2=7 !
Недалеко с таким можно зайти.
И математика, и её подмножество ДОТУ - часть Вселенной, значит не могут описать происходящее вне Вселенной. Но точно так же и астрономия или микроэлектроника не могут описать Надмирную Реальность. Приравняем и их всех докучи?
ДОТУ=математика=астрономия=микроэлектроника ?

Поправочка:
Пример такой логики: 2 и 7 - оба меньше 10, значит 2=7 !

Товарищъ Ываывыаывааа, вам известно понятие контекст или понятие относительность?

Конечно, я что-то слышал об этом.
И вполне согласен: в контексте 10-ки, 2-ку можно считать равной 7-ке

И вполне согласен: в контексте 10-ки, 2-ку можно считать равной 7-ке
Когда нужно обосновать подобное утверждение на помощь приходит кольцо вычетов по модулю n. В нашем случае в кольце вычетов по модулю 5 выражение «2 = 7» будет истинным. Однако чтобы не запутаться, а точнее не забыть, что все эти чудеса происходят в рамках группы, принято говорить вместо равно «сравнимо по модулю»

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


Возвращаясь к утверждению, породившему данный пример логики, хотелось бы отметить, что теорему Гёделя доказывали не ради какой-то конкретной задачи. Дело в том, что физики привыкли пользоваться и не доказанными фактами, лишь бы они работали. Смысл доказательств в возможности выйти на новые горизонты.

В рамках нашего обсуждения, математику можно сравнить с грядкой, а теорию (ДОТУ) с кустом на ней. На этой грядке есть и другие кусты. Так вот, теорема Гёделя имеет отношение к кустам, но не к самой грядке. На одном из кустов 2=7, на другом нет. Но не один куст не заменит всю грядку.
Сложно вам что-либо возразить. Если помните фильм «Клерки 2» момент, где Рэндал слышит историю про Проклапика… похожее чувство.
 
И математика, и её подмножество ДОТУ - часть Вселенной, значит не могут описать происходящее вне Вселенной
Ваше сознание — часть вас. Значит ли это ваше сознание не способно описать ничего вне вас? 

То, что ДОТУ ничего не может описать вне вселенной связано с её мировоззренческой основой, которая работает только с объективной реальностью. На мой взгляд это надуманное ограничение, поскольку положения ДОТУ прекрасно применимы в том числе и к виртуальным структурам (объектам не объективной реальности). Тут смысл в том, что граница вселенной проходит не где-то в далёких галактиках, она находится прямо перед нами.

Математическому же ощупыванию доступны сущности даже за пределами объективной реальности.
Математическому же ощупыванию доступны сущности даже за пределами объективной реальности.
Это да, интересный момент!

Конечно интересный!
И в этом контексте:
безконечность = 100
Потому, что больше 10

Как говориться сам придумал, сам наехал. Не надоело сарказничать над своими же нелепостями ?

Не более, чем обсуждать то, чего мы приниципиально не можем познать.

Не более, чем обсуждать то, чего мы приниципиально не можем познать.
То есть те кто считают что могут познать — еретики и их надо на костер?
То что Вы ставите себе планку за которой что либо познать не можете, совсем не значит что другие тоже не могут. Не обольщайтесь тем что выяснили что есть граница, может быть не правы именно Вы.

//То есть те кто считают что могут познать — еретики и их надо на костер?//
Ну, каждый будет по своей нравственности. Кто на костёр тащить, а кто просто пойдёт дальше, дабы не терять времени попусту.
Познавайте, кто ж против!

//Математическому же ощупыванию доступны сущности даже за пределами объективной реальности.//
О, дальше больше, ждём вычисления формулы Бога.
А потом - ещё и предьявить Ему претензию, когда выяснится, что формула Ему не соответствует.
.
Сколько тысяч лет, а всё так же есть желающие "ухватить Бога за бороду"...

По Вашему, за пределами объективной реальности, кроме Творца, ни чего нет?

Всё, что там есть - это для нас и есть Творец.

Чтобы говорить о том, что находится за пределами объективной реальности, нужно договорить о правилах рассуждений. Этим вопросом занимается «теория познания». Смысл в том, что человеческому восприятию помимо нашей объективной реальности доступно пять видов реальностей. То есть предполагается, что даже если наша реальность единственная, существует бесконечно много не объективных реальностей. Физики же пошли дальше и воспользовавшись математической логикой придумали мультивселенную, но там разговор отдельный, потому что выйти за рамки одной объективной реальности в рамках модели мультивселенной — занятие возможное только теоретически.

Творец же, как его описывают материалы концепции находится как вне объективных реальностей мультивселенной, так и вне каких бы то ни было не объективных реальностей.
Звучит так, как если бы вы в ответ на доказательство одной теоремы, ткнули носом доказавшего в факт отстутствия доказательства на всё остальное. Понимаете, в математике всегда были пара тройка нерешаемых задач. Некоторые были настолько нерешаемыми, что их даже объявили задачами тысячелетия. 

Математики прекрасно понимают, что у их знаний есть границы. И если что-то вдруг из ранее недоказанного вдруг становится доказанным это значит лишь, что область непознанного увеличилась. И нерешаемых задач наоборот прибавится.

На ум пришел один отрывок, подходит под ситуацию: 

– Напрасно вы так отблагодарили Кими, – недовольно поднял руку учитель, – в новой картине вселенной еще многое доступно лишь математическому «ощупыванию» отдельных явлений. Вы забыли, что наука движется во тьме незнаемых глубин мира подобно слепцу с протянутыми руками, осязая неясные контуры. И лишь после громадного труда создаются аппараты исследования, могущие осветить неизвестное и приобщить его к познанному. Иван Ефремов «Час быка»
-- Из оного вытекает лишь то, что ДОТУ не является ОБЩЕЙ теорией, но не вытекает то, что она не является ДОСТАТОЧНО ОБЩЕЙ ( в смысле достаточной для описания процессов ).
Можете подробнее раскрыть разницу между «общая» и «достаточно общая»? 
 тщетных попыток доказать правильность математических аксиом математическими инструментами.
Не уверен, что утверждение в отношении аксиом применимо ко всей науке в целом. Моя оценка опирается на мнение Роджера Пенроуза, озвученное в его книге «Новый ум короля». Не исключаю, что оно может быть неточным.
Добавить комментарий

Развиваемые публикации

Новые комментарии