Programmé en UV2 MAJ INF
Présentation :
Après l'introduction à algorithmique faite par le module "Initiation à l'informatique et à la programmation (S1)", cet module présente une sélection riche de sujets d’algorithmique: structures de données avancées, le traitement de chaînes, la Géométrie Algorithmique et l'algorithme de classification K-means. Un professionnel ferra une une présentation de la place de l'algorithmique dans l'entreprise avec un étude de cas.
Objectifs pédagogiques :
- Être capable d'identifier la structure de donnée adéquate pour un problème.
- Être capable d'apprécier les avantages d'une optimisation algorithmique et la mettre en œuvre.
- Être capable d'analyser et de comparer les structures complexes de données.
- Être capable d'identifier l'algorithme de recherche de chaîne de caractère dans un texte.
- Être capable de mettre en œuvre une méthode de classification non supervisée des données.
Pré-requis :
TC101A : Algorithmique
Liens :
INF UV1
Volume horaire :
21h
Contenu détaillé :
Un TP d'initiation à la programmation avec Python sera placé au début des cours.
1) Structures de données avancées
1.1) Listes, piles, files
1.2) Tables de hachage
1.3) Arbres (binaires, rouge-noir, etc.)
1.4) Graphes
2) Algorithmes de traitement de chaînes
2.1) Recherche de chaînes de caractères
2.2) Algorithme naïf
2.3) Algorithme de Karp-Rabin, fonction de hachage
2.4) Automate
2.5) Algorithme de Morris & Pratt
2.6) Algorithme de Boyer-Moore
2.7) Autres type de traitement de chaînes : cryptage, compression
3) Algorithmes génétiques
4) L'algorithmique en entreprise
Travaux personnels encadrés :
Étude de l'algorithme K-means.
Année 2016/2017
Dernière mise à jour le 08-FEB-16
Validation par le responsable de programme le
|