Chapitre 1 : Rappel

 

Chapitre 1 : Rappel

Introduction à l'algorithmique

1. Définition de l'algorithme

Un algorithme est une séquence finie et ordonnée d'instructions précises permettant de résoudre un problème ou d'accomplir une tâche spécifique. Les algorithmes sont la base des programmes informatiques. Ils permettent de décomposer des tâches complexes en étapes simples et compréhensibles.

2. Historique et importance de l'algorithmique

L'algorithmique a ses racines dans les travaux de mathématiciens anciens, tels qu'Al-Khwârizmî au IXe siècle, dont le nom a donné le terme "algorithme". L'importance de l'algorithmique réside dans sa capacité à optimiser les performances des programmes et à résoudre des problèmes efficacement. L'évolution des ordinateurs et des langages de programmation a été largement influencée par le développement de nouvelles techniques algorithmiques.

Concepts de base

1. Variables

Une variable est un espace de stockage en mémoire qui a un nom et peut contenir une valeur. Les variables permettent de manipuler des données et de les utiliser dans les algorithmes.

2. Types de données

Les types de données définissent la nature des valeurs que peuvent prendre les variables. Les types de données courants sont :

  • Entiers (int) : nombres sans décimales.
  • Réels (float) : nombres avec décimales.
  • Booléens (bool) : valeurs de vérité (vrai ou faux).
  • Caractères (char) : symboles individuels.

3. Structures de contrôle

Les structures de contrôle permettent de modifier le flux d'exécution d'un algorithme :

  • Conditionnelles (if, else) : permettent de prendre des décisions en fonction de conditions.
  • Boucles (for, while) : permettent de répéter des blocs d'instructions jusqu'à ce qu'une condition soit remplie.

Structures de données fondamentales

1. Listes

Une liste est une collection ordonnée d'éléments, qui peut contenir des types de données variés. Les listes permettent de stocker et de manipuler des ensembles de données.

2. Tableaux

Un tableau est une structure de données qui stocke un ensemble fixe d'éléments du même type. Les éléments sont accessibles par des indices.

3. Piles

Une pile est une structure de données qui suit le principe LIFO (Last In, First Out), où le dernier élément ajouté est le premier à être retiré. Les opérations principales sont empiler (push) et dépiler (pop).

4. Files

Une file est une structure de données qui suit le principe FIFO (First In, First Out), où le premier élément ajouté est le premier à être retiré. Les opérations principales sont enfiler (enqueue) et défiler (dequeue).

Opérations de base sur les structures de données

1. Liste

  • Insertion : ajouter un élément à une position spécifique.
  • Suppression : retirer un élément à une position spécifique.
  • Accès : accéder à un élément à une position spécifique.

2. Tableau

  • Accès : accéder à un élément via son indice.
  • Modification : changer la valeur d'un élément via son indice.

3. Pile

  • Empiler : ajouter un élément au sommet de la pile.
  • Dépiler : retirer l'élément du sommet de la pile.

4. File

  • Enfiler : ajouter un élément à la fin de la file.
  • Défiler : retirer l'élément du début de la file.

Algorithmes de base

1. Recherche linéaire

La recherche linéaire consiste à parcourir chaque élément d'une liste ou d'un tableau séquentiellement jusqu'à trouver l'élément recherché ou atteindre la fin de la structure.

2. Recherche binaire

La recherche binaire est une méthode efficace pour rechercher un élément dans un tableau trié en divisant récursivement l'espace de recherche en deux moitiés.

3. Tri par sélection

Le tri par sélection consiste à trouver le plus petit élément dans une liste non triée et à le placer à la première position. Ce processus est répété pour les positions restantes.

4. Tri par insertion

Le tri par insertion construit la liste triée un élément à la fois en insérant chaque nouvel élément dans sa position appropriée parmi les éléments déjà triés.