Introduction

1 Présentation du module

Algorithmique et Structure de Données est un module de renforcement des compétences en 24 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: Complexité (2h)
  • Séance 4 et 5: Tableaux (4h)
  • Séance 6 et 7: Listes (4h)
  • Séance 8: Examen blanc sur Moodle avec Safe Exam Browser (2h)
  • Séance 9 et 10: Dictionnaires (4h)
  • Séance 11: Recherche et Tri (2h)
  • Séance 12: Examen session 1 sur Moodle avec Safe Exam Browser (2h)
  • Rattrapage: Examen session 2 sur Moodle avec Safe Exam Browser (2h)

1.2 Obtention des crédits

  1. Si note session 1 \(\ge\) 10 alors crédits obtenus.
  2. Sinon, si note session 2 \(\ge\) 10 alors crédits obtenus (grade E au maximum).
  3. Sinon crédits non obtenus.

1.3 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

Attention, le langage de programmation Python que vous allez utiliser dans ce module est restreint 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.