Algorithme et complexité
Ce cours, destiné aux étudiants de mastère de recherche (M1) en Génie Logiciel à l’ISIMM, porte sur l’analyse de l’efficacité des algorithmes en temps et en mémoire. Il introduit les bornes asymptotiques (O, Ω, Θ), l’étude des cas meilleur, moyen et pire, ainsi que l’analyse des algorithmes itératifs et récursifs.
Le cours développe un raisonnement rigoureux, essentiel pour la conception, la comparaison et l’optimisation d’algorithmes dans un contexte de recherche.
Processus Stochastique
Un processus stochastique est une suite de variables aléatoires décrivant l’évolution d’un système dans le temps.
-
Chaînes de Markov : la probabilité du prochain état dépend seulement de l’état actuel. Elles sont définies par une matrice de transition et une distribution initiale.
-
Chaînes de Markov cachées (HMM) : les états réels ne sont pas observables directement. On observe seulement des sorties probabilistes liées aux états cachés.
-
États cachés : système réel non visible.
-
Observations : ce que l’on mesure.
-
Paramètres du modèle : A (transitions), B (probabilités d’émission), π (distribution initiale).
-
Problèmes principaux :
• Évaluation (probabilité d’une séquence observée, algorithme Forward).
• Décodage (retrouver les états cachés les plus probables, algorithme de Viterbi).
• Apprentissage (ajustement des paramètres, algorithme Baum-Welch). -
Applications : reconnaissance vocale, bio-informatique, finance, séries temporelles.
-
-
Files d’attente : modélisation de systèmes avec arrivées de clients et services.
-
Notation de Kendall : A/S/c où A = loi des arrivées (M = exponentielle), S = loi du service, c = nombre de serveurs.
-
Exemple M/M/1 : arrivées de Poisson (taux λ), service exponentiel (taux μ), un seul serveur.
• Condition de stabilité : λ < μ.
• Nombre moyen de clients : L = ρ/(1-ρ) avec ρ = λ/μ.
• Temps d’attente moyen : W = 1/(μ - λ). -
Applications : réseaux, serveurs, télécommunications.
-
Conclusion : les HMM permettent de modéliser des systèmes cachés produisant des observations, tandis que les files d’attente analysent la performance et la congestion de systèmes de service.