Informatique 2- Structure de données et algorithmes PET-PI - 3PMKSDAL

Objectif(s)

L'enseignement introduit certaines 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 (listes, piles, files, arbres, graphes) et présente quelques implémentations et algorithmes utilisant ces structures de données.

Il renforce les compétences en génie logiciel : spécification, analyse, codage, compilation, tests, gestion de version.

Contenu(s)

Exemples de 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 : listes, piles, files
Dictionnaires et tables de hachage
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
Jeu de carte de la bataille avec pile et file
Vérificateur orthographique et Table de Hachage
Calcul formel de dérivée d'expressions mathématiques et arbre binaire

Mini projet de fin de module. Exemples de sujets : 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.

Cours informatique premier semestre 1A

Contrôle des connaissances

SESSION 1 :

Types d'évaluation : EX - examen écrit
Durée : 1h
Documents autorisés : aucun
Documents interdits : tout document électronique (sur téléphone, ordinateur, ...)
Matériels spécifiques autorisés : aucun
Calculatrice : non
Possible en distanciel : si nécessaire

Types d'évaluation : CC - Cntrôle continu
CC : QCM + rendu des BE + rendu du projet de fin de semestre (Cf. consignes énoncé)

N1 = 40%EX + 60%CC

SESSION DE RATTRAPAGE :

Types d'évaluation : EX - examen écrit
Durée : 1h
Documents autorisés : aucun
Documents interdits : tout document électronique (sur téléphone, ordinateur, ...)
Matériels spécifiques autorisés : aucun
Calculatrice : non
Possible en distanciel : si nécessaire

Types d'évaluation : CC - Contrôle continu
CC : report de la note de session 1

N1 = 60%EX + 40%CC

Informations complémentaires