Informatique 2 - Structures de données et algorithmes MT - 3PMRSDAL

Objectif(s)

Poursuite de l'apprentissage des outils conceptuels des langages impératifs afin de concevoir des algorithmes permettant de résoudre un problème et du savoir-faire pour l'implanter ces algorithmes à travers le langage de programmation C, particulièrement important pour l'ingénierie telle qu'abordée à Phelma :
L'objectif de ce cours est de fournir les bases d'une part des outils conceptuels des langages impératifs et d'autre part du langage de programmation C, particulièrement important pour l'ingénierie telle qu'abordée à Phelma MT.
Acquérir et mettre en pratique méthodes de la programmation structurée.
Apprendre l'algorithmique.
Acquérir une maitrise du cycle de développement logiciel : spécification, analyse, codage, compilation, tests, gestion de version.
Apprendre le langage C, en particulier dans ses spécificités "proches de la machine".

Apprentissage des principales notions et structures de données à la base des solutions à de nombreux problèmes non numériques. Il aborde la programmation récursive et les principales structures de données dynamiques et types abstraits utilisées aujourd'hui (comme les listes, piles, files, arbres, graphes) et présente quelques implémentations et algorithmes utilisant ces structures de données.

Contenu(s)

Principales notions abordées :
Programmation récursive, notion de complexité
Notion de Type de Données Abstraites
Structures de données chaînées linéaires comme les listes, piles, files
Dictionnaires et tables de hachage ou structures arboresente.
Structures de données arborescentes : arbres binaire

Tp : Ces notions sont mises en oeuvre BE par les étudiants, en langage C, sous Linux, sur des exemples concrets; Quelques exemples de problèmes traités :
Fractale de MandelBrot et Récursivité
Tri par tas
Vérificateur orthographique et Table de Hachage
Calcul vectoriel
...

2 projets sont à réaliser durant le module :

Micro-projet. Exemples : Traitement d'image, mosaïquage, inpainting, stéganographie, calcul vectoriel...

Mini projet. Exemples ; Recherche d'itinéraires dans le métro et le RER parisien par recherche du plus court chemin dans un graphe avec différents algorithmes : Dijkstra, Bellman, A-Star, etc.

Module de premier semestre informatique 1 - programmation - MT