Informatique et Sciences du Numérique au lycée : un pas plus loin/ALGORITHMES

Un livre de Wikilivres.

(Introduction à écrire par les wikipédiennes (iens) construisant les sections. Chapitre à construire par les wikipédiennes (iens) concernées (és) par ce domaine. Le plan indiqué est extrait de la table des matières de l'ouvrage du secondaire et doit être modifié pour donner une vision plus générale de l'algorithmique. Quelques pages wikipedia sont accrochées dans ce plan comme premiers éléments de contenus. Il est nécessaire qu'elles soient revues (introduites, allégées ou complétées, reformulées) par des spécialistes d'algorithmique pour bien remplir les objectifs de l'ouvrage.


  • AJOUTER DEUX NOMBRES EXPRIMÉS EN BASE DEUX
  1. L’addition
  2. L’addition pour les nombres exprimés en base deux
  3. Les invariants de boucle
  • DESSINER
  1. Dessiner dans une fenêtre
  • LA DICHOTOMIE
  1. La recherche en table
  2. La conversion analogique-numérique
  3. Trouver un zéro d’une fonction
  • TRIER

voir la page qui parle des Algorithmes de tri.

  1. Le tri par sélection
  2. Le tri par fusion
  3. L’efficacité des algorithmes
  • PARCOURIR UN GRAPHE

Voir la page qui parle des graphes et de leurs algorithmes.

Voir aussi l'algorithme de Dijkstra qui calcule le plus court chemin entre deux sommets d'un graphe et voir également l'algorithme de Floyd-Warshall et l'algorithme de Bellman-Ford.

L'algorithme de Tarjan calcule les composantes connexes d'un graphe.

Les algorithmes tels que l'algorithme de Kruskal, ou l'algorithme de Prim transforment un graphe connexe, en un "arbre couvrant" du graphe c'est à dire un arbre qui contient tous les sommets du graphe et quelques arêtes.

Voir la page qui traite des arbres binaires et de leurs algorithmes.

  1. La liste des chemins à prolonger
  2. Éviter de tourner en rond
  3. La recherche en profondeur et la recherche en largeur Le parcours d’un graphe
  4. États et transitions