LAMP: Programmation IV

11 ao?t 2006

• La correction de l'examen final ? ét? mise en ligne environ l?.

Le cours porte sur les paradigmes de programmation avancés, en couvrant notamment:

• la Programmation Fonctionnelle
• la Programmation Logique

Pour la programmation fonctionnelle on utilisera le langage Scala.

Semaine 1 (15 mars):

• Introduction. Programmation impérative : transformeurs de prédicats. Programmation fonctionnelle : Scala, environnement et évaluation d'une fonction, appel par valeur, appel par nom, fonctions imbriquées, portée lexicale. Requêtes XML. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 2 (22 mars):

• Programmation fonctionnelle?: modèle d'évaluation, récursion terminale, définition de valeurs, fonctions d'ordre supérieur, fonctions anonymes, currification, types fonctionnels. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 3 (29 mars):

• Abstractions de données?: objets, méthodes, auto-référence, classes et substitutions, opérateurs, classes abstraites, extension d'une classe, liaison dynamique, classes standards. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 4 (5 avril):

• Filtrage de motifs?: décomposition OO contre décomposition fonctionnelle, classes "cas". Listes?: constructeurs, opérations primitives, polymorphisme, concaténation. Exceptions. La classe List. Tri de listes, schémas récurrents avec les listes, motifs de calcul avec fonctions d'ordre supérieur. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 5 (12 avril):

• Fonctions d'ordre supérieur sur les listes. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 6 (26 avril):

• Preuve de programmes fonctionnels: induction structurelle. La notation For?: syntaxe, exemples, traduction. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 7 (3 mai):

• Fonctions et objets. Application du filtrage de motif ? la différentiation symbolique. Déomposition orient?-objet et déomposition utilisant le filtrage de motif. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 8 (10 mai):

• Effets de bord: application ? la simulation d'éléments discrets. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 9 (17 mai):

• Réseaux de contraintes. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 10 (24 mai):

• Flots et itérateurs. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 11 (31 mai):

• Lisp (1/2) : préentation du langage, conception d'un interpréeur en Scala. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 12 (7 juin):

