# 111 – Richard Karp: Algorithmes et complexité de calcul | Mit

Podcast: Jouer dans une nouvelle fenêtre | Télécharger

S’abonner: Spotify | Mélo |

Richard Karp est professeur à Berkeley et l’une des figures les plus importantes de l’histoire de l’informatique théorique. En 1985, il a reçu le prix Turing pour ses recherches sur la théorie des algorithmes, y compris le développement de l’algorithme Edmonds – Karp pour résoudre le problème maximal d’écoulement sur les réseaux, l’algorithme Hopcroft – Karp NP-complete. Cet article était probablement le catalyseur le plus important dans l’explosion de l’intérêt pour l’étude de la complétude NP et du problème P VS NP.

Soutenez ce podcast en soutenant nos sponsors:
– Huit sommeil: https://eightsleep.com/lex
– Cash App – Utilisez le code «lexpodcast» et téléchargez:
– Cash App (App Store): https://apple.co/2spruhe
– application en espèces (Google Play): https://bit.ly/2mlvp5w

Si vous souhaitez obtenir plus d’informations sur ce podcast, allez à https://lexfridman.com/ai ou connectez-vous avec @lexfridman sur Gazouillement, Liendin, Facebook, Moyenou Youtube où vous pouvez regarder les versions vidéo de ces conversations. Si vous aimez le podcast, veuillez le noter 5 étoiles sur Podcasts Applesuivez Spotifyou le soutenir sur Patreon.

Voici le contour de l’épisode. Sur certains joueurs de podcast, vous devriez pouvoir cliquer sur l’horodatage pour sauter à ce moment.

CONTOUR:
00:00 – Introduction
03:50 – Géométrie
09:46 – Visualiser un algorithme
13h00 – un bel algorithme
18:06 – Don Knuth and Geeks
22:06 – Les premiers jours des ordinateurs
25:53 – Test de Turing
30:05 – Conscience
33:22 – Algorithmes combinatoires
37:42 – Algorithme d’Edmonds-Karp
40:22 – complexité algorithmique
50:25 – p = np
54:25 – Problèmes NP-complete
1:10:29 – Prouver P = NP
1:12:57 – Problème de mariage stable
1:20:32 – Algorithmes randomisés
1:33:23 – un problème difficile peut-il être facile dans la pratique?
1:43:57 – Problèmes ouverts en informatique théorique
1:46:21 – Une idée étrange de la théorie de la complexité
1:50:49 – Apprentissage automatique
1:56:26 – Bioinformatique
2:00:37 – Mémoire du père de Richard

https://www.youtube.com/watch?v=kllcrlfluzs