| Accueil
 Professeur etDémonstrateurs
 Horaires et locaux
 Notes de cours
 Démonstrationset devoirs
 Examens
 Liens utiles
 Au sujet dulivre de cours
 Consultez vos notes
 Foire aux questions(FAQ)
 |  | Notes de cours
 
Deux types de notes vous sont proposés ici: 
  Mes bonnes résolutions pour cette session: Je ferai le maximum
pour que cette page soit mise à jour avant chaque cours afin que vous
puissiez vous y présenter avec les exemples que nous
étudierons. D'avance mille excuses pour les fois où je n'y parviendrai
pas (le premier cours en est un exemple). les notes de cours réalisées par Marc Feeley
 des brèves de cours qui résument très sommairement
les points importants abordés en cours et proposent le cas échéant des
exemples vus en cours mais non extraits du livre ou des notes de cours
(un peu de variété ne fait pas de mal).  
 
 Prenez note que mes brèves de cours pourront être mise à jour
après le cours concerné.
 
 Acétates rédigées par Marc Feeley
 Cours après cours[lundi 2 décembre 2002] (2 heures)
[lundi 2 décembre 2002] (1 heure) Quelques prédicats classiques (suite)
 arbre de preuve pour insertion permutation d'une liste (essayez de l'écrire en C/C++ ou Java)
 tri d'une liste en O(n.n!)
 un tri plus décent (quicksort)
 les différences de listes (où comment faire une concaténation en temps constant).
 La négation en Prolog 
 Entre l'intuition et la réalité (cas de l'insertion d'une valeur dans un arbre binaire de recherche utilisée pour la suppression)
 
 Prologet les listes
 parallèle avec les listes en Scheme quelques prédicats classiques:
 appartenance d'un élément à une liste
 intersection de deux listes
 concaténation de deux listes
 insertion d'un élément dans une liste
 [mardi 26 novembre 2002] (2 heures)
 
 Unification
 Algorithme de contrôle de Prolog Arbre de preuve
 Structure de données en Prolog [lundi 25 novembre 2002] (1 heure)
 
 Programmation logique et Prolog
 langage déclaratif
 un exemple intuitif
 principes de base de Prolog [mardi 19 novembre 2002] (2 heures)
 
 Schemesuite et fin (attachez vos tuques):
 Deux exemples sur les continuations qui montrent que l'on peut
rendre terminale une récursivité qui ne l'est pas en se servant des
continuations.
 Suppléments:
 
 ai-je déclenché (malgré moi) en vous la passion des
continuations? 
Si oui, alors essayez d'écrire avec une continuation la
méthode
 liste->reverse-intqui prend en paramètre une
