Algorithmique avancée GIN3103 S1
Enseignant:
Email:
Durée totale du cours: 45 H
Semestre : 1
Nombre de crédits : 3
| Modules
spécialisés |
Modules de
base |
Sciences et techniques de
l’ingénierie |
Préparation à la carrière professionnelle |
| X |
| Nombre d’heures | Activités hors classe | |||
| 45 | 38 | |||
| cours | TD | TP | ||
| 30 | 15 | |||
Sommaire:
L’algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d’algorithmes, c’est à dire de processus systématiques de résolution, par le calcul, d’un problème permettant de décrire les étapes vers le résultat. En d’autres termes, un algorithme est une suite finie et non-ambiguë d’opérations permettant de donner la réponse à un problème.
| Code | GIN3103 |
Algorithmique avancée
|
Volume Horaire : 3h Cours intégrés (par semaine)
Objectifs d’apprentissage et compétences visées
A l’issue de cette unité d’enseignement, l’étudiant sera capable de :
- Maitriser les concepts algorithmiques de base : constituants d’un programme, types simples et structurés, structures de contrôle, sous-programmes
- Concevoir et réaliser des algorithmes et des structures de données récursifs ou non ;
- Choisir un algorithme de tri et expliquer son fonctionnement ;
- Concevoir un type de données abstrait à partir de spécifications données en langage naturel ;
- Choisir et justifier le choix d’un algorithme ou d’une structure de données ;
- Concevoir une structure linéaire particulière de manière statique ou dynamique ;
- Implémenter les primitives sur les listes, les piles et les files chaînées
- Appliquer les parcours d’arbre sur des exemples concrets : arbres binaires de
Eléments de contenu
- Partie 1 (3 séances)
- 1 séance (3h) : Introduction + types de données (types intégrés + énuméré + tableaux + enregistrement + exemples) et structures de contrôle (choix + boucles + exemples)
- 2 séances (6h) : TD
- Partie 2 (5 séances)
- 1 séance (3h) : sous-programmes + décomposition + variable locale/globale + paramètre formel/réel + passage de paramètres + exemple(s)
- 1 séance (3h) : récursivité
- 1 séance (3h) : recherche et tri (insertion, sélection, à bulles, rapide)
- 2 séances (6h) : TD sur la partie 2 (anciens DS et Examens)
- Partie 3 : (5 séances)
- 3 séances (9h) : pointeurs + types abstraits de données (liste + pile + file + exemples)
- 1 séance (3h) : arbre binaire + exemples
- 1 séance (3h) : TD
Méthodes d’enseignement et d’apprentissage
– Enseignement frontal (magistral) avec des exemples à résoudre en commun.
– Exercices d’application & Travaux dirigés avec discussion.
Connaissances et compétences pré-requises
L’étudiant-e doit connaître et savoir utiliser les notions suivantes : constituants d’un programme, types simples et structurés, structures de contrôle, sous-programmes.
Références bibliographiques
- Un polycopié (Notes du cours) de l’enseignant sera
- Les recommandations bibliographiques suivantes doivent être considérées :
- Thomas Cormen, « Algorithmes : Notions de base », Éditeur Dunod, 2013, ISBN 2100702904, 9782100702909.
Modalité d’évaluation
- 40% Contrôle continu (Tests + Devoir surveillé, Assiduité)
- 60% Examen semestriel
Résultats d’apprentissage :
- Maîtriser les bases de l’algorithmique,
- Connaître les principales structures de données et quelques algorithmes
- Être capable d’organiser un traitement complexe en le découpant en procédures et
- Pouvoir implémenter des algorithmes et mettre au point les programmes écrits dans une démarche de lisibilité et de réutilisabilité.