Introduction aux concepts fondamentaux
Ce cours présente les notions clés de l'algorithmique, de la récursivité, de la complexité et des graphes. Chaque section s’appuie sur des définitions précises et des exemples illustratifs pour faciliter la compréhension.
Algorithmes et itérations
Définition informelle d’un algorithme
Une procédure de calcul bien définie transformant une entrée en une sortie. Il prend une ou plusieurs valeurs en entrée et renvoie une ou plusieurs valeurs en sortie.
Itération
En informatique, une itération est la répétition d’un bloc d’instructions.
Conversion récursivité ↔ itération
- Toute fonction récursive peut être remplacée par une itération équivalente. La version itérative peut toutefois être plus complexe à écrire.
- Exemple : la factorielle.
- Itératif → boucle for
- Récursif → appel de fonction
Invariant de multiplication
Après i tours, y = x^i. Cet invariant montre que chaque itération multiplie y par x, accumulant la puissance.
Complexité temporelle de la multiplication
La complexité en temps de l’algorithme de multiplication est O(n) : il y a n itérations, chacune effectuant un nombre constant d’opérations.
Recherche dichotomique
- Complexité : O(log n).
- Fonctionne uniquement sur un tableau préalablement trié en ordre croissant (fausse affirmation : « fonctionne sur un tableau non trié »).
Fonctions particulières
Fonction d’Ackermann
Cas de base : si m = 0 alors le résultat est n + 1.
Méthode diviser‑pour‑régner
Les trois étapes sont : Diviser, Régner, Combiner. « Diviser » découpe le problème, « Régner » résout les sous‑problèmes, « Combiner » assemble les solutions.
Graphes
Définition formelle
Un graphe G = (X, A) avec X l’ensemble des sommets et A l’ensemble des arcs, sous‑ensemble du produit cartésien X×X.
Types de graphes
- Orienté → arcs directionnels.
- Non orienté → arêtes bidirectionnelles.
Degré d’un sommet
Nombre d’arcs incident à ce sommet. Pour les graphes orientés, il compte les arcs entrants et sortants. Dans un graphe non orienté, le degré correspond au nombre de voisins (affirmation vraie).
Graphes complets et bipartis
- Kn : chaque paire de sommets est connectée.
- Ka,b : chaque sommet de la partie V1 est connecté à tous les sommets de la partie V2.
Matrices d’adjacence
Pour un graphe orienté, Mij = 1 si (xi, xj) ∈ A, sinon 0. Chaque ligne i et colonne j indique la présence d’un arc de xi vers xj.
Dans un graphe non orienté, la matrice d’adjacence est toujours symétrique, car chaque arête [x,y] implique à la fois (x,y) et (y,x).
Usage mémoire
Comparaison entre représentation matricielle et liste d’adjacence :
| Structure | Complexité mémoire |
|---|---|
| Matrice | θ(n²) |
| Liste | θ(n + m) |
Chemins et circuits
Un chemin dans un graphe orienté est une suite d’arcs où l’extrémité de chaque arc est l’origine du suivant. La longueur du chemin est le nombre d’arcs.
Un circuit n’est pas un chemin dont l’origine diffère de l’extrémité ; au contraire, un circuit a la même origine et la même extrémité (affirmation fausse).
Théorie de la calculabilité
Réduction many‑one
Une fonction totale récursive f telle que x ∈ A ⇔ f(x) ∈ B. Elle transforme chaque instance de A en une instance de B de façon computable.
Problème de l’arrêt
Le problème de l’arrêt est indécidable (affirmation fausse). Aucun algorithme ne peut décider pour tous les programmes s’ils s’arrêtent.
Fonctions h(p,x) et h(p,x,t)
- h(p,x) n’est pas calculable.
- h(p,x,t) est calculable grâce au paramètre temps t, qui permet de vérifier la terminaison dans un délai fini.
Théorème de Rice
Toute propriété non triviale sur le comportement d’une fonction calculable est indécidable. Si deux programmes calculent la même fonction, la propriété leur donne la même valeur.
Ensembles semi‑décidables et décidables
- Tout ensemble semi‑décidable n’est pas forcément décidable (affirmation fausse). Il peut être récursivement énumérable sans être décidable.
- Tout ensemble fini est toujours décidable : on peut tester l’appartenance en comparant avec les éléments listés.
Conclusion
Ce cours couvre les bases essentielles de l’algorithmique, de la complexité, des structures de graphes et des notions de calculabilité. La maîtrise de ces concepts permet d’aborder des problèmes plus avancés en informatique théorique et appliquée.
