Princeton University

Algorithmes, partie II

Robert Sedgewick
Kevin Wayne

Instructeurs : Robert Sedgewick

328 679 déjà inscrits

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

(2,010 avis)

niveau Intermédiaire
Certaines connaissances prérequises
Planning flexible
Env. 62 heures
Apprenez à votre propre rythme
96%
La plupart des étudiants ont apprécié ce cours
Obtenez un aperçu d'un sujet et apprenez les principes fondamentaux.
4.9

(2,010 avis)

niveau Intermédiaire
Certaines connaissances prérequises
Planning flexible
Env. 62 heures
Apprenez à votre propre rythme
96%
La plupart des étudiants ont apprécié ce cours

Compétences que vous acquerrez

  • Catégorie : Graphiques
  • Catégorie : Structure des données
  • Catégorie : Algorithmes
  • Catégorie : Compression des données

Détails à connaître

Évaluations

13 devoirs

Enseigné en Anglais

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

Emplacement réservé

Il y a 14 modules dans ce cours

Bienvenue aux algorithmes, partie II.

Inclus

1 vidéo2 lectures

Nous définissons un graphe non orienté API et considérons les représentations de la matrice d'adjacence et des listes d'adjacence. Nous introduisons deux algorithmes classiques pour la recherche d'un graphe : la recherche en profondeur d'abord et la recherche en largeur d'abord. Nous examinons également le problème du calcul des composantes connectées et concluons par des problèmes et des applications connexes.

Inclus

6 vidéos2 lectures1 devoir

Dans ce cours, nous étudions les graphes dirigés. Nous commençons par la recherche en profondeur d'abord et la recherche en largeur d'abord dans les digraphes et nous décrivons des applications allant de la collecte des ordures à l'exploration du web. Ensuite, nous introduisons un algorithme basé sur la recherche en profondeur pour calculer l'ordre topologique d'un digraphe acyclique. Enfin, nous implémentons l'algorithme de Kosaraju-Sharir pour calculer les composantes fortes d'un digraphe.

Inclus

5 vidéos1 lecture1 devoir1 devoir de programmation

Dans ce cours, nous étudions le problème de l'arbre couvrant minimal. Nous commençons par étudier un algorithme générique de type "greedy" pour le problème. Ensuite, nous considérons et implémentons deux algorithmes classiques pour le problème - l'algorithme de Kruskal et l'algorithme de Prim. Nous concluons par quelques applications et problèmes ouverts.

Inclus

6 vidéos2 lectures1 devoir

Dans ce cours, nous étudions les problèmes des plus courts chemins. Nous commençons par analyser quelques propriétés de base des chemins les plus courts et un algorithme générique pour le problème. Nous introduisons et analysons l'algorithme de Dijkstra pour les problèmes de plus courts chemins avec des poids non négatifs. Ensuite, nous considérons un algorithme encore plus rapide pour les DAG, qui fonctionne même si les poids sont négatifs. Nous concluons avec l'algorithme de Bellman-Ford-Moore pour les digraphes pondérés par les arêtes sans cycles négatifs. Nous considérons également des applications allant du remplissage en fonction du contenu à l'arbitrage.

Inclus

5 vidéos1 lecture1 devoir1 devoir de programmation

Dans ce cours, nous introduisons les problèmes du flux maximal et de la coupe minimale. Nous commençons par l'algorithme de Ford-Fulkerson. Pour analyser sa correction, nous établissons le théorème maxflow-mincut. Ensuite, nous considérons une implémentation efficace de l'algorithme de Ford-Fulkerson, en utilisant la règle du plus court chemin augmentant. Enfin, nous considérons des applications, notamment l'appariement bipartite et l'élimination de baseball.

Inclus

6 vidéos2 lectures1 devoir1 devoir de programmation

Dans ce cours, nous examinons des algorithmes de tri spécialisés pour les chaînes de caractères et les objets apparentés. Nous commençons par un sous-programme permettant de trier des nombres entiers dans un petit intervalle. Nous examinons ensuite deux algorithmes de tri radix classiques, les tris radix LS et MSD. Ensuite, nous considérons une variante particulièrement efficace, qui est un hybride du tri radix MSD et du tri sélectif connu sous le nom de tri sélectif radix à trois voies. Nous concluons avec le tri par suffixe et les applications connexes.

Inclus

6 vidéos1 lecture1 devoir

