A. SIGAYRET :
ALGORITHMIQUE
 

Présentation :
  Il existe diverses manières d'aborder l'algorithmique. L'approche choisie ici étudie les algorithmes indépendamment de leur transcription en langage de programmation et préalablement à leur utilisation sur différents exemplaires de données. Cette approche se concentre ainsi sur les difficultés essentielles de la résolution des problèmes algorithmique. Quand ces difficultés se révèlent importantes, elle permet, en différant les efforts d'implémentation, d'éviter de se perdre dans des solutions inefficaces ou des détails chronophages. Ces cours et exercices, indépendants de toute unité d'enseignement, synthétisent et résument différents travaux et exposés ; on voudra bien excuser les lacunes et simplifications imposées par la loi du genre. Sous la rubrique Algorithmes de référence sont présentées des solutions de problèmes algorithmiques essentiels (sans souci d'exhaustivité, et avec surement quelques coquilles), ce qui donne des modèles d'écriture d'algorithmes.
Cours
  1. Algorithmique et algorithme.
  2. Données et traitements.
  3. Preuves d'un algorithme, complexité.
  4. Problème et faisabilité.
  5. Paradigmes et méthodes de résolution.
Exercices
  1. Série 1.      
  2. Série 2.
  3. Serie 3.
  4. Série 4.
  5. Série 5.
  6. Série 6.
  7. Série 7.
  8. Série 8.
Algorithmes de référence
  1. Parcours de graphe. (DEGRE, LARGEUR, PROFONDEUR, EXPLORER)
  2. Graphe sans circuit. (S-SEQUENCE, ARCRETOUR)
  3. Fermetures de graphe. (Roy-Warshall)
  4. Connexité de graphe. (CC, CFC-AscDesc, CFC-Circuit, CFC-magique)
  5. Graphe valué sur les arêtes (DIJKSTRA, PRIM, KRUSKAL, SOLLIN, Ford-Fulkerson)
  6. Couplage maximal de graphe (AMELIORER, AMELIORERVITE)
  7. Cycle eulérien de multigraphe (EULERIEN)
  8. Gestion de partition (FUSIONNER, SEPARER)
  9. Problèmes d'arbres (symPAC, CODER, EFFEUILLER, EPLUCHER)
  10. Problèmes NP-complets (...)
  2018-06-28   –   A. Sigayret