Concepts Informatiques

Informations générales

Je n’assure plus ce cours qui existe toujours. Les documents ici présents sont donc encore d’utilité publique.

Pré-requis

Ce cours peut-être suivi par tout étudiant ayant des connaissances minimales en programmation. Il a été conçu comme suite possible du cours IP1 du premier semestre de première année de Licence. Il suit aussi le cours PF1 Principes de Fonctionnement des Machines Binaires, lequel est moins nécessaire mais pas inutile.

Contenu

Le cours est en deux parties :

on étudie d’abord d’un point de vue des machines comment différentes constructions des langages de haut-niveau sont implantées (variables globales, pointeurs, références, fonctions, paramètres, variables locales…)
on s’intéresse ensuite à la récursion et ses différentes applications (types récursifs, fonction récursives, élimination de la récursion, optimisation, backtracking…)

Dans le fil du cours, on s’emploie à traduire (compiler) des programmes dans des formes plus proches de celles acceptées par les machines.

Supports de cours

Livre

2014

Jean-Marie Rifflet, Jean-Baptiste Yunès

Fondements de la Programmation Concepts et Techniques Ouvrage

Ellipses, 2014, ISBN: 9782340000148.

Résumé | Liens | BibTeX

@book{rifflet2014fondements,

title = {Fondements de la Programmation Concepts et Techniques},

author = {Jean-Marie Rifflet and Jean-Baptiste Yunès},

url = {https://www.editions-ellipses.fr/accueil/8629-fondements-de-la-programmation-concepts-et-techniques-9782340000148.html#description-scroll-tricks},

isbn = {9782340000148},

year  = {2014},

date = {2014-08-26},

publisher = {Ellipses},

abstract = {Cet ouvrage, à l’usage de tout informaticien, du programmeur à l’ingénieur, a pour but de fixer plus profondément un certain nombre de concepts de programmation. Ce livre n’est pas un manuel de programmation au sens traditionnel. On n’y trouvera pas l’habituelle litanie des arcanes syntaxiques de tel ou tel langage, d’abord parce qu’il ne se focalise pas sur un langage en particulier et ensuite parce qu’il ne se préoccupe pas de ces questions largement traitées par ailleurs. Son but est de cerner au travers d’exemples très nombreux, plus de 120 programmes documentés et décortiqués, quelques concepts essentiels de la programmation :

– les notions de variables, pointeurs, références, tableaux et structures qui prennent des formes variées et s’utilisent différemment selon les langages

– le concept de fonctions, appels de fonctions, transmissions de paramètres et renvois de valeurs

– la structure de pile et ses usages

– la récursion, ses différentes formes, ses avantages et inconvénients.

L’approche proposée est volontairement pragmatique, presque aucun formalisme n’est utilisé. Il s’agit d’écrire des programmes dans divers langages couramment utilisés (principalement Java, C, C++ mais pas seulement) illustrant des concepts, de les traduire vers une machine virtuelle simple permettant de comprendre comment ces constructions s’incarnent en machine et donc quels sont leurs impacts sur l’exécution des programmes : performance ou fiabilité par exemple. Par conséquent, le lecteur, qu’il soit débutant ou confirmé, sera par la suite capable de faire des choix bien éclairés et de mieux conduire sa conception de programmes.

Les codes sources des programmes peuvent être retrouvés sur Internet à partir des pages des auteurs.},

keywords = {},

pubstate = {published},

tppubtype = {book}

}

Fermer

Vidéos et illustrations

Reportez-vous à la fin de la page ici.

2015—2016

premier cours, les variables, types primitifs et valeurs, types références, objets (tableaux). Le code commenté du cours.
second cours, les variables statiques, les constantes, les variables locales et la pile, le passages des arguments par valeur, le test d’égalité entre variables, les tableaux à deux dimensions. Le code du cours.
troisième cours, la création des variables locales suit un procédé particulier, la structure de donnée associée est une pile, dont voici une implémentation qui utilise comme réserve un tableau
quatrième cours, de l’usage de la pile pour vérifier le parenthésage d’une expression ou pour évaluer une expression arithmétique
cinquième cours, la réécriture de programmes Java en programmes Java plus proches d’un point de vue structurel de ceux d’une machine physique: la simple séquence et sa traduction, des variables statiques et la traduction et la rupture conditionnelle le if et sa traduction (agrémentée d’une trace du séquençage des instructions)
sixième cours, la réécriture de programes (suite): la boucle for et sa traduction, l’appel de fonction et sa traduction avec une pile annexe, des appels de fonction imbriqués et la traduction avec une pile annexe, puis la traduction sans pile annexe (création d’une pile dans la mémoire)
septième cours, la récursion et sa traduction. Une suite (arithmétique) définie récursivement et sa traduction en machine. La pile est implantée dans la mémoire…
huitième cours, le problème de la conversion d’un calcul itératif en calcul récursif et vice-versa, les deux versions de la factorielle, la transformation itérative en récursive, puis récursive en itératif par le passage en récursion terminale. Une illustration de la récursion pour dessiner un «arbre» (avec des feuilles).
neuvième cours. Réduction de la récursion, par une analyse de la fonction calculée pour accélerer la convergence de l’argument (l’exponentiation rapide) ou par mémoisation pour obtenir une réduction de l’arbre de calcul (Fibonacci)
dixième cours. Le rebroussement, retour sur trace ou backtracking illustré par le rendu de monnaie
onzième cours. La récursion et ce que l’on peut en retirer. Y-a-t’il une sortie pour un labyrinthe ? Combien de sorties ? Combien de chemin ? Quels chemins ? Le code
Partiel

2014—2015

premier cours : la compilation, l’analyse concernant les variables, distinction entre : symbole, stockage/emplacement, valeur, adresse, contenu, contenant. Un exemple en Java et un exemple en C.
second cours : le passage par valeur; les différentes zones mémoires. L’exemple du cours.
troisième cours : le fonctionnement d’une pile et l’implémentation d’une pile.
quatrième cours : l’utilisation d’une pile pour analyser le parenthésage d’une expression et pour évaluer une expression arithmétique postfixée
cinquième cours : la traduction « machine » de structures de contrôle du flux d’exécution : la sequence et sa traduction, l’aternative et sa traduction et la boucle tant-que et sa traduction.
sixième cours, la traduction d’appel de fonction sans récursion : l’appel à une fonction et sa traduction, des appels à plusieurs fonctions et sa traduction, une fonction avec argument et sa traduction
septième cours : un programme récursif calculant une suite arithmétique et sa traduction avec une pile d’appels, un exemple d’affichage de la fractale « triangle de sierpinski » lequel nécessite des classes utilitaires additionnelles du package fr.upd.
huitième cours, quelques usages de la récursion : considérations sur le calcul de la suite de Fibonnacci (récursion d’ordre 2, nombre d’appels, temps de calcul, espace de calcul), rappel sur l’existence de structures de données définies récursivement (la liste), utilisation de la récursion pour générer des approximations de fractales (objets auto-similaires) comme la courbe du Dragon qui fait super-méga-peur (un Dragon!). Le programme utilise une classe annexe servant à simplifier l’affichage graphique en Java :
- sa documentation
- son code. Pour l’utiliser, le plus simple est de désarchiver le fichier téléchargé directement dans le répertoire contenant les sources du programme. Sinon, il faut utiliser l’option -classpath ou -cp à la compilation et l’exécution à la main, ou configurer l’IDE utilisé (pour éclipse c’est très bien documenté sur Internet via une recherche adéquate du type installer un package externe sous Eclipse)
neuvième cours, récursion terminale et dérécursion, le cas de la factorielle et le cas de l’exponentiation rapide
dixième cours et onzième cours, la version finale de l’exponentiation rapide, la mémoisation de la suite de fibonacci et backtracking sur le Sudoku.
Partiel 2015
Examen 2015 session 1
Examen 2015 session 2

2013—2014

premier cours : discussion sur le statut syntaxique des variables (l-value, r-value), la compilation, le stockage en mémoire des variables, le concept de référence vers objet (illustré via les tableaux) et les initialisations : l’exemple du cours
second cours : discussion sur le statut mémoire des variables (statique, pile, tas) et le mode de transmission d’arguments en Java (pour les variables primitives) : l’exemple du cours
troisième cours : discussion sur la sémantique de la transmission de paramètres par valeur. De l’impossibilité d’échanger des variables primitives transmises en paramètre via un appel de fonction premier exemple et de l’accès possible à des variables via des références transmises en paramètres de sorte qu’un échange de variables manipulées indirectement soit rendu possible second exemple
quatrième cours : les piles et à quoi elles servent; étude du problème de l’interprétation d’une expression arithmétique en notation post-fixée (polonaise inversée) : l’exemple du cours
cinquième cours : réaliser des appels de fonction avec une pile (merci à Jean-Marie Rifflet pour m’avoir remplacé) : blocs d’activation (stack frame), pile (stack)
sixième cours : retour sur la traduction de programme : la séquence (source, traduction), l’alternative (source, traduction), une pile implémentée à l’aide d’un tableau source et son implantation dans notre machine source
septième cours, un exemple de programme appelant une fonction et sa traduction machine, un exemple de définition de fonction récursive (naïve), un exemple de calcul récursif de la valeur du terme d’une suite récurrente
huitième cours, un exemple de calcul récursif de la suite de Fibonacci, un exemple d’affichage de la fractale « triangle de sierpinski » lequel nécessite des classes utilitaires additionnelles du package fr.upd:
- la documentation
- le code. Pour l’utiliser, le plus simple est de désarchiver le fichier téléchargé directement dans le répertoire contenant les sources du programme. Sinon, il faut utiliser l’option -classpath ou -cp à la compilation et l’exécution à la main, ou configurer l’IDE utilisé (pour éclipse c’est très bien documenté sur Internet via une recherche adéquate du type installer un package externe sous Eclipse)
- un exemple d’affichage de la courbe du Dragon (exemple réalisé par M. Patrick Chen)
neuvième cours, les exemples de dé-récursion : P1, P2, Factorielle, Exponentielle rapide
onzième cours, savez-vous sortir d’un labyrinthe ?.

2012—2013

premier cours : discussion sur le statut syntaxique des variables (l-value, r-value), la compilation, le stockage en mémoire des variables, le concept de référence vers objet (illustré via les tableaux) et les initialisations : l’exemple du cours
second cours : discussion sur le statut mémoire des variables (statique, pile, tas) et le mode de transmission d’arguments en Java (pour les variables primitives) : l’exemple du cours
troisième cours : discussion sur la sémantique de la transmission de paramètres par valeur. De l’impossibilité d’échanger des variables primitives transmises en paramètre via un appel de fonction premier exemple et de l’accès possible à des variables via des références transmises en paramètres de sorte qu’un échange de variables manipulées indirectement soit rendu possible second exemple
quatrième cours : les piles et à quoi elles servent; étude du problème de l’interprétation d’une expression arithmétique en notation post-fixée (polonaise inversée) : l’exemple du cours
cinquième cours : réaliser des appels de fonction avec une pile (merci à Jean-Marie Rifflet pour m’avoir remplacé) : blocs d’activation (stack frame), pile (stack)
sixième cours : retour sur la traduction de programme : la séquence (source, traduction), l’alternative (source, traduction), une pile implémentée à l’aide d’un tableau source et son implantation dans notre machine source
septième cours, un exemple de programme appelant une fonction et sa traduction machine, un exemple de définition de fonction récursive (naïve), un exemple de calcul récursif de la valeur du terme d’une suite récurrente
huitième cours, un exemple de calcul récursif de la suite de Fibonacci, un exemple d’affichage de la fractale « triangle de sierpinski » lequel nécessite des classes utilitaires additionnelles du package fr.upd:
- la documentation
- le code. Pour l’utiliser, le plus simple est de désarchiver le fichier téléchargé directement dans le répertoire contenant les sources du programme. Sinon, il faut utiliser l’option -classpath ou -cp à la compilation et l’exécution à la main, ou configurer l’IDE utilisé (pour éclipse c’est très bien documenté sur Internet via une recherche adéquate du type installer un package externe sous Eclipse)
- un exemple d’affichage de la courbe du Dragon (exemple réalisé par M. Patrick Chen)
neuvième cours, les exemples de dé-récursion : P1, P2, Factorielle, Exponentielle rapide
onzième cours, savez-vous sortir d’un labyrinthe ?.
Partiel 2013 et la correction de l’exercice 2.
Examen 2013 et sa correction partielle
Examen 2013 session 2
Corrigé de l’examen 2012 : Exercice 1, Exercice 2, Exercice 3

2011—2012

Pour l’année 2011—2012, voici quelques archives de TD :

TD1 : variables, types, références et valeurs
TD2 : passage de paramètres
TD3 : piles (non électriques)
TD4 : traduction de programmes
TD5 : itérer, récurer?
TD6 : traduction de programmes 2, retour vers l’enfer, il faut appeler des fonctions!
TD7 : programmation dynamique
TD8 : récursion, il faut l’éliminer…
TD9 : savez-vous rebrousser chemin ?