CM1-introduction et rappels.pdf

LIFAPSD – Algorithmique, Programmation et Structures de données Nicolas Pronost Présentation de l’UE L’algorithmique et la programmation sont au centre de toutes applications logicielles, tous domaines confondus Génie Analyse...

LIFAPSD – Algorithmique, Programmation et Structures de données Nicolas Pronost Présentation de l’UE L’algorithmique et la programmation sont au centre de toutes applications logicielles, tous domaines confondus Génie Analyse logiciel numérique Bio- Interaction informatique homme- machine Algorithmique et Intelligence Système et programmation artificielle réseaux Informatique Bases de graphique et Sécurité données vision informatique 2 Place de l’UE dans le parcours LIFAP LIFAPI LIFAPR Algorithmique programmation Algorithmique et programmation récursive impérative, initiation LIFBAP Bases de l’architecture pour la programmation LIFAPSD Algorithmique, Programmation et Structures de Données LIFAPCD LIFAPC LIFAPOO Conception et Algorithmique Algorithmique et développement programmation et programmation d’applications complexité orienté objet 3 Prérequis (surtout LIFAPI) Savoir écrire un algorithme simple en langage algorithmique manipuler des variables de type booléen, entier, réel, caractère manipuler des tableaux et des 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/C++ 4 Contenu de l’UE LIFAPSD Manipulation des principales structures de données utilisées en informatique types primitifs: entier, réel, caractère, booléen, pointeur types agrégés: tableau et structure gestion des entrées-sorties: standard et fichier structures dynamiques: tableau, liste, arbre, pile et file 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 5 Objectifs d’apprentissage A la fin de cette UE, vous serez capable d’expliquer les forces et faiblesses des structures de données classiques de construire une structure de donnée complexe à partir de structures de base de prévoir l’évolution des données manipulées par un algorithme de mesurer l’efficacité d’un algorithme simple de concevoir un algorithme s’appuyant sur une structure de données appropriée de mettre tout ça en œuvre en C++ 6  Modalités d’évaluation 2 CC de TD 20 % (individuel, en salle de TD, env. 15 min) (10+10) 2 CC de TP 40 % (individuel, en salle de TP, env. 30 min) (20+20) ECA (session 1, début janvier) 40 % (individuel, anonyme, en amphi, 1h30) Rattrapage de l’ECA (session 2, fin juin) 40 % (individuel, anonyme, en amphi, 1h30) Le rattrapage de session 2 ne remplace que la note de l’ECA de janvier, pas la note globale de l’UE, et le remplace dans tous les cas (même si note obtenue inférieure). Les autres notes (CC de TD et TP notés) sont conservées. Une absence justifiée à un CC entraine sa neutralisation et injustifiée un zéro au CC. Une absence (justifiée ou injustifiée) à l’ECA entraine un zéro à l’épreuve. 7 Informations pratiques Site de l’UE http://licence-info.univ-lyon1.fr/LIFAPSD Informations générales sur l’UE Transparents des CM Ressources pour certains TP Vous pouvez venir en TP avec vos ordinateurs portables Diapositives des cours et polycopié TD/TP Notes de cours dès le début de semestre Pas besoin d’imprimer le polycopié vous-même, il vous sera distribué au premier TD Corrigés des exercices de TD (au fur et à mesure) Corrigés des exercices de TP (au fur et à mesure) Annales d’examens (énoncés et corrigés) Littérature (liens) 8 Chapitre 1 Introduction et rappels 9 Qu’est ce qu’un programme? Déclarations et définitions de données Structurées en « structures de données » Décrivent les données à manipuler tab : tableau [1...15] de réels double tab ; i : entier int i; moy : réel float moy; Instructions Structurées par l’algorithme Décrivent les actions à effectuer sur les données moy ← 0.0 moy = 0.0; Pour i allant de 1 à 15 par pas de 1 faire for (i=0;i caractères Une grille (dame, échec, reversi) => tableau statique 2D Le joueur => structure/classe Les éléments à afficher à l’écran => tableau de taille dynamique Les sauvegardes => fichier Le déplacement des ennemis => graphe 12 Notion de variable Chaque variable possède un nom un type, et donc une taille en octets une adresse en mémoire, qui ne change pas au cours de l’exécution une valeur, qui elle peut changer au cours de l’exécution du programme Quand une nouvelle valeur est placée dans une variable (par affectation ou cin), elle remplace et détruit la valeur précédente PILE int a = 2; a 2 1005 13 Taille des types primitifs Taille supposée pour le modèle Type théorique utilisé en LIFAPSD char, bool 1 octet int, float 4 octets double, @ 8 octets 14 Taille des types primitifs Si vous êtes curieux pour votre machine #include int main () { cout