Algorithmique et programmation avancée (LIFAP3)


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

Organisation 2020-2021

Pour rappel, la distanciation physique et le port du masque sont obligatoires dans tous les bâtiments de l'université, cela inclut bien sûr toutes les salles de cours.

CM. Pas de présentiel (amphi) pour les CM. Vous consultez à distance les vidéos des CM (voir liens ci-dessous) soit pendant les créneaux de CM (mardi début d'après-midi) soit pendant un créneau libre (lundi matin ou mardi après-midi). Pendant les créneaux de CM (mardi début d'après-midi), le responsable d'UE assure une permanence pour répondre à vos questions sur le salon de discussion dédié sur Discord (cf. mail du responsable d'UE du 04/09). Seule la présentation de l'UE le lundi 7 septembre à 8h sera en visio-conférence sur WebEx (cf. mail du responsable d'UE du 04/09).

TD. Chaque étudiant suivra un TD en présentiel 1 semaine sur 2 dans le créneau et la salle indiqués sur l'emploi du temps. L'autre semaine il le suivra à distance sur WebEx (cf. mail du responsable d'UE du 04/09) sous un format cours-TD les lundi matin de 8h à 9h30. Les demi-groupes qui commencent en présentiel la semaine du 14 septembre sont les demi-groupes 1 (cf. case Grp sur Tomuss).

TP. Chaque étudiant suivra un TP en présentiel 1 semaine sur 2 dans le créneau et la salle indiqués sur l'emploi du temps. L'autre semaine il travaillera à distance et pourra échanger avec les enseignants et les autres étudiants sur un forum de discussion (cf. mail du responsable d'UE du 04/09). Les étudiants travaillant à distance sont encouragés à travailler avec un environnement de développement en ligne afin de pouvoir partager et débugger facilement le code avec les enseignants (par exemple avec repl.it, C++ shell, ou CodeBunk). Les demi-groupes qui commencent en présentiel la semaine du 28 septembre sont les demi-groupes 1 (cf. case Grp sur Tomuss).

MCC. La note finale LIFAP3 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:
LIFAP3 = (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 importants suivants. La note de session 2 (en juin) remplace la note ECA (contrôle final de janvier) même si la note de session 2 est inférieure. Également, une absence, quelle soit justifiée ou injustifiée, à l'ECA entraîne un DEF à l'UE en session 1 (mais l'étudiant peut venir en session 2). Une absence injustifiée attribue la note de zéro au contrôle. Au dessus de 40% d'absences justifiées aux contrôles continus, toutes les absences justifiées sont converties en zéro. Les justificatifs sont à déposer (dans les 7 jours pour les séances normales, dans les 48h pour les CC et l'ECA) à la scolarité de la licence bâtiment Quai 43.
Les contrôles continus auront lieu le lundi 28 septembre (CC1TD demi-groupes 1) et le lundi 5 octobre (CC1TD demi-groupes 2), le lundi 12 octobre (CC1TP groupes ABCD demi-groupes 1) et le mardi 13 octobre (CC1TP groupes EFGH demi-groupes 1), le lundi 19 octobre (CC1TP groupes ABCD demi-groupes 2) et le mardi 20 octobre (CC1TP groupes EFGH demi-groupes 2), le lundi 2 novembre (CC2TD demi-groupes 1) et le lundi 9 novembre (CC2TD demi-groupes 2), le lundi 30 novembre (CC2TP groupes ABCD demi-groupes 1) et le mardi 1 décembre (CC2TP groupes EFGH demi-groupes 1), le lundi 7 décembre (CC2TP groupes ABCD demi-groupes 2) et le mardi 8 décembre (CC2TP groupes EFGH demi-groupes 2).

Divers.
Vous n'avez pas besoin d'imprimer le polycopié des énoncés de TD et TP, une version papier vous sera distribuée lors de votre premier TD.
Vous devez signaler votre présence à chaque séance de TD et de TP. Il n'y a pas de relevé de présence pour les CM. L'appel sera fait avec les étudiants en présentiel. Pour le distanciel vous devez poster un message court (comme "bonjour") au début de chaque séance à distance sur le chat WebEx pour les TD et sur le salon Discord pour les TP. Que ça soit sur WebEx ou sur Discord vous devez donc utiliser votre vrai nom et non pas un pseudonyme. Le non respect de cette règle entraînera l'impossibilité de communiquer à distance.

Emploi du temps et groupes

Automne 2020

Emplois du temps sur ADE :
Emploi du temps LIFAP3 groupes A1 et A2
Emploi du temps LIFAP3 groupes B1 et B2
Emploi du temps LIFAP3 groupes C1 et C2
Emploi du temps LIFAP3 groupes D1 et D2
Emploi du temps LIFAP3 groupes E1 et E2
Emploi du temps LIFAP3 groupes F1 et F2
Emploi du temps LIFAP3 groupes G1 et G2
Emploi du temps LIFAP3 groupes H1 et H2

Emploi du temps LIFAP3 tous les groupes

Résumé des emplois du temps (les salles en présentiel sont sur ADE) :

JOUR DATE HEURE CM TD TP CC PRES. DIST.
LUNDI 07/09 8h-11h15 CM1-CM2 ABCDEFGH 1-2
MARDI 08/09 14h-15h30 CM3 ABCDEFGH 1-2
LUNDI 14/09 8h-9h30 TD1 ABCD 1 ABCDEFGH 2
9h45-11h15 TD1 EFGH 1
MARDI 15/09 14h-15h30 CM4 ABCDEFGH 1-2
LUNDI 21/09 8h-9h30 TD2 ABCD 2 ABCDEFGH 1
9h45-11h15 TD2 EFGH 2
MARDI 22/09 14h-15h30 CM5 ABCDEFGH 1-2
LUNDI 28/09 8h-9h30 TD3 CC1TD ABCD 1 ABCDEFGH 2
9h45-11h15 TD3 CC1TD EFGH 1
9h45-13h00 TP1 ABCD 1 ABCD 2
MARDI 29/09 14h-15h30 CM6 ABCDEFGH 1-2
15h45-19h00 TP1 EFGH 1 EFGH 2
LUNDI 05/10 8h-9h30 TD4 CC1TD ABCD 2 ABCDEFGH 1
9h45-11h15 TD4 CC1TD EFGH 2
9h45-13h00 TP2 ABCD 2 ABCD 1
MARDI 06/10 14h-15h30 CM7 ABCDEFGH 1-2
15h45-19h00 TP2 EFGH 2 EFGH 1
LUNDI 12/10 8h-9h30 TD5 ABCD 1 ABCDEFGH 2
9h45-11h15 TD5 EFGH 1
9h45-13h00 TP3 CC1TP ABCD 1 ABCD 2
MARDI 13/10 14h-15h30 CM8 ABCDEFGH 1-2
15h45-19h00 TP3 CC1TP EFGH 1 EFGH 2
LUNDI 19/10 8h-9h30 TD6 ABCD 2 ABCDEFGH 1
9h45-11h15 TD6 EFGH 2
9h45-13h00 TP4 CC1TP ABCD 2 ABCD 1
MARDI 20/10 14h-15h30 CM9 ABCDEFGH 1-2
15h45-19h00 TP4 CC1TP EFGH 2 EFGH 1
LUNDI 26/10
MARDI 27/10
LUNDI 02/11 8h-9h30 TD7 CC2TD ABCD 1 ABCDEFGH 2
9h45-11h15 TD7 CC2TD EFGH 1
MARDI 03/11 14h-15h30 CM10 ABCDEFGH 1-2
LUNDI 09/11 8h-9h30 TD8 CC2TD ABCD 2 ABCDEFGH 1
9h45-11h15 TD8 CC2TD EFGH 2
MARDI 10/11 14h-15h30 CM11 ABCDEFGH 1-2
LUNDI 16/11 8h-9h30 TD9 ABCD 1 ABCDEFGH 2
9h45-11h15 TD9 EFGH 1
9h45-13h00 TP5 ABCD 1 ABCD 2
MARDI 17/11 14h-15h30 CM12 ABCDEFGH 1-2
15h45-19h00 TP5 EFGH 1 EFGH 2
LUNDI 23/11 8h-9h30 TD10 ABCD 2 ABCDEFGH 1
9h45-11h15 TD10 EFGH 2
9h45-13h00 TP6 ABCD 2 ABCD 1
MARDI 24/11 15h45-19h00 TP6 EFGH 2 EFGH 1
LUNDI 30/11 8h-9h30 TD11 ABCD 1 ABCDEFGH 2
9h45-11h15 TD11 EFGH 1
9h45-13h00 TP7 CC2TP ABCD 1 ABCD 2
MARDI 01/12 15h45-19h00 TP7 CC2TP EFGH 1 EFGH 2
LUNDI 07/12 8h-9h30 TD12 ABCD 2 ABCDEFGH 1
9h45-11h15 TD12 EFGH 2
9h45-13h00 TP8 CC2TP ABCD 2 ABCD 1
MARDI 08/12 15h45-19h00 TP8 CC2TP EFGH 2 EFGH 1

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 partie 1 vidéo partie 1
CM4 - Classes et objets (2/2) transparents partie 2 vidéo partie 2
CM5 - Fichier, tri et complexité (1/2) transparents partie 1 - transparents partie 2 vidéo partie 1 - vidéo partie 2
CM6 - Fichier, tri et complexité (2/2) transparents partie 3 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 parties 1 et 2 vidéo parties 1 et 2
CM12 - Arbre (2/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é vidéo
TD2 - Vie et mort des variables en mémoire (2/2) énoncé corrigé vidéo
TD3 - Classe et objet (1/2) énoncé
TD4 - Classe et objet (2/2) énoncé
TD5 - Algorithme, invariant de boucle et complexité (1/2) énoncé
TD6 - Algorithme, invariant de boucle et complexité (2/2) énoncé
TD7 - Tri fusion (1/2) énoncé
TD8 - Tri fusion (2/2) énoncé
TD9 - Tableau dynamique énoncé
TD10 - Liste chaînée énoncé
TD11 - Pile et file énoncé
TD12 - Arbre binaire énoncé

Exercices de TP

Polycopié entier des énoncés de TD et TP

TP1 - De LIFAP1 à LIFAP3 énoncé
TP2 - Vie et mort des variables en mémoire énoncé
TP3 - Classe et objet énoncé
TP4 - Fichier, complexité et tri fusion énoncé random.txt, reverse.txt, sorted.txt
TP5 - Tableau dynamique énoncé ElementTD.h, ElementTD.cpp, TableauDynamique.h
TP6 - Liste doublement chaînée énoncé ElementL.h, ElementL.cpp, Liste.h
TP7 - Pile et file énoncé ElementL.h, ElementL.cpp, ElementTD.h, ElementTD.cpp, File.h, Pile.h
TP8 - Arbre binaire de recherche énoncé ElementA.h, ElementA.cpp, Arbre.h

Annales d'examens et corrigés


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.