• Lisp (2/2) : un interpréteur Lisp en Scala. (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 13 (14 juin):

• Programmation logique (1/2): Prolog, présentation et implémentation (unification). (pdf, ps, 2on1.ps, 4on1.ps).

Semaine 1 (15 mars): Racine carrée, racine cubique, triangle de Pascal.

Enonc? en (pdf) ou (ps).

Solution en (pdf) ou (ps).

Semaine 2 (22 mars): Factorielle, Fibonacci, élévation ? la puissance, polyn?me de Lagrange.

Enonc? en (pdf) ou (ps).

Solution en (pdf) ou (ps).

Semaine 3 (29 mars): Ensembles d'entiers.

Enonc? en (pdf) ou (ps). Source des classes IntSet.

Solution en (pdf) ou (ps).

Semaine 4 (5 avril): Listes associatives.

Enonc? en (pdf) ou (ps).

Solution en (pdf) ou (ps).

Semaine 5 (12 avril): Ensemble des parties, combinaisons de pièces, addition de grands entiers, preuve par induction structurelle.

Enonc? en (pdf) ou (ps).

Solution en (pdf) ou (ps).

Semaine 6 (26 avril): Induction structurelle, preuve de l'inversion de listes, problème des n-reines.

Enonc? en (pdf) ou (ps).

Squelette: queens-partial.scala.

Solution en (pdf) ou (ps).

Semaine 7 (3 mai): Langage d'images pour les fractales.

Enonc? en (pdf) ou (ps).

Bibliothèque : Painter-partial.scala.

Solution en (pdf) ou (ps).

Semaine 8 (10 mai): Simulateur de circuit logique.

Enonc? en (pdf) ou (ps).

Squelette: Simulator-partial.scala.

Solution en (pdf) ou (ps).

Semaine 9 (17 mai):

Examen intermédiaire. (pdf) ou (ps).

Solution en (pdf) ou (ps).

Semaine 10 (24 mai): Fibonacci, ln(2), nombres premiers.

Enonc? en (pdf) ou (ps).

Squelette: week10-partial.scala.

Solution en (pdf) ou (ps).

Semaine 11 (25 mai): Réseaux de contraintes.

Enonc? en (pdf) ou (ps).

Squelette: solver-partial.scala.

Solution en (pdf) ou (ps).

Pour vous faciliter la préparation de l'examen final, voici quelques examens des années passées.
(2004 fin) (2005 fin) (2004 mid) (2005 mid)

Et voici les solutions.
(2004 fin) (2005 fin) (2004 mid) (2005 mid)

Semaine 12 (7er juin): Lisp.

Enonc? en (pdf) ou (ps).

Squelette: lisp-partial.scala.

Solution en (pdf) ou (ps). Code de la solution: lispNew.scala?powerset.lisp.

Semaine 13 (14 juin): Prolog, Lisp.

Enonc? en (pdf) ou (ps).

Interpréteur Prolog: prolog.scala.

Solution en (pdf) ou (ps).

Semaine 14 (21 juin): Examen final

Enonc? en (pdf) ou (ps).

Solution en (pdf) ou (ps).

Utilisation en salle INF2 (Windows)

Nous avons prépar? quelques instructions pour l'utilisation de Scala en salle INF2.

Comment écrire un programme en Scala

Pour compiler et exécuter un programme, suivez les instructions sur la page d'exemples de Scala.

Lien de référence

Le site web de Scala contient toutes les informations utiles au programmeur Scala, en particulier la documentation du language et de la bibliothèque standard.

Vous pouvez egalement profiter des EclipseTutorials.zip (format .doc, anglais) pour installation et execution des programmes en Eclipse.

Le cours a maintenant son forum de discussion?: epfl.ic.cours.programmationIV.

N'hésitez pas ? y exprimer vos interrogations, vos problèmes. D'autres étudiants pourront peut-être vous aider et les assistants s'engagent ? traiter régulièrement les nouveaux messages. C'est aussi par ce biais que nous vous communiquerons des annonces générales concernant le cours.

Le plus simple pour accéder au forum est de le faire?:

• en utilisant le navigateur, ou
• directement par le web.

Enfin, si vous avez des questions générales concernant l'utilisation des forums de discussion ? l'EPFL vous trouverez tout sur le site?: Usenet News

L'intégration des notes de programmation III et IV est terminée. Vous pouvez consulter votre résultat final sur ce document.

L'examen final a ét? corrig?.

Les résultats détaillés pour le cours sont disponible sur ce document.

Le calcul de votre note se fait sur la somme des points que vous avez obtenus sur les deux examens, d'après une échelle linéaire (4 ? partir de 50% du nombre maximum de points possibles, 6 ? partir de 90%).

Toutefois, vu les résultats alarmants du second exercice de l'examen final (sauce au curry), le nombre maximum de points possibles est défini sans les 20 points de cet exercice qui devient effectivement un bonus.

Le cours est donc not? sur 150 points, d'après le barème suivant.

Points	Note
0	1.0
1-14	1.5
15-29	2.0
30-44	2.5
45-59	3.0
60-74	3.5
75-89	4.0
90-104	4.5
105-119	5.0
120-134	5.5
135-149	6.0
150-170	6.0	Avec nos félicitations les plus vives

Vous pouvez consulter votre copie dans le bureau INR 320. Pour être s?rs de trouver quelqu'un, prenez rendez-vous par email.

Professeur

• Martin Odersky, stairsINR319, phone36863

Assistants

• Sébastien Briais, stairsINR317, phone37576
• Gilles Dubochet, stairsINR320, phone36867
• Burak Emir, stairsINR320, phone36867
• Stéphane Micheloud, stairsBC346, phone37593
• Nikolay Mihaylov, stairsINR321, phone36864

Assistants-Etudiants

• Structure and Interpretation of Computer Programs.
  Harold Abelson and Gerald J. Sussman. 2nd edition. MIT Press 1996.
  Consultable également en ligne.
• Approche Fonctionnelle de la Programmation.
  Guy Cousineau et Michel Mauny. Ediscience International. 1998.
• Introduction to Functional Programming using Haskell.
  Richard Bird. Prentice Hall 1998.
• Foundations of Logic Programming.
  J.W. Lloyd. Springer Verlag. 1984.
• Effective Java.
  Joshua Bloch. Addison Wesley, 2001.