Об этом курсе
Недавно просмотрено: 28,627

100% онлайн

Начните сейчас и учитесь по собственному графику.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Начальный уровень

Прибл. 15 часа на выполнение

Предполагаемая нагрузка: 5 weeks, 3-5 hours/week ...

Английский

Субтитры: Английский, Греческий

100% онлайн

Начните сейчас и учитесь по собственному графику.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Начальный уровень

Прибл. 15 часа на выполнение

Предполагаемая нагрузка: 5 weeks, 3-5 hours/week ...

Английский

Субтитры: Английский, Греческий

Программа курса: что вы изучите

Неделя
1
3 ч. на завершение

What is a Graph?

What are graphs? What do we need them for? This week we'll see that a graph is a simple pictorial way to represent almost any relations between objects. We'll see that we use graph applications daily! We'll learn what graphs are, when and how to use them, how to draw graphs, and we'll also see the most important graph classes. We start off with two interactive puzzles. While they may be hard, they demonstrate the power of graph theory very well! If you don't find these puzzles easy, please see the videos and reading materials after them.

...
14 видео ((всего 52 мин.)), 5 материалов для самостоятельного изучения, 5 тестов
14 видео
Knight Transposition2мин
Seven Bridges of Königsberg4мин
What is a Graph?7мин
Graph Examples2мин
Graph Applications3мин
Vertex Degree3мин
Paths5мин
Connectivity2мин
Directed Graphs3мин
Weighted Graphs2мин
Paths, Cycles and Complete Graphs2мин
Trees6мин
Bipartite Graphs4мин
5 материала для самостоятельного изучения
Slides1мин
Slides1мин
Slides1мин
Slides1мин
Glossary10мин
2 практического упражнения
Definitions10мин
Graph Types10мин
Неделя
2
5 ч. на завершение

CYCLES

We’ll consider connected components of a graph and how they can be used to implement a simple program for solving the Guarini puzzle and for proving optimality of a certain protocol. We’ll see how to find a valid ordering of a to-do list or project dependency graph. Finally, we’ll figure out the dramatic difference between seemingly similar Eulerian cycles and Hamiltonian cycles, and we’ll see how they are used in genome assembly!

...
12 видео ((всего 89 мин.)), 4 материалов для самостоятельного изучения, 6 тестов
12 видео
Total Degree5мин
Connected Components7мин
Guarini Puzzle: Code6мин
Lower Bound5мин
The Heaviest Stone6мин
Directed Acyclic Graphs10мин
Strongly Connected Components7мин
Eulerian Cycles4мин
Eulerian Cycles: Criteria11мин
Hamiltonian Cycles4мин
Genome Assembly12мин
4 материала для самостоятельного изучения
Slides1мин
Slides1мин
Slides1мин
Glossary10мин
4 практического упражнения
Computing the Number of Edges10мин
Number of Connected Components10мин
Number of Strongly Connected Components10мин
Eulerian Cycles2мин
Неделя
3
4 ч. на завершение

Graph Classes

This week we will study three main graph classes: trees, bipartite graphs, and planar graphs. We'll define minimum spanning trees, and then develop an algorithm which finds the cheapest way to connect arbitrary cities. We'll study matchings in bipartite graphs, and see when a set of jobs can be filled by applicants. We'll also learn what planar graphs are, and see when subway stations can be connected without intersections. Stay tuned for more interactive puzzles!

...
11 видео ((всего 55 мин.)), 4 материалов для самостоятельного изучения, 6 тестов
11 видео
Trees8мин
Minimum Spanning Tree6мин
Job Assignment3мин
Bipartite Graphs5мин
Matchings3мин
Hall's Theorem7мин
Subway Lines1мин
Planar Graphs3мин
Euler's Formula4мин
Applications of Euler's Formula7мин
4 материала для самостоятельного изучения
Slides1мин
Slides1мин
Slides1мин
Glossary10мин
3 практического упражнения
Trees10мин
Bipartite Graphs10мин
Planar Graphs10мин
Неделя
4
4 ч. на завершение

Graph Parameters

We'll focus on the graph parameters and related problems. First, we'll define graph colorings, and see why political maps can be colored in just four colors. Then we will see how cliques and independent sets are related in graphs. Using these notions, we'll prove Ramsey Theorem which states that in a large system, complete disorder is impossible! Finally, we'll study vertex covers, and learn how to find the minimum number of computers which control all network connections.

...
14 видео ((всего 52 мин.)), 5 материалов для самостоятельного изучения, 8 тестов
14 видео
Graph Coloring3мин
Bounds on the Chromatic Number3мин
Applications3мин
Graph Cliques3мин
Cliques and Independent Sets3мин
Connections to Coloring1мин
Mantel's Theorem5мин
Balanced Graphs2мин
Ramsey Numbers2мин
Existence of Ramsey Numbers5мин
Antivirus System2мин
Vertex Covers3мин
König's Theorem8мин
5 материала для самостоятельного изучения
Slides1мин
Slides1мин
Slides1мин
Slides1мин
Glossary10мин
4 практического упражнения
Graph Coloring10мин
Cliques and Independent Sets10мин
Ramsey Numbers10мин
Vertex Covers10мин
4.6
Рецензии: 50Chevron Right

33%

начал новую карьеру, пройдя эти курсы

50%

получил значимые преимущества в карьере благодаря этому курсу

33%

стал больше зарабатывать или получил повышение

Лучшие отзывы о курсе Introduction to Graph Theory

автор: SUFeb 28th 2019

Appreciate the structure and the explanations with examples. The practice tool before every lesson not makes it fun to learn but also sets the student in the context and can anticipate the concept.

автор: RHNov 17th 2017

Was pretty fun and gave a good intro to graph theory. Definitely felt inspired to go deeper and understood the most basic proof ideas. The later lectures can spike in difficulty though. Very nice!

Преподаватели

Avatar

Alexander S. Kulikov

Visiting Professor
Department of Computer Science and Engineering

О Калифорнийский университет в Сан-Диего

UC San Diego is an academic powerhouse and economic engine, recognized as one of the top 10 public universities by U.S. News and World Report. Innovation is central to who we are and what we do. Here, students learn that knowledge isn't just acquired in the classroom—life is their laboratory....

О Национальный исследовательский университет "Высшая школа экономики"

National Research University - Higher School of Economics (HSE) is one of the top research universities in Russia. Established in 1992 to promote new research and teaching in economics and related disciplines, it now offers programs at all levels of university education across an extraordinary range of fields of study including business, sociology, cultural studies, philosophy, political science, international relations, law, Asian studies, media and communicamathematics, engineering, and more. Learn more on www.hse.ru...

О специализации ''Introduction to Discrete Mathematics for Computer Science'

Discrete Math is needed to see mathematical structures in the object you work with, and understand their properties. This ability is important for software engineers, data scientists, security and financial analysts (it is not a coincidence that math puzzles are often used for interviews). We cover the basic notions and results (combinatorics, graphs, probability, number theory) that are universally needed. To deliver techniques and ideas in discrete mathematics to the learner we extensively use interactive puzzles specially created for this specialization. To bring the learners experience closer to IT-applications we incorporate programming examples, problems and projects in our courses....
Introduction to Discrete Mathematics for Computer Science

Часто задаваемые вопросы

  • Зарегистрировавшись на сертификацию, вы получите доступ ко всем видео, тестам и заданиям по программированию (если они предусмотрены). Задания по взаимной оценке сокурсниками можно сдавать и проверять только после начала сессии. Если вы проходите курс без оплаты, некоторые задания могут быть недоступны.

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

Остались вопросы? Посетите Центр поддержки учащихся.