Accueil
Professeur et Démonstrateurs
Horaires et locaux
Notes de cours
Démonstrations et devoirs
Examens
Liens utiles
Au sujet du livre de cours
Consultez vos notes
Foire aux questions (FAQ)
|
|
Notes de cours
Deux types de notes vous sont proposés ici:
- 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).
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).
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)
- 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
[lundi 2 décembre 2002] (1 heure)
- 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)
-
Prolog et 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)
-
Scheme suite 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-int
qui 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 produire
4321 , où f est 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):
append et reverse
- récursion terminale
- la forme spéciale
letrec
[mardi 5 novembre 2002] (2 heures)
- Les formes spéciales de base
and ,or ,not , et lambda
- Variables globales et locales en Scheme, notion d'environnement
- Les listes pour représenter des données:
- les formes spéciales
quote et eval
- 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.lex
Vous 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]
|