Introduction

1 Présentation du module

Algorithmique et Structure de Données est un module de remise à niveau en 20 heures destiné aux étudiants en 1ière année du cycle ingénieur ESTIA.

1.1 Séquencement des séances

  • Séance 1 et 2: Introduction et Fondamentaux (4h)
  • Séance 3 et 4: Complexité (4h)
  • Séance 5 et 6: Listes (4h)
  • Séance 7 et 8: Dictionnaires (4h)
  • Séance 9 et 10: Défis (4h)

1.2 Acquis d’apprentissage visés

À la fin du module, l’étudiant sera capable de :

  • Comprendre le déroulement des algorithmes
  • Analyser la complexité en temps des algorithmes
  • Concevoir des algorithmes pour répondre à des problèmes
Note

Ces acquis d’apprentissage sont indispensables pour suivre de nombreux modules d’enseignement du cycle ingénieur ESTIA:

  • en Informatique – Développment Web Statique (CI 1A), Programmation Procédurale (CI 1A), Programmation Orientée Objet (CI 2A), Programmation Orientée Objet Évenementielle (CI 2A), Développement Rapide d’Applications (CI 2A) et Systèmes Mobiles Communicants (CI 2A)
  • en Électronique – Systèmes Microprogrammés (CI 2A)
  • en Mécanique – Simulation Avancée en Mécanique (CI 2A)
  • en Robotique – Robotique Collaborative et Vision et Robotique (CI 2A)

2 Généralités

2.1 Qu’est-ce qu’un algorithme ?

Un algorithme est une suite finie d’instructions qui renvoie un résultat en sortie à partir de données en entrée. Les algorithmes sont présents dans de nombreuses activités humaines et permettent de résoudre des problèmes (voir Figure 1).

(a) Recette de cuisine
(b) Partition de musique
(c) Manuel d’assemblage
Figure 1: Exemples d’analogies pour comprendre ce qu’est un algorithme.

2.2 Qu’est-ce qu’une structure de données ?

Une structure de données permet d’organiser et stocker de la donnée entre les instructions. Grâce aux structures de données, les algorithmes peuvent gérer, accéder et modifier les données lorsqu’ils en ont besoin. On retrouvent des formes de structure de données dans de nombreuses activités humaines (voir Figure 2).

(a) Recette de cuisine
(b) Partition de musique
(c) Manuel d’assemblage
Figure 2: Exemples d’analogies pour comprendre ce qu’est une structure de données.

2.3 Quels outils pour apprendre ?

Il est possible d’apprendre l’algorithmique et les structures de données de manière théorique avec un cahier et un crayon. Dans ce module, nous allons apprendre de manière pratique avec le language de programmation Python pour les raisons suivantes:

  • Simplicité et Lisibité : Python utilise une syntaxe simple et lisible qui permet de se concentrer sur les concepts fondamentaux plutôt que sur les détails syntaxiques.
  • Feedback Immédiat : En programmant, vous obtenez des résultats immédiats et pouvez voir si votre algorithme fonctionne comme prévu.
  • Débogage : Les environnements de programmation aident à identifier et à corriger les erreurs dans les algorithmes.
  • Expérimentation : En programmant, vous pouvez facilement tester différents algorithmes et voir lequel est le plus efficace en temps d’éxecution ou en espace mémoire.
Important

Au début de ce module, nous utiliserons une version restreinte de Python pour vous permettre d’implémenter par vous-même des algorithmes (e.g., min, max, abs, reverse, sort, range) et des structures de données (e.g., list, dict) qui sont fournis nativement dans Python. La boucle for et l’opérateur in sont également interdits.

Vers la fin de ce module, nous utiliserons la version complète de Python pour implémenter des algorithmes plus complexes et utiliser des structures de données plus avancées.