Об этом курсе
4.6
Оценки: 139
Рецензии: 32
100% онлайн

100% онлайн

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

Гибкие сроки

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

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

Часов на завершение

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

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

Английский

Субтитры: Английский
100% онлайн

100% онлайн

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

Гибкие сроки

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

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

Часов на завершение

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

Предполагаемая нагрузка: 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....
Reading
14 videos (Total 52 min), 5 материалов для самостоятельного изучения, 5 тестов
Video14 видео
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мин
Reading5 материала для самостоятельного изучения
Slides1мин
Slides1мин
Slides1мин
Slides1мин
Glossary10мин
Quiz2 практического упражнения
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! ...
Reading
12 videos (Total 89 min), 4 материалов для самостоятельного изучения, 6 тестов
Video12 видео
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мин
Reading4 материала для самостоятельного изучения
Slides1мин
Slides1мин
Slides1мин
Glossary10мин
Quiz4 практического упражнения
Computing the Number of Edges10мин
Number of Connected Components10мин
Number of Strongly Connected Components10мин
Eulerian Cycles2мин
Неделя
3
Часов на завершение
3 ч. на завершение

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!...
Reading
11 videos (Total 55 min), 4 материалов для самостоятельного изучения, 6 тестов
Video11 видео
Trees8мин
Minimum Spanning Tree6мин
Job Assignment3мин
Bipartite Graphs5мин
Matchings3мин
Hall's Theorem7мин
Subway Lines1мин
Planar Graphs3мин
Euler's Formula4мин
Applications of Euler's Formula7мин
Reading4 материала для самостоятельного изучения
Slides1мин
Slides1мин
Slides1мин
Glossary10мин
Quiz3 практического упражнения
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....
Reading
14 videos (Total 52 min), 5 материалов для самостоятельного изучения, 8 тестов
Video14 видео
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мин
Reading5 материала для самостоятельного изучения
Slides1мин
Slides1мин
Slides1мин
Slides1мин
Glossary10мин
Quiz4 практического упражнения
Graph Coloring10мин
Cliques and Independent Sets10мин
Ramsey Numbers10мин
Vertex Covers10мин
4.6
Рецензии: 32Chevron Right

Лучшие рецензии

автор: 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!

автор: DNNov 12th 2017

I like this course. Very basic, but teachers are really great and explanations are perfect! Highly recommended for all who wants to begin with Graph Theory.

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

Avatar

Alexander S. Kulikov

Visiting Professor
Department of Computer Science and Engineering

О University of California San Diego

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

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 communications, IT, mathematics, 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. Просто ознакомиться с содержанием курса можно бесплатно.

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