Двигатель

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

13 февраля 2017 в 23:22 |

Емеля |Henson | 2010 | 0

Ключи: наука

П К О Б

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

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

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

О курсе

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

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

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

Требования

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

Понятие графа и виды графов.
Различные применения графов: от Кенигсберских мостов до Интернета.
Связность графа, подграфы и степень вершины.
Эквивалентные определения деревьев.
Планарность и критерий Куратовского
Формула Эйлера.
Хроматическое число планарного графа.
Перечисление деревьев: код Прюфера и формула Кэли.
Формула для числа унициклических графов.
Эйлеровы циклы и критерий эйлеровости.
Гамильтоновы циклы. Критерий Дирака и критерий Хватала.
Паросочетания. Теорема Холла и Кенига.
Экстремальная теория графов. Теорема Турана.
Аналог теоремы Турана для графов на плоскости.
Теория Рамсея. Знакомства среди шести человек.
Определение числа Рамсея.
Нижняя и верхняя оценки чисел Рамсея.

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

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

Источник