Aperçu des sections

  • Présentation

    Organisation : 4 CM + 4 TP, chacun d'1 h 15. Chacun(e) peut venir et repartir quand il ou elle veut, en fonction de ses besoins.

    Cet enseignement est plutôt orienté vers les grands débutants en informatique, mais des étudiants plus confirmés pourront y trouver çà et là une occasion de remettre leurs idées en place, voire d'aborder quelques éléments nouveaux.

    Le cours magistral est axé sur l'algorithmique, indépendamment des langages de programmation ; des exercices en classe s'y intercalent de temps en temps.

    Les TP sont placés dans l'emploi du temps nettement après le début de l'enseignement de C de 3e année ; axés sur la maîtrise de la programmation dans ce langage, ils se déroulent sous forme de séances de soutien, alternant à la demande aide individuelle et reprise de notions délicates au tableau.


    Le plan prévisionnel du cours magistral est le suivant :


    I) Kit de survie

    * Concevoir un algorithme et le programmer, à la convergence d'un projet destiné à satisfaire un besoin, d'une machine séquentielle munie d'un système d'exploitation, et d'une intelligence humaine.

    * "Algorithms + Data Structures = Programs" : instructions simples et composées, constantes et variables, types (valeurs accessibles et opérateurs prédéfinis), objets et paquetages.


    II) Organiser un algorithme de façon modulaire

    * Sous-programmes, fonctions et procédures ; paramètres et variables locales, portée et visibilité ; déclaration vs. définition.

    * Paramètres formels et réels ; passage de paramètres par valeur et par adresse ; rôle des pointeurs.

    * Récursivité ; instances du sous-programme récursif et pile des appels.


    III) Structures de données

    * Tableaux et enregistrements

    * Piles, listes, files, arbres.


  • Algorithmique

    On trouvera ci-dessous :

    * un algorithme dont il est demandé de comprendre le fonctionnement et la finalité ("Un algorithme mystérieux") ;

    * un très célèbre et très fondamental article scientifique expliquant comment décomposer un problème en sous-problèmes plus simples, et mettant en valeur l'importance des choix en matière de structure de données ; une solution itérative et une solution récursive sont données pour l'exemple choisi, consistant à placer, sans conflit, 8 reines sur un échiquier ("Program Development by Stepwise Refinement") ;

    * des exercices d'entraînement à l'algorithmique, de niveau très varié ("Entraînements d'algorithmique") ;

    * une présentation un peu plus détaillée d'un de ces exercices d'entraînement ("La conjecture de Syracuse").


    Toutes ces lectures et activités sont facultatives, mais fortement recommandées ; les exercices ne seront ni corrigés ni notés, mais je serai ravi d'examiner les solutions, partielles ou complètes, que me proposeront les étudiants, et de donner des indications pour les améliorer si c'est utile ou nécessaire.

  • Les Tours de Hanoi (récursivité)

    Le problème de mathématique récréative dit des Tours de Hanoi, qui date de 1892, fait partie de ceux dont la solution la plus naturelle est récursive.

    Je vous propose de résoudre cette amusette en quatre étapes, plus une facultative :

    * consultez le début de la page https://fr.wikipedia.org/wiki/Tours_de_Hanoï, jusqu'à "Résolution algorithmique" non compris, pour connaître ou vous remémorer ce dont il s'agit

    * élaborez un algorithme récursif résolvant le problème à N disques (je vous recommande de vous inspirer de la solution à 4 disques présentée sous forme d'animation sur cette page - NB : page consultée le 07/09/2018)

    * vérifiez que votre algorithme se ramène à celui donné au paragraphe "Solution récursive" de la page Wiki

    * adaptez au besoin le programme correspondant pour qu'il produise un résultat identique au contenu du premier fichier ci-dessous dans le cas où on déplace une Tour de Hanoi comprenant 4 disques d'or de l'aiguille de diamant n° 1 à l'aiguille n° 3 ; le second des deux fichiers ci-dessous contient un exemple de solution, programmé en Ada

    * (facultatif) étendez votre algorithme de sorte à pouvoir connaître, à tout moment, quels sont les disques présents sur chaque poteau (ce qui permet, par exemple, une visualisation graphique de chaque étape de la résolution).

  • Programmation en C

    La syntaxe du C n'est pas enseignée lors de ces séances de remise à niveau ; les étudiants sont renvoyés pour cela à leurs cours de 3e année MIC / IMACS ou aux divers sites d'apprentissage disponibles.

    Deux documents sont cependant fournis ci-dessous : un exemple commenté de petit programme en C, et un cours très complet et intéressant, comprenant de nombreux exercices corrigés, rédigé par un chercheur de l'IRIT (Institut de Recherche en Informatique de Toulouse) qui enseigne à l'INSA, Dominique Longin..