Accueil

• Description

  AlgoWeb a pour vocation de proposer une description des algorithmes les plus communs, et d'en proposer le pseudo-code.

• Qu'est-ce qu'un algorithme ?

  • Definition

    Un algorithme est une suite d'instruction clair et sans confusion. Son but est généralement de résoudre un problème généralisé. Il doit renvoyer le bon résultat peu importe les paramètres donnés en entrée, tant qu'ils rentrent dans les critères établis lors de la construction de l'algorithme.

  • Complexité

    Les algorithmes se décomposent généralement en deux parties.
    La première est la structure de stockage des données.
    La seconde est la méthode de parcours de ces données.

    De chacune de ces deux parties découle la complexité en temps et la complexité en mémoire. Il s'agit de mesurer l'impact de l'entrée sur la mémoire utilisé, ou le temps d'execution. On note la complexité d'un algorithme en fonction des paramètres d'entrée, standardisé "N". Les appelations les plus courantes sont répértoriés dans le tableau ci-dessous.

    Notation	Type de complexité
    O(1)	complexité constante (indépendante de la taille de la donnée)
    O(log(n))	complexité logarithmique
    O(n)	complexité linéaire
    O(n*log(n))	complexité quasi-linéaire
    O(n2)	complexité quadratique
    O(n3)	complexité cubique
    O(np)	complexité polynomiale
    O(nlog(n))	complexité quasi-polynomiale
    O(2n)	complexité exponentielle
    O(n!)	complexité factorielle

  • Exemple

    Un exemple courant d'algorithmes sont ceux de parcours de graphes. Voici par exemple l'ordrde de parcours des noeuds avec un DFS ou un BFS.

• Sommaire

  • Structures de données brutes

    Les structures de données brutes sont des moyens particulier de stocker des données, sur lequel certains algorithmes peuvent être effectués. La plupart sont implémentées dans la bibliothèque standard des langages. Cependant, il peut arriver que la structure n'existe pas dans un langage particulier. Dans ce cas, l'utilisateur pourra la coder lui-même. Le site donnera le code permettant d'implémenter certaines structures.

    • Constantes

      Page dédiée : Constantes

      Une constante est une variable qui ne peut changer de valeur.

  • Structures de données travaillées

    Les structures de données travaillées sont des structures de données sur lequel un travail a déjà été effectué. Elle peut parfois être fournie en entrée de l'algorithmes, mais la plupart du temps, les entrées fournies sont données sous formes brutes. Dans ce cas, il sera nécessaires à l'utilisateur d'effectuer les calculs nécessaires pour préparer l'utilisation des données. En effet, ces structures sont souvent un prérequis à l'utilisation de certains algorithmes.

    Dans beaucoup de cas, des algorithmes existent pour structurer des données brutes. Un exemple simple est la liste triée, on peut la génerer à partir d'une liste non-triée, en utilisant un algorithme de tri.

    • listes cumulées croissantes

      Page dédiée : Listes cumulées croissantes Alias : Listes cumulatives;Listes cumulées

      Les listes cumulatives permettent d'obtenir avec une complexité constante en temps la somme d'éléments contenu entre deux bornes d'une liste.

      Les listes cumulatives sont basées sur sur une liste, trié ou non. L'ordre à une importance, la somme se faisant d'un élément à un autre, ajoutant tout ceux entre eux.