Algorithmique, Programmation et Structure de Données (LIFAPSD)
Présentation
Prérequis
- Savoir écrire un algorithme simple en langage algorithmique
- manipuler des variables de type booléen, entier, réel, caractère
- manipuler des tableaux et chaînes de caractères
- connaître les structures de contrôle (tests, boucles, ...)
- savoir découper un programme en fonctions et procédures
- connaître les modes de passage des paramètres
- être familier avec l’organisation de la mémoire
- Savoir implémenter tout ça en langage C++
Contenu de l'UE
- Manipulation des principales structures de données utilisées en informatique
- types primitifs: entier, réels, caractères, booléens, pointeurs
- types agrégés: tableaux et structures
- gestion des entrées-sorties: standard et fichier
- structures dynamiques: tableaux, piles, files, listes, arbres, fichiers
- Les classes et objets
- membre, spécificateur d’accès, surcharge d’opérateur
- type de données abstrait et programmation modulaire
- Algorithmique
- algorithmes de tri (sélection, insertion, fusion)
- introduction à la notion de complexité algorithmique
MCC
La note finale LIFAPSD est calculée comme suit, où CC1TD et CC2TD sont les deux contrôles continus de TD, CC1TP et CC2TP sont les deux contrôles continus de TP et ECA est l'épreuve commune anonyme:LIFAPSD = (10 * CC1TD + 10 * CC2TD + 20 * CC1TP + 20 * CC2TP + 40 * ECA) / 100
Les modalités de contrôle des connaissances pour les UE en CCI sont disponibles sur le site de l'Université. Notez les points spécifiques importants suivants. La note de session 2 (en juin) remplace la note de l'ECA (contrôle final de janvier) même si la note de session 2 est inférieure. Une absence, qu'elle soit justifiée ou injustifiée, à un contrôle continu (CC1TD, CC1TP, CC2TD, CC2TP) entraîne la neutralisation de la note du CC concerné. Par contre une absence, qu'elle soit justifiée ou injustifiée, à l'ECA entraîne la note de zéro à cette épreuve.Les contrôles continus auront lieu le lundi 25 septembre (CC1TD), le lundi 6 novembre (CC2TD), le lundi 9 octobre (CC1TP groupes ABCD) et mardi 10 octobre (CC1TP groupes EFGH), et le lundi 27 novembre (CC2TP groupes ABCD) et mardi 28 novembre (CC2TP groupes EFGH).
Emploi du temps et groupes
Automne 2023 - Emplois du temps sur ADE : Emploi du temps LIFAPSD groupes A1 et A2Emploi du temps LIFAPSD groupes B1 et B2
Emploi du temps LIFAPSD groupes C1 et C2
Emploi du temps LIFAPSD groupes D1 et D2
Emploi du temps LIFAPSD groupes E1 et E2
Emploi du temps LIFAPSD groupes F1 et F2
Emploi du temps LIFAPSD groupes G1 et G2
Emploi du temps LIFAPSD groupes H1 et H2
Emploi du temps LIFAPSD tous les groupes
Ressources
Transparents et vidéos de CM
CM1 - Introduction et rappels | transparents | vidéo |
CM2 - Allocation dynamique de mémoire | transparents | vidéo |
CM3 - Classes et objets (1/2) | transparents | vidéo partie 1 |
CM4 - Classes et objets (2/2) | transparents | vidéo partie 2 |
CM5 - Fichier, tri et complexité (1/2) | transparents | vidéo partie 1 - vidéo partie 2 |
CM6 - Fichier, tri et complexité (2/2) | transparents | vidéo partie 3 |
CM7 - TDA et programmation séparée | transparents | vidéo |
CM8 - Tableau Dynamique | transparents | vidéo |
CM9 - Liste | transparents | vidéo |
CM10 - Pile et file | transparents | vidéo |
CM11 - Arbre (1/2) | transparents | vidéo partie 1 |
CM12 - Arbre (2/2) | transparents | vidéo partie 2 |
CM12 (bonus) - Résumé sur les TDA | transparents | vidéo |
Exercices de TD
Polycopié entier des énoncés de TD et TP.TD1 - Vie et mort des variables en mémoire (1/2) | énoncé | corrigé |
TD2 - Vie et mort des variables en mémoire (2/2) | énoncé | corrigé |
TD3 - Classe et objet (1/2) | énoncé | corrigé |
TD4 - Classe et objet (2/2) | énoncé | corrigé |
TD5 - Algorithme, invariant de boucle et complexité (1/2) | énoncé | corrigé |
TD6 - Algorithme, invariant de boucle et complexité (2/2) | énoncé | corrigé |
TD7 - Tri fusion (1/2) | énoncé | corrigé |
TD8 - Tri fusion (2/2) | énoncé | corrigé |
TD9 - Tableau dynamique | énoncé | corrigé |
TD10 - Liste chaînée | énoncé | corrigé |
TD11 - Pile et file | énoncé | corrigé |
TD12 - Arbre binaire | énoncé | corrigé |
Exercices de TP Polycopié entier des énoncés de TD et TP
TP1 - De LIFAPI à LIFAPSD | énoncé | corrigé | |
TP2 - Vie et mort des variables en mémoire | énoncé | corrigé | |
TP3 - Classe et objet | énoncé | corrigé | |
TP4 - Fichier et complexité expérimentale | énoncé | random.txt, reverse.txt, sorted.txt | corrigé |
TP5 - Tableau dynamique | énoncé | ElementTD.h, ElementTD.cpp, TableauDynamique.h | TableauDynamique.cpp |
TP6 - Liste doublement chaînée | énoncé | ElementL.h, ElementL.cpp, Liste.h | Liste.cpp |
TP7 - Pile et file | énoncé | ElementL.h, ElementL.cpp, ElementTD.h, ElementTD.cpp, File.h, Pile.h | File.cpp et Pile.cpp |
TP8 - Arbre binaire de recherche | énoncé | ElementA.h, ElementA.cpp, Arbre.h | Arbre.cpp |
Annexes
- Annexe A - Commandes Linux usuelles
- Annexe B - Tirage de nombres aléatoires
- Annexe C - Mesure de temps d'exécution
Annales d'examens et corrigés
- ECA automne 2023 : énoncé et corrigé
- ECA automne 2022 : énoncé et corrigé
- ECA automne 2021 : énoncé et corrigé
- ECA automne 2020 : énoncé et corrigé
- ECA automne 2019 : énoncé et corrigé
Littérature
Il existe des tonnes de ressources sur Internet et dans les librairies pour apprendre l'algorithmique et la programmation C++. Voici quelques livres disponibles à la BU de science, ainsi que quelques liens utiles.- Algorithmique : cours avec 957 exercices et 158 problèmes, T. Cormen et al., 2010
- Programmez avec le langage C++, M. Nebra et M. Schaller, 2015
- Conception d'algorithmes: principes et 150 exercices corrigés, P. Bosc et al., 2016
- Apprendre le C++, C. Delannoy, 2008
- Algorithmique : applications en C, C++ et Java, J.-M. Léry et F. Jacquenod, 2013
- LIFAPI (CM/TD/TP/exam) : pour ceux qui n'ont pas suivi l'UE l'année dernière
- Tutoriels C++ et cours d'algo (developpez.com)
- Documentation et tutoriel C++ (cplusplus.com en anglais)
- Outil en ligne de visualisation d'exécution de code C++
- IDE C++ (et autres) en ligne