University of California San Diego
Introduction à la théorie des graphes

Offrez à votre carrière le cadeau de Coursera Plus avec $160 de réduction, facturé annuellement. Économisez aujourd’hui.

University of California San Diego

Introduction à la théorie des graphes

Alexander S. Kulikov
Владимир Подольский

Instructeurs : Alexander S. Kulikov

53 558 déjà inscrits

Inclus avec Coursera Plus

Obtenez un aperçu d'un sujet et apprenez les principes fondamentaux.
4.5

(1,042 avis)

niveau Débutant
Aucune connaissance prérequise
Planning flexible
Env. 20 heures
Apprenez à votre propre rythme
88%
La plupart des apprenants ont aimé ce cours
Obtenez un aperçu d'un sujet et apprenez les principes fondamentaux.
4.5

(1,042 avis)

niveau Débutant
Aucune connaissance prérequise
Planning flexible
Env. 20 heures
Apprenez à votre propre rythme
88%
La plupart des apprenants ont aimé ce cours

Détails à connaître

Certificat partageable

Ajouter à votre profil LinkedIn

Évaluations

30 devoirs

Enseigné en Anglais

Découvrez comment les employés des entreprises prestigieuses maîtrisent des compétences recherchées

Emplacement réservé

Élaborez votre expertise du sujet

Ce cours fait partie de la Spécialisation Introduction aux mathématiques discrètes pour l'informatique
Lorsque vous vous inscrivez à ce cours, vous êtes également inscrit(e) à cette Spécialisation.
  • Apprenez de nouveaux concepts auprès d'experts du secteur
  • Acquérez une compréhension de base d'un sujet ou d'un outil
  • Développez des compétences professionnelles avec des projets pratiques
  • Obtenez un certificat professionnel partageable
Emplacement réservé
Emplacement réservé

Obtenez un certificat professionnel

Ajoutez cette qualification à votre profil LinkedIn ou à votre CV

Partagez-le sur les réseaux sociaux et dans votre évaluation de performance

Emplacement réservé

Il y a 5 modules dans ce cours

Qu'est-ce qu'un graphique ? Pourquoi en avons-nous besoin ? Cette semaine, nous verrons qu'un graphique est un moyen simple de représenter presque toutes les relations entre des objets. Nous verrons que nous utilisons des applications graphiques tous les jours ! Nous apprendrons ce que sont les graphes, quand et comment les utiliser, comment les dessiner, et nous verrons également les classes de graphes les plus importantes. Nous commencerons par deux puzzles interactifs. Bien qu'ils soient difficiles, ils démontrent très bien la puissance de la théorie des graphes ! Si vous ne trouvez pas ces énigmes faciles, veuillez consulter les vidéos et les documents de lecture qui les suivent.

Inclus

14 vidéos6 lectures5 devoirs1 laboratoire non noté

Nous examinerons les composantes connectées d'un graphe et la manière dont elles peuvent être utilisées pour mettre en œuvre un programme simple permettant de résoudre l'énigme de Guarini et de prouver l'optimalité d'un certain protocole. Nous verrons comment trouver un ordre valide dans une liste de tâches ou un graphe de dépendance de projet. Enfin, nous découvrirons la différence spectaculaire entre les cycles eulériens et les cycles hamiltoniens, apparemment similaires, et nous verrons comment ils sont utilisés dans l'assemblage du génome !

Inclus

12 vidéos4 lectures7 devoirs5 laboratoires non notés

Cette semaine, nous étudierons trois grandes classes de graphes : les arbres, les graphes bipartis et les graphes planaires. Nous définirons les arbres à portée minimale, puis nous développerons un algorithme qui trouve le moyen le moins coûteux de relier des villes arbitraires. Nous étudierons les correspondances dans les graphes bipartites et verrons quand un ensemble d'emplois peut être pourvu par des candidats. Nous apprendrons également ce que sont les graphes planaires et verrons quand les stations de métro peuvent être reliées sans intersection. Restez à l'écoute pour d'autres énigmes interactives !

Inclus

11 vidéos4 lectures6 devoirs2 laboratoires non notés

Nous nous concentrerons sur les paramètres des graphes et les problèmes qui y sont liés. Tout d'abord, nous définirons la coloration des graphes et nous verrons pourquoi les cartes politiques peuvent être colorées en seulement quatre couleurs. Ensuite, nous verrons comment les cliques et les ensembles indépendants sont liés dans les graphes. En utilisant ces notions, nous prouverons le théorème de Ramsey qui stipule que dans un grand système, le désordre complet est impossible ! Enfin, nous étudierons les couvertures de sommets et apprendrons à trouver le nombre minimum d'ordinateurs qui contrôlent toutes les connexions du réseau.

Inclus

14 vidéos5 lectures8 devoirs1 laboratoire non noté

Cette semaine, nous allons développer un algorithme qui détermine la quantité maximale d'eau qui peut être acheminée dans un réseau d'approvisionnement en eau donné. Cet algorithme est également utilisé dans la pratique pour l'optimisation du trafic routier et la planification des vols des compagnies aériennes. Nous verrons comment les flux dans les réseaux sont liés aux correspondances dans les graphes bipartis. Nous développerons ensuite un algorithme qui trouve des correspondances stables dans les graphes bipartis. Cet algorithme résout le problème de l'appariement des étudiants avec les écoles, des médecins avec les hôpitaux et des donneurs d'organes avec les patients. À la fin de cette semaine, nous mettrons en œuvre un algorithme qui a remporté le prix Nobel d'économie !

Inclus

13 vidéos6 lectures4 devoirs

Instructeurs

Évaluations de l’enseignant
4.3 (161 évaluations)
Alexander S. Kulikov
University of California San Diego
13 Cours818 627 apprenants
Владимир Подольский
8 Cours222 717 apprenants

Offert par

Recommandé si vous êtes intéressé(e) par Algorithmes

Pour quelles raisons les étudiants sur Coursera nous choisissent-ils pour leur carrière ?

Felipe M.
Étudiant(e) depuis 2018
’Pouvoir suivre des cours à mon rythme à été une expérience extraordinaire. Je peux apprendre chaque fois que mon emploi du temps me le permet et en fonction de mon humeur.’
Jennifer J.
Étudiant(e) depuis 2020
’J'ai directement appliqué les concepts et les compétences que j'ai appris de mes cours à un nouveau projet passionnant au travail.’
Larry W.
Étudiant(e) depuis 2021
’Lorsque j'ai besoin de cours sur des sujets que mon université ne propose pas, Coursera est l'un des meilleurs endroits où se rendre.’
Chaitanya A.
’Apprendre, ce n'est pas seulement s'améliorer dans son travail : c'est bien plus que cela. Coursera me permet d'apprendre sans limites.’

Avis des étudiants

Affichage de 3 sur 1042

4.5

1 042 avis

  • 5 stars

    66,31 %

  • 4 stars

    23,60 %

  • 3 stars

    6,62 %

  • 2 stars

    2,11 %

  • 1 star

    1,34 %

KG
5

Révisé le 8 avr. 2019

LT
5

Révisé le 11 déc. 2017

AT
5

Révisé le 24 nov. 2017

Emplacement réservé

Ouvrez de nouvelles portes avec Coursera Plus

Accès illimité à plus de 7 000 cours de renommée internationale, à des projets pratiques et à des programmes de certificats reconnus sur le marché du travail, tous inclus dans votre abonnement

Faites progresser votre carrière avec un diplôme en ligne

Obtenez un diplôme auprès d’universités de renommée mondiale - 100 % en ligne

Rejoignez plus de 3 400 entreprises mondiales qui ont choisi Coursera pour les affaires

Améliorez les compétences de vos employés pour exceller dans l’économie numérique

Foire Aux Questions