COURS INFO
Automates
algo berry-sethy (aka construction de Glushkov): c’est algo pr transformer expression reg en automate, en renommant etc :
PDF puis construction avec q_0
voir https://5demi.fr/exercices/info/
Algos jeux
Stratégie gagnante : strat dans laquelle on est sûr de gagner
position \(s_0\) gagnante (très informellement) : « MAT EN N »
Attracteur : c’est tous les moyens qui amènent à la victoire
en gros si on est dans l’attracteur on est dans une position gagnante
Classes de complexité et décidabilité
réduction de Karp : c qd on r
Algorithmes probabilistes
Las Vegas (La Vérité) : renvoie tjrs ce qui est attendu mais le temps d’execution varie
Monte Carlo (Menteur Chronique) : renvoie le bon résultat avec une certaine proba