UE — Algorithmique fondamentale

Licence — L1+L2 | Informatique | 6 ECTS

Unité d'enseignement « Algorithmique fondamentale » — Informatique (L1, L2). Cette UE permet de construire les bases conceptuelles, méthodologiques et pratiques associées à la thématique.

Informations générales

Compétences visées

À l'issue de cette unité d'enseignement, l'étudiant sera capable de :

Thèmes abordés

T1. Théorie de la complexité

Étude approfondie : Théorie de la complexité.

T1.1. Notion de complexité algorithmique (temps, espace)

Cette section introduit les concepts fondamentaux de la complexité algorithmique, essentiels pour évaluer l'efficacité des algorithmes.

  • Notions clés :
  • complexité O(n) O(n²) O(log n) temps espace efficacité

T1.2. Diviser pour régner (tri fusion, exponentiation rapide)

Présentation de la stratégie algorithmique "diviser pour régner" et ses applications concrètes.

  • Notions clés :
  • diviser pour régner tri fusion merge sort exponentiation rapide récursivité

T3. Algorithmes d'optimisation

Étude approfondie : Algorithmes d'optimisation.

T3.1. Algorithmique avancée

Concepts avancés en algorithmique pour résoudre des problèmes complexes.

  • Notions clés :
  • algorithme boucle liste recherche tri complexité

T3.2. Recherche, tri et filtrage dans une table

Techniques de manipulation et d'analyse de données structurées.

  • Notions clés :
  • recherche tri filtrage sélection projection critère

T3.3. Algorithmes de tri (tri par insertion, tri par sélection)

Comparaison des principales méthodes de tri et analyse de leur efficacité.

  • Notions clés :
  • tri tri par insertion tri par sélection comparaison échange invariant

T3.4. Recherche dichotomique dans un tableau trié

Optimisation de la recherche dans des structures de données ordonnées.

  • Notions clés :
  • dichotomie recherche dichotomique tableau trié diviser pour régner logarithme

T3.5. Programmation dynamique (mémoïsation, sous-problèmes optimaux)

Stratégie de résolution de problèmes par décomposition en sous-problèmes.

  • Notions clés :
  • programmation dynamique mémoïsation sous-problème Fibonacci optimal tableau

T3.6. Recherche textuelle (algorithme naïf, Boyer-Moore)

Techniques de recherche de motifs dans des chaînes de caractères.

  • Notions clés :
  • recherche textuelle motif Boyer-Moore automate chaîne de caractères

T4. Algorithmes de graphes

Étude approfondie : Algorithmes de graphes.

T4.1. Algorithmes gloutons

Stratégies d'optimisation par choix locaux successifs.

  • Notions clés :
  • glouton optimisation choix local rendu de monnaie sac à dos

T4.2. Algorithmes sur les arbres (parcours en profondeur, en largeur)

Techniques de parcours et d'analyse des structures arborescentes.

  • Notions clés :
  • parcours en profondeur parcours en largeur DFS BFS arbre récursivité

T4.3. Algorithmes sur les graphes (parcours, plus court chemin, détection de cycle)

Algorithmes fondamentaux pour l'analyse des réseaux et des structures relationnelles.

  • Notions clés :
  • Dijkstra BFS DFS plus court chemin cycle graphe parcours

Ressources complémentaires