liste et une continuation et qui retourne l'entier dont les chiffres
sont en ordre inverse par rapport à la liste:
 (liste->reverse-int '(1 2 3 4) f)devrait produire4321, oùfest une fermeture à définir.
  Voici une solution possible: [cont.scm] où la fonction avec
continuation est masquée.
 [lundi 18 novembre 2002] (1 heure)
 
 les fonctions peuvent avoir comme valeur de retour une fonction
 composition de deux fonctions
 curification d'une fonction
 les continuations
 Suppléments:
 [mardi 12 novembre 2002] (2 heures)
 
 récursion plate versus récursion profonde, cas de la fonction
reverse à votre tour d'être du bon côté du marteau (évaluation du cours)
 les fonctions en Lisp sont des objets de première classe:
 les fonctions peuvent être stockées dans des structures de données
 les fonctions peuvent avoir comme paramètre des fonctions (on parle alors de fonction d'ordre supérieur)
 map
 for-each
 fonctions avec nombre variable d'arguments
 garder les éléments d'une liste qui possèdent une certaine propriété (application au tri-rapide)
 combiner les éléments d'une liste entre-eux à l'aide d'une fonction
 Suppléments:
 
Une version itérative et récursive profonde de
reverse: reverse.scm (ce n'est pas la version prédéfinie de la fonction). [lundi 11 novembre 2002] (1 heure)
 
 les fonctions de traitement des listes (suite): appendetreverse récursion terminale
 la forme spéciale letrec [mardi 5 novembre 2002] (2 heures)
 
Les formes spéciales de base and,or,not, etlambdaVariables globales et locales en Scheme, notion d'environnement
Les listes pour représenter des données:
 les formes spéciales quoteeteval représentation graphique des listes
 les fonctions de traitement des listes: car,cdr,cons,list,car,append,length,member,reverse, etc. [lundi 4 novembre 2002] (1 heure)
 
Introduction aux langages fonctionnels
Particularités de Scheme: typé dynamiquement, portée statique, concis
Évaluation d'une expression en Scheme
Les formes spéciales de base if,let,define,display,write [lundi 28 octobre 2002] (1 heure)
 
Les méthodes (suite et fin, alarme ou pas)
 mécanisme d'appel d'une méthode
 [mardi 22 octobre 2002] (2 heures)
 
Les méthodes (suite et alarme)
 les macros (C) et les procédures en ligne (C++)
 paramètres optionnels (cas de C++)
 surdéfinition d'une méthode (en C++ ou Java)
 surdéfinition d'un opérateur en C++
 risquons nos vies à l'UdeM en restant dans une salle de cours pendant que l'alarme se déclenche
 Suppléments:
 
 Exemple typique de classe C++, surdéfinition des opérateurs: les
déclarations Rational.h, les
définitions Rational.cc et le
programme rat.cc,
 [lundi 21 octobre 2002] (1 heure)
 
Les méthodes (suite)
 passage de paramètre par nom
 cas des tableaux à deux dimensions passés en paramètre (en C, en JAVA)
 cas des méthodes passées en paramètre (C)
 Suppléments:
 
 Illustration du passage par nom exemple.
 Passage d'un tableau à 2 dimensions en paramètre en C: tab2.c.
 Passage d'un tableau à 2 dimensions en paramètre en JAVA: Tab2.java.
 Passage d'une méthode en paramètre: demo1.c.
 [mardi 8 octobre 2002] (2 heures)
 
Représentation de types "utilisateur" classiques (suite et fin)
 les structures, les unions
 les pointeurs (pointeurs fous, fuite de mémoire, et garbage collector)
Les méthodes
 les différents modes de passage des paramètres
 [lundi 7 octobre 2002] (1 heure)
 
Représentation de types classiques
 types primitifs (entiers, flottants, caractères, booléens)
 type pseudo-primitif: string
 types "utilisateur"
 types ordinaux (énumérations et intervalles)
 les tableaux (static, fixed stack-dynamic, stack-dynamic, head-dynamic)
 [mardi 1 octobre 2002] (2 heures)
 
Concept de variable (nom,adresse,valeur,type,durée de vie et portée)
 liens statiques et dynamiques
 liens de typage
 liens de stockage
 vérification de type, langages fortement typés
 [lundi 30 septembre 2002] (1 heure)
 
 Étude d'un compilateur complet (analyse lexicale, syntaxique et
sémantique) traduisant des sources écrits dans un sous-ensemble de C,
en un byte-code réaliste interprétable par une machine à pile:
Suite et fin ! 
 présentation du byte-code
 présentation de la machine à pile associée
 comment générer le byte-code ?
 Suppléments:
 
Le mini-compilateur écrit par Marc Feeley et disponible dans les
notes de cours du même auteur: tinyc.c.
 [mardi 24 septembre 2002] (2 heures)
 
 Analyse syntaxique montante (bottom-up) et descendante (top-down)
 Principes d'écriture d'un analyseur syntaxique descendant
récursif, grammaires LL1
 Étude d'un compilateur complet (analyse lexicale, syntaxique et
sémantique) traduisant des sources écrits dans un sous-ensemble de C,
en un byte-code réaliste interprétable par une machine à pile:
 Suppléments:
 
Le mini-compilateur écrit par Marc Feeley et disponible dans les
notes de cours du même auteur: tinyc.c.
 [lundi 23 septembre 2002] (1 heure)
 
 Analyse lexicale, rôle et implémentations possibles (atomate / lex)
 Écriture d'un analyseur lexical
 Codage direct d'un automate
 Flex
 Suppléments:
 
 Le code d'un mini-analyseur lexical écrit en C: lex.c
 Le code d'un mini-analyseur lexical écrit en
flex, ift2030.lexVous aimez
 flex? Précipitez-vous sur la documentation en
ligne également disponible dans les man-pages (man flex) Un exemple de programme reconnu par les deux analyseurs
précédants: prog.tordu
 [mardi 17 septembre 2002] (2 heures)
 
 Une grammaire est ambiguë s'il existe au moins une chaîne pour laquelle plusieurs arbres syntaxiques existent -> notion de précédance et d'associativité des opérateurs
 Note concernant les notations pré- et post-fixée des expressions
 Analyse lexicale, rôle et implémentations possibles (atomate / lex)
 Un exemple de programme reconnu par les deux analyseurs
précédants: prog.tordu
 [lundi 16 septembre 2002] (1 heure)
 
 Classification Chomskienne des langages (suite et fin?)
 Les langages de type 2 (hors-context / context-free)
 Quelques mots sur les langages de type 1 (contextuels)
 Encore moins de mots sur les langages de type 0 
 Grammaires BNF (Backus Naur Form) et arbres syntaxiques abstraits (ASA)
 [mardi 10 septembre 2002] (2 heures)
 
 
 Brève histoire des langages de programmation (suite et fin)
 Description des langages de programmation
 Pourquoi ?
 Moyens: tutoriels, manuels de référence, description formelle
 Syntaxe versus sémantique 
 Classification chomskiennes des langages
 Grammaire, dérivation
 Les langages réguliers (ou langages de type 3)
 [lundi 9 septembre 2002] (1 heure)
 
 
 Choix des langages de programmation (suite et fin)
 Implémentation des langages de programmation (compilation=traduction vs interprétation)
 Brève histoire des langages de programmation
 Suppléments:
 
Le premier ordinateur électronique utilisable [eniac] (1946, UPenn)
Hiérarchie d'un sous-ensemble de langages marquants
Machine de Von Neumann
Exemple de petit code machine pour famille x86 (Intel):
binaire    hex
10001011   8B  \
01000101   45   | lire 1er entier dans reg. AX
00001010   0A  /
00000011   03  \
01000101   45   | lire 2em entier et ajouter a AX
00010100   14  /
 Que fait ce morceau de programme Pascal ?
|  | read(x); |  | 2: | if x = 0 then goto 8; |  |  | writeln(x); |  | 4: | read(next); |  |  | if next = x then goto 4; |  |  | x := next; |  |  | goto 2; |  | 8: | ; |  Compter les mots d'un texte et afficher les mots en ordre croissant de fréquence. Voici une idée des temps d'exécution: [temps vs formes], [temps vs mots ]
Voici un exemple de corpus sur
lequel appliquer ces programmes.
 [mardi 3 septembre 2002] (2 heures)
 
Bonne rentrée à toutes et tous. Notre premier cours commence avec
quelques généralités:
 
 Tour d'horizon du cours IFT2030, conseils d'usage, etc.
 Quelques raisons pour l'étude de ce cours
 Tour d'horizon des domaines d'application
 Évaluation d'un langage, revue de quelques critères (non exhaustifs et souvent dépendants et/ou contradictoires: facilité de lecture/écriture, orthogonalité, sécurité, coût, support aux gros projets)
 
 [top]
 |