Université Lyon 1
Arqus
Accueil  >>  Algorithmique, programmation et complexité
  • Unité d'enseignement : Algorithmique, programmation et complexité
Nombre de crédits de l'UE : 6
Code APOGEE : INF3002L
    Responsabilité de l'UE :
CHAINE RAPHAELLE
 raphaelle.chaineuniv-lyon1.fr
04.72.43.26.62
NIVOLIERS VINCENT
 vincent.nivoliersuniv-lyon1.fr
    Contact scolarité :
CHAINE RAPHAELLE
 raphaelle.chaineuniv-lyon1.fr
04.72.43.26.62
    Type d'enseignement
Nb heures *
Cours Magistraux (CM)
15 h
Travaux Dirigés (TD)
15 h
Travaux Pratiques (TP)
30 h

* Ces horaires sont donnés à titre indicatif.

    Pré-requis :
Cette UE capitalise sur les matières proposées les années précédentes. En particulier elle repose principalement sur les UE :
  • Algorithmique et programmation impérative, initiation (LIFAPI);
  • Algorithmique et programmation et structures de données (LIFAPSD);
  • Conception et développement d'applications (LIFAPCD);
et dans une moindre mesure, pour la maîtrise de la récursion et l'approche fonctionnelle :
  • Algorithmique et programmation récursive (LIFAPR)
  • Programmation fonctionnelle (LIFAPF)
Du point de vue algorithmique et structure de données, elle suppose la maîtrise des notions suivantes :
  • conteneurs de base : tableaux, tableaux dynamiques, listes chaînées (LIFAPI, LIFAPSD)
  • arbres binaires de recherche (sans stratégie de rééquilibrage) (LIFAPR, LIFAPSD)
  • conception et compréhension d'algorithmes itératifs simples à base de boucles (LIFAPI)
  • conception et compréhension d'algorithmes récursifs simples : cas d'arrêt, appel récursif (LIFAPR)
  • notion de pile d'appels de fonction et de tas pour l'allocation dynamique de mémoire (LIFAPSD)
Du point de vue pratique, les travaux pratiques se feront en C++. Une maîtrise de base de ce langage et de la programmation en général est attendue :
  • maîtrise de son système d'exploitation et de l'installation de logiciels (LIFAPCD)
  • maîtrise d'un éditeur de code (LIFAPCD)
  • compilation d'un programme décrit sur plusieurs fichiers (LIFAPCD)
  • structures de données de base en C++ : types primitifs, tableaux, adresses (pointeurs), références (LIFAPI, LIFAPSD)
  • allocation dynamique, construction et destruction des structures de données (LIFAPSD)
  • récupération et analyse des erreurs de compilation simples (erreurs de syntaxe, de typage) (LIFAPCD)
  • récupération et analyse des erreurs d'exécution simples (erreur de segmentation, boucle infinie) (LIFAPCD)
Enfin certaines notions mathématiques sont nécessaires pour la compréhension de cette UE :
  • compréhension d'énoncés formels utilisant des quantificateurs : pour tout, il existe
  • notation de sommation (somme pour i allant de a à b), factorisation et développement
  • expression générale de la somme des termes de suites arithmétiques et géométriques
  • mécanisme de preuve, en particulier preuve par récurrence
  • notions élémentaires de probabilités : calcul de moyenne, distribution uniforme
    Compétences attestées (transversales, spécifiques) :
Cette UE apporte des compétences à la fois formelles et pratiques liées à la compréhension, la conception et la mise en œuvre d'algorithmes. Du point de vue de la compréhension et conception, elle apporte des compétences pour :
  • Analyser et décomposer une tâche pour concevoir un algorithme
  • Concevoir des algorithmes répondant à un cahier des charges, en choisissant les structures de données adéquates
  • Concevoir un algorithme itératif ou récursif adapté à une structure de données
  • Dérouler un algorithme ou un code écrit dans un langage quelconque à la main
  • Traduire un algorithme décrit formellement dans un langage de programmation
  • Identifier et manipuler les représentations des données en machine
  • Utiliser les algorithmes classiques, les combiner pour résoudre des problèmes complexes
  • Évaluer la complexité algorithmique d’une solution ou d’un algorithme proposé
  • Expliquer le modèle d’exécution mémoire d’un programme C et la pile logicielle
  • Modéliser des problèmes concrets en des instances de problèmes plus abstraits (codage, logique, graphes)
En ce qui concerne la mise en œuvre pratique via la traduction dans un langage de programmation et son exécution sur une machine, cette UE aspire à permettre de :
  • Reproduire, décrire la chaîne d’interprétation ou de compilation et savoir interpréter/compiler une application avec les systèmes de build standards des langages standards
  • Résoudre un problème logiciel (erreur à la compilation, à l’exécution)
  • Illustrer la bonne exécution d’un programme en programmant les bonnes sorties issues de bons jeux de tests
  • Évaluer en pratique les performances d’une solution
Enfin plus généralement, elle apporte des compétences relative au développement d'applications robustes, durables et maintenables, dans le cadre d'un travail en groupe :
  • Architecturer un logiciel complexe en définissant le modèle des données et la structure des composants à concevoir ou à utiliser
  • Distinguer, comparer, choisir certaines architectures logicielles ou certains design patterns
  • Utiliser des composants logiciels existants et les intégrer dans un développement
  • Programmer un logiciel implémentant une spécification fonctionnelle et technique
  • Assurer la pertinence, la fiabilité et la qualité d’une solution algorithmique ou logicielle
  • Lire et analyser une spécification, en tirer une réalisation
    Programme de l'UE / Thématiques abordées :
Cette UE aborde la conception et l'analyse d'algorithmes, ainsi que diverses structures de données classiques que l'on peut trouver dans les librairies standard de la plupart des langages de programmation pour répondre aux besoins usuels. Elle aborde en particulier :
Selon les années, il sera également possible d'aborder certaines notions supplémentaires :
  • preuves de programmes
  • algorithmes glouton, programmation dynamique
  • problèmes classiques sur les graphes (coloration, flots)
Date de la dernière mise-à-jour : 13/05/2020
SELECT MEN_ID, `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`, `PAR_ID` FROM parcours INNER JOIN ue_parcours ON PAR_ID_FK=PAR_ID INNER JOIN mention ON MEN_ID = PAR_MENTION_FK WHERE PAR_ACTIVATE = 0 AND UE_ID_FK='292' ORDER BY `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`