Légende de la leçon
Vert : définitions
I. Types d'algorithmes de décision
1) Algorithmes déterministes
- Fonctionnement : ces algorithmes suivent un ensemble précis de règles ou d'étapes pour traiter les données. Ils garantissent le même résultat à chaque exécution avec les mêmes données d'entrée.
- Exemple - algorithme de tri : considérons l'algorithme de tri par sélection. Il parcourt la liste, trouve le minimum, et l'échange avec l'élément en première position. Ce processus est répété pour le reste de la liste, en plaçant à chaque fois le minimum suivant à sa position correcte.
2) Algorithmes non déterministes
- Fonctionnement : ces algorithmes intègrent une forme de choix aléatoire, ce qui signifie que leur exécution peut donner des résultats différents avec les mêmes données d'entrée.
- Exemple - algorithme génétique : inspiré de la biologie, cet algorithme commence avec un ensemble de solutions (appelé « population »), sélectionne les meilleures en fonction d'une fonction de fitness, puis les combine et les modifie (par croisement et mutation) pour créer une nouvelle génération de solutions.
3) Algorithmes d'optimisation
- Fonctionnement : ces algorithmes cherchent à maximiser ou minimiser une fonction objectif. Ils explorent l'espace des solutions possibles pour trouver la solution optimale.
- Exemple - algorithme du simplexe : utilisé pour les problèmes de programmation linéaire, l'algorithme du simplexe navigue sur les sommets du polytope formé par les contraintes du problème pour trouver le point où la fonction objectif est optimisée.
II. Exemples spécifiques d'algorithmes de décision
1) Algorithme de Dijkstra
Fonctionnement : utilisé pour trouver le chemin le plus court dans un graphe. Il commence au nœud initial, explore les voisins, et utilise une structure de données de type file de priorité pour sélectionner le nœud le plus proche non visité. Il met à jour les distances des nœuds voisins et répète le processus jusqu'à atteindre le nœud cible.
2) Algorithme de prise de décision de Markov (MDP)
Fonctionnement : il modélise les décisions dans des situations où les résultats sont partiellement aléatoires et partiellement sous le contrôle d'un agent. Les MDP utilisent des états, des actions, des récompenses et des probabilités de transition pour définir un processus de décision. L'algorithme cherche la stratégie (ou politique) qui maximise la somme des récompenses attendues.
III. Algorithmes de décision en intelligence artificielle
- Classification et régression : utilisent des données d'entraînement pour apprendre comment classer de nouvelles données ou prédire une valeur continue.
- Clustering : regroupe les données en ensembles basés sur leur similarité ou d'autres critères sans utiliser de données d'entraînement.
Je retiens
