Séance de cours
Cette séance de cours introduit des algorithmes randomisés pour le problème min-cut, en se concentrant sur l'algorithme de Karger. L'instructeur explique la probabilité de succès dans la recherche de la coupe minimale, le concept de coupe au bon endroit, et l'analyse des différentes phases de l'algorithme. La séance de cours porte sur le calcul des probabilités de réussite des coupes, l'importance des capacités de bord et l'impact des coupes au mauvais endroit. Différents scénarios et calculs sont présentés pour illustrer l'efficacité et les limites de l'algorithme.