Nous vous invitons à un voyage fascinant dans la théorie des graphes - un domaine qui allie l'élégance de la peinture et la rigueur des mathématiques ; il est simple, mais non dépourvu de sophistication. La théorie des graphes nous offre à la fois un moyen facile de représenter picturalement de nombreux résultats mathématiques majeurs et un aperçu des théories profondes qui les sous-tendent.
Offrez à votre carrière le cadeau de Coursera Plus avec $160 de réduction, facturé annuellement. Économisez aujourd’hui.
Introduction à la théorie des graphes
Ce cours fait partie de Spécialisation Introduction aux mathématiques discrètes pour l'informatique
Instructeurs : Alexander S. Kulikov
53 558 déjà inscrits
Inclus avec
(1,042 avis)
Détails à connaître
Ajouter à votre profil LinkedIn
30 devoirs
Découvrez comment les employés des entreprises prestigieuses maîtrisent des compétences recherchées
Élaborez votre expertise du sujet
- 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
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
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
Offert par
Recommandé si vous êtes intéressé(e) par Algorithmes
Rice University
University of Colorado Boulder
Fractal Analytics
Shanghai Jiao Tong University
Pour quelles raisons les étudiants sur Coursera nous choisissent-ils pour leur carrière ?
Avis des étudiants
Affichage de 3 sur 1042
1 042 avis
- 5 stars
66,31 %
- 4 stars
23,60 %
- 3 stars
6,62 %
- 2 stars
2,11 %
- 1 star
1,34 %
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
L'accès aux cours et aux devoirs dépend de votre type d'inscription. Si vous suivez un cours en mode audit, vous pourrez consulter gratuitement la plupart des supports de cours. Pour accéder aux devoirs notés et obtenir un certificat, vous devrez acheter l'expérience de certificat, pendant ou après votre audit. Si vous ne voyez pas l'option d'audit :
Il se peut que le cours ne propose pas d'option d'audit. Vous pouvez essayer un essai gratuit ou demander une aide financière.
Le cours peut proposer l'option "Cours complet, pas de certificat" à la place. Cette option vous permet de consulter tous les supports de cours, de soumettre les évaluations requises et d'obtenir une note finale. Cela signifie également que vous ne pourrez pas acheter un certificat d'expérience.
Lorsque vous vous inscrivez au cours, vous avez accès à tous les cours de la Specializations, et vous obtenez un certificat lorsque vous terminez le travail. Votre certificat électronique sera ajouté à votre page de réalisations - de là, vous pouvez imprimer votre certificat ou l'ajouter à votre profil LinkedIn. Si vous souhaitez uniquement lire et visualiser le contenu du cours, vous pouvez auditer le cours gratuitement.
Si vous vous êtes abonné, vous bénéficiez d'une période d'essai gratuite de 7 jours pendant laquelle vous pouvez annuler votre abonnement sans pénalité. Après cette période, nous ne remboursons pas, mais vous pouvez résilier votre abonnement à tout moment. Consultez notre politique de remboursement complète.