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.
Este curso faz parte do Programa de cursos integrados Introduction to Discrete Mathematics for Computer Science
oferecido por
Universidade da Califórnia, San Diego
National Research University Higher School of Economics
Programa de cursos integrados Introduction to Discrete Mathematics for Computer ScienceUniversidade da Califórnia, San DiegoInformações sobre o curso
143,560 visualizações recentes
Resultados de carreira do aprendiz
33%
comecei uma nova carreira após concluir estes cursos
50%
consegui um benefício significativo de carreira com este curso
33%
recebi um aumento ou promoção
Certificados compartilháveis
Tenha o certificado após a conclusão
100% on-line
Comece imediatamente e aprenda em seu próprio cronograma.
Prazos flexíveis
Redefinir os prazos de acordo com sua programação.
Nível iniciante
Aprox. 20 horas para completar
Inglês
Legendas: Inglês, Grego
Resultados de carreira do aprendiz
33%
comecei uma nova carreira após concluir estes cursos
50%
consegui um benefício significativo de carreira com este curso
33%
recebi um aumento ou promoção
Certificados compartilháveis
Tenha o certificado após a conclusão
100% on-line
Comece imediatamente e aprenda em seu próprio cronograma.
Prazos flexíveis
Redefinir os prazos de acordo com sua programação.
Nível iniciante
Aprox. 20 horas para completar
Inglês
Legendas: Inglês, Grego
oferecido por
Universidade da Califórnia, 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 communicamathematics, engineering, and more.
Programa - O que você aprenderá com este curso
3 horas para concluir
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.
3 horas para concluir
14 vídeos (Total 52 mín.), 5 leituras, 5 testes
14 videos
Airlines Graph1min
Knight Transposition2min
Seven Bridges of Königsberg4min
What is a Graph?7min
Graph Examples2min
Graph Applications3min
Vertex Degree3min
Paths5min
Connectivity2min
Directed Graphs3min
Weighted Graphs2min
Paths, Cycles and Complete Graphs2min
Trees6min
Bipartite Graphs4min
5 leituras
Slides1min
Slides1min
Slides1min
Slides1min
Glossary10min
2 exercícios práticos
Definitions10min
Graph Types10min
5 horas para concluir
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!
5 horas para concluir
12 vídeos (Total 89 mín.), 4 leituras, 6 testes
12 videos
Total Degree5min
Connected Components7min
Guarini Puzzle: Code6min
Lower Bound5min
The Heaviest Stone6min
Directed Acyclic Graphs10min
Strongly Connected Components7min
Eulerian Cycles4min
Eulerian Cycles: Criteria11min
Hamiltonian Cycles4min
Genome Assembly12min
4 leituras
Slides1min
Slides1min
Slides1min
Glossary10min
4 exercícios práticos
Computing the Number of Edges10min
Number of Connected Components10min
Number of Strongly Connected Components10min
Eulerian Cycles30min
4 horas para concluir
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!
4 horas para concluir
11 vídeos (Total 55 mín.), 4 leituras, 6 testes
11 videos
Road Repair3min
Trees8min
Minimum Spanning Tree6min
Job Assignment3min
Bipartite Graphs5min
Matchings3min
Hall's Theorem7min
Subway Lines1min
Planar Graphs3min
Euler's Formula4min
Applications of Euler's Formula7min
4 leituras
Slides1min
Slides1min
Slides1min
Glossary10min
3 exercícios práticos
Trees10min
Bipartite Graphs10min
Planar Graphs10min
4 horas para concluir
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.
4 horas para concluir
14 vídeos (Total 52 mín.), 5 leituras, 8 testes
14 videos
Map Coloring3min
Graph Coloring3min
Bounds on the Chromatic Number3min
Applications3min
Graph Cliques3min
Cliques and Independent Sets3min
Connections to Coloring1min
Mantel's Theorem5min
Balanced Graphs2min
Ramsey Numbers2min
Existence of Ramsey Numbers5min
Antivirus System2min
Vertex Covers3min
König's Theorem8min
5 leituras
Slides1min
Slides1min
Slides1min
Slides1min
Glossary10min
4 exercícios práticos
Graph Coloring10min
Cliques and Independent Sets10min
Ramsey Numbers10min
Vertex Covers10min
Avaliações
Principais avaliações do INTRODUCTION TO GRAPH THEORY
por SU27 de Fev de 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.
por RH16 de Nov de 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!
por SS6 de Jun de 2020
Week 5 was very confusing and not well curated. Please fix this.I had to lookup youtube videos to understand the concepts and that defeats the purpose of me taking the course on coursera
por TT31 de Dez de 2017
This course is interesting, and it is a good introduction. I like the first four weeks' courses, while I feel the last week's course is not clear presented, which changes the instructor.
Sobre Programa de cursos integrados Introduction to Discrete Mathematics for Computer Science
Discrete Mathematics is the language of Computer Science. One needs to be fluent in it to work in many fields including data science, machine learning, and software engineering (it is not a coincidence that math puzzles are often used for interviews). We introduce you to this language through a fun try-this-before-we-explain-everything approach: first you solve many interactive puzzles that are carefully designed specifically for this online specialization, and then we explain how to solve the puzzles, and introduce important ideas along the way. We believe that this way, you will get a deeper understanding and will better appreciate the beauty of the underlying ideas (not to mention the self confidence that you gain if you invent these ideas on your own!). To bring your experience closer to IT-applications, we incorporate programming examples, problems, and projects in the specialization.
Perguntas Frequentes – FAQ
Quando terei acesso às palestras e às tarefas?
Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:
- The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
- The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
O que recebo ao me inscrever nesta Especialização?
Quando você se inscreve no curso, tem acesso a todos os cursos na Especialização e pode obter um certificado quando concluir o trabalho. Seu Certificado eletrônico será adicionado à sua página de Participações e você poderá imprimi-lo ou adicioná-lo ao seu perfil no LinkedIn. Se quiser apenas ler e assistir o conteúdo do curso, você poderá frequentá-lo como ouvinte sem custo.
Qual é a política de reembolso?
Se você se inscrever, terá 7 dias para testar sem custo e, durante este período, pode cancelar sem multa. Depois disso, não reembolsamos, mas você pode cancelar sua inscrição a qualquer momento. Veja nossa política para o reembolso total.
Existe algum auxílio financeiro disponível?
Sim, a Coursera oferece auxílio financeiro ao aluno que não possa pagar a taxa. Faça a solicitação clicando no link Auxílio Financeiro, abaixo do botão "Inscreva-se" à esquerda. Preencha uma solicitação e será notificado caso seja aprovado. Você terá que completar esta etapa para cada curso na Especialização, incluindo o Trabalho de Conclusão de Curso. Saiba mais .
Ganharei créditos universitários por concluir o curso?
Este curso não oferece créditos universitários, mas algumas universidades podem aceitar certificados de cursos que podem ser convertidos em créditos. Entre em contato com sua instituição para saber mais. Com os cursos on-line e os certificados Mastertrack™ do Coursera, é possível ganhar créditos universitários.
Mais dúvidas? Visite o Central de Ajuda ao Aprendiz.
