Ce cours fait partie de la Spécialisation Introduction to Discrete Mathematics for Computer Science

proposé par

University of California San Diego

National Research University Higher School of Economics

Spécialisation Introduction to Discrete Mathematics for Computer Science

University of California San Diego

À propos de ce cours

4.6

119 ratings

•

29 reviews

We invite you to a fascinating journey into Graph Theory — an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major mathematical results, and insights into the deep theories behind them.
In this course, among other intriguing applications, we will see how GPS systems find shortest routes, how engineers design integrated circuits, how biologists assemble genomes, why a political map can always be colored using a few colors. We will study Ramsey Theory which proves that in a large system, complete disorder is impossible!
By the end of the course, we will implement an algorithm which finds an optimal assignment of students to schools. This algorithm, developed by David Gale and Lloyd S. Shapley, was later recognized by the conferral of Nobel Prize in Economics.
As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students....

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.

Réinitialisez les dates limites selon votre disponibilité.

Approx. 13 heures pour terminer

Sous-titres : English

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.

Réinitialisez les dates limites selon votre disponibilité.

Approx. 13 heures pour terminer

Sous-titres : English

Section

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 vidéos (Total 52 min), 5 lectures, 5 quiz

Airlines Graph1 min

Knight Transposition2 min

Seven Bridges of Königsberg4 min

What is a Graph?7 min

Graph Examples2 min

Graph Applications3 min

Vertex Degree3 min

Paths5 min

Connectivity2 min

Directed Graphs3 min

Weighted Graphs2 min

Paths, Cycles and Complete Graphs2 min

Trees6 min

Bipartite Graphs4 min

Slides1 min

Slides1 min

Slides1 min

Slides1 min

Glossary10 min

Definitions10 min

Graph Types10 min

Section

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 vidéos (Total 89 min), 4 lectures, 6 quiz

Handshaking Lemma7 min

Total Degree5 min

Connected Components7 min

Guarini Puzzle: Code6 min

Lower Bound5 min

The Heaviest Stone6 min

Directed Acyclic Graphs10 min

Strongly Connected Components7 min

Eulerian Cycles4 min

Eulerian Cycles: Criteria11 min

Hamiltonian Cycles4 min

Genome Assembly12 min

Slides1 min

Slides1 min

Slides1 min

Glossary10 min

Computing the Number of Edges10 min

Number of Connected Components10 min

Number of Strongly Connected Components10 min

Eulerian Cycles2 min

Section

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 vidéos (Total 55 min), 4 lectures, 6 quiz

Road Repair3 min

Trees8 min

Minimum Spanning Tree6 min

Job Assignment3 min

Bipartite Graphs5 min

Matchings3 min

Hall's Theorem7 min

Subway Lines1 min

Planar Graphs3 min

Euler's Formula4 min

Applications of Euler's Formula7 min

Slides1 min

Slides1 min

Slides1 min

Glossary10 min

Trees10 min

Bipartite Graphs10 min

Planar Graphs10 min

Section

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 vidéos (Total 52 min), 5 lectures, 8 quiz

Map Coloring3 min

Graph Coloring3 min

Bounds on the Chromatic Number3 min

Applications3 min

Graph Cliques3 min

Cliques and Independent Sets3 min

Connections to Coloring1 min

Mantel's Theorem5 min

Balanced Graphs2 min

Ramsey Numbers2 min

Existence of Ramsey Numbers5 min

Antivirus System2 min

Vertex Covers3 min

König's Theorem8 min

Slides1 min

Slides1 min

Slides1 min

Slides1 min

Glossary10 min

Graph Coloring10 min

Cliques and Independent Sets10 min

Ramsey Numbers10 min

Vertex Covers10 min

4.6

par RH•Nov 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!

par DN•Nov 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.

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 communications, IT, mathematics, engineering, and more.
Learn more on www.hse.ru...

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....

When will I have access to the lectures and assignments?

Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.

What will I get if I subscribe to this Specialization?

When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.

What is the refund policy?

Is financial aid available?

D'autres questions ? Visitez le Centre d'Aide pour les Etudiants.

Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.