Dans cet exposé, nous examinons des algorithmes spécialisés pour les tables de symboles avec des clés de type chaîne de caractères. Notre objectif est de créer une structure de données aussi rapide que le hachage et encore plus flexible que les arbres de recherche binaires. Nous commençons par des essais à plusieurs voies, puis nous considérons des essais de recherche ternaire. Enfin, nous examinons les opérations basées sur les caractères, y compris la correspondance des préfixes et le préfixe le plus long, ainsi que les applications correspondantes.

Inclus

3 vidéos2 lectures1 devoir

Dans ce cours, nous examinons les algorithmes de recherche d'une sous-chaîne dans un morceau de texte. Nous commençons par un algorithme de force brute, dont le temps d'exécution est quadratique dans le pire des cas. Ensuite, nous considérons l'ingénieux algorithme de Knuth-Morris-Pratt dont le temps d'exécution est garanti linéaire dans le pire des cas. Nous présentons ensuite l'algorithme de Boyer-Moore, dont le temps d'exécution est sous-linéaire pour des entrées typiques. Enfin, nous examinons l'algorithme d'empreintes digitales de Rabin-Karp, qui utilise le hachage de manière intelligente pour résoudre la recherche de chaînes de caractères et les problèmes connexes.

Inclus

5 vidéos1 lecture1 devoir1 devoir de programmation

Une expression régulière est une méthode permettant de spécifier un ensemble de chaînes de caractères. Le sujet de ce cours est le célèbre algorithme grep qui détermine si un texte donné contient une sous-chaîne de l'ensemble. Nous examinons une implémentation efficace qui utilise notre implémentation de l'accessibilité des digraphes de la semaine 1.

Inclus

5 vidéos2 lectures1 devoir

Nous étudions et mettons en œuvre plusieurs schémas classiques de compression de données, y compris le codage de longueur d'exécution, la compression de Huffman et la compression LZW. Nous développons des implémentations efficaces à partir des premiers principes en utilisant une bibliothèque Java pour la manipulation de données binaires que nous avons développée à cette fin, basée sur les implémentations de la file d'attente prioritaire et de la table de symboles des cours précédents.

Inclus

4 vidéos1 lecture1 devoir1 devoir de programmation

Nos cours de cette semaine sont centrés sur l'idée de modèles de résolution de problèmes tels que le maxflow et le chemin le plus court, où un nouveau problème peut être formulé comme une instance de l'un de ces problèmes, et ensuite résolu avec un algorithme classique et efficace. Pour compléter le cours, nous décrivons le problème classique non résolu de l'informatique théorique qui est centré sur le concept d'efficacité des algorithmes et qui nous guide dans la recherche de solutions efficaces à des problèmes difficiles.

Inclus

4 vidéos2 lectures1 devoir

La quintessence du modèle de résolution de problèmes est connue sous le nom de programmation linéaire, et la méthode du simplexe pour la résoudre est l'un des algorithmes les plus utilisés. Dans ce cours, nous donnons un aperçu de ce sujet central de la recherche opérationnelle et décrivons sa relation avec les algorithmes que nous avons étudiés.

Inclus

4 vidéos1 lecture1 devoir

Existe-t-il un modèle universel de résolution de problèmes auquel se ramènent tous les problèmes que nous aimerions résoudre et pour lequel nous connaissons un algorithme efficace ? Vous serez peut-être surpris d'apprendre que nous ne connaissons pas la réponse à cette question. Dans ce cours, nous introduisons les classes de complexité P, NP et NP-complet, nous posons la fameuse question P = NP et nous examinons les implications dans le contexte des algorithmes que nous avons traités dans ce cours.

Inclus

6 vidéos1 lecture1 devoir

Instructeurs

Évaluations de l’enseignant
4.8 (290 évaluations)
Robert Sedgewick
Princeton University
7 Cours1 877 083 apprenants
Kevin Wayne
Princeton University
5 Cours1 831 139 apprenants

Offert par

Princeton University

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

4.9

2 010 avis

  • 5 stars

    93,59 %

  • 4 stars

    5,21 %

  • 3 stars

    0,49 %

  • 2 stars

    0,24 %

  • 1 star

    0,44 %

Affichage de 3 sur 2010

MP
5

Révisé le 12 janv. 2024

MS
5

Révisé le 27 févr. 2021

TD
5

Révisé le 19 mars 2019

Emplacement réservé

Ouvrez de nouvelles portes avec Coursera Plus

Accès illimité à 10,000+ cours de niveau international, projets pratiques et programmes de certification prêts à l'emploi - 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