|
|
|
|
|
|
Ce cours a pour but de donner les
éléments algorithmiques et théoriques de la bio-
informatique de la séquence. Le contenu est totalement
tourné vers la comparaison de séquences, tout en passant
en revue les algorithmes de recherche de motifs dans un
texte. |
|
-
Recherche exacte de motifs
-
Recherche d'un seul motif (Algorithme naïf, Algorithme de
Rabin-Karp, Algorithme à base d'automates, Algorithme de
Knuth-Morris-Pratt)
-
Recherche de plusieurs motifs (arbre des motifs,
Généralisation de KMP)
-
Applications
- Index de
Texte
-
structure d'index de texte
- arbre
des suffixes
-
Construction de l'arbre des suffixes
-
Applications
-
Programmation Dynamique
-
éléments théoriques
- Le
problème du sac à dos
- La plus
longue sous-séquence commune
-
généralisations :
-
alignement de séquences avec matrice de substitution
-
alignement multiple (n séquences), analyse de la
complexité
|
|
|
|
|
|
|
|
Ce cours présente les représentations
mathématiques et logiques de base pour la modélisation
des systèmes dynamiques et discrets. |
|
-
Systèmes dynamiques et discrets : présentation
(réactivité, ressources), modèles de
Kripke.
- Logiques
temporelles : CTL, LTL, CTL*
-
Applications : modélisation, vérification de
propriétés temporelles, utilisation de
model-checker.
-
Réseaux de Pétri : modèles,
représentation matricielle, graphe de marquage,
traces.
-
Vérification : séquence de franchissement,
bornitude, vivacité
|
|
|
|
|
|
|
|
1. Semestre 5
