CS2104 Lecture1 - UCLouvain

CS2104 Lecture1 - UCLouvain

FSAB1402: Informatique 2 Algorithmes sur les Listes Peter Van Roy Dpartement dIngnierie Informatique, UCL [email protected] 2007 P. Van Roy. All rights reserved. 1 Ce quon va voir aujourdhui Rsum des derniers cours Techniques de programmation

Utilisation de variables non-lies Amlioration de lefficacit avec un accumulateur Utilisation du type pour construire une fonction rcursive Algorithme de tri: Mergesort Programmer avec plusieurs accumulateurs Programmer avec un tat 2007 P. Van Roy. All rights reserved. 2 Suggestions de lecture pour ce cours Chapitre 1 (sections 1.4-1.6):

Chapitre 3 (section 3.4.1): Notation des types Chapitre 3 (section 3.4.2): Listes et fonctions sur les listes, fonctions correctes Programmer avec les listes Chapitre 3 (section 3.4.3): Les accumulateurs

2007 P. Van Roy. All rights reserved. 3 Rsum des deux derniers cours 2007 P. Van Roy. All rights reserved. 4 Rcursion sur les listes Dfinir une fonction {Nth L N} qui renvoie la nime lment de L Raisonnement:

Si N==1 alors le rsultat est L.1 Si N>1 alors le rsultat est {Nth L.2 N-1} Voici la dfinition complte: fun {Nth L N} if N==1 then L.1 elseif N>1 then {Nth L.2 N-1} end end 2007 P. Van Roy. All rights reserved. 5 Pattern matching (correspondance des formes)

Voici une fonction avec plusieurs formes: fun {Length Xs} case Xs of nil then 0 [] X|Xr then 1+{Length Xr} [] X1|X2|Xr then 2+{Length Xr} end end Comment les formes sont-elles choisies? 2007 P. Van Roy. All rights reserved. 6 Complexit calculatoire Complexit temporelle et spatiale Meilleur cas, pire cas et cas moyen

Analyse asymptotique La notation O Les notations , Attention: est plus difficile que O et ! O : borne suprieure : borne infrieure : borne infrieure et suprieure Complexit temporelle dun algorithme rcursif Complexit en moyenne 2007 P. Van Roy. All rights reserved. 7

Complexit polynomiale Voici une version efficace pour calculer le triangle de Pascal: fun {FastPascal N} if N==1 then [1] else L in L={FastPascal N-1} {AddList {ShiftLeft L} {ShiftRight L}} end end La complexit en temps est O(n2) Complexit polynomiale: un polynome en n 2007 P. Van Roy. All rights reserved. 8 Techniques de

programmation 2007 P. Van Roy. All rights reserved. 9 Techniques de programmation Nous avons dj vu quelques fonctions rcursives sur les listes Nous allons maintenant approfondir les techniques de programmation sur les listes Utiliser les variables non-lies pour faciliter la rcursion

terminale (exemple dAppend) Utiliser un accumulateur pour augmenter lefficacit dun algorithme (exemple de Reverse) Utiliser un type pour dfinir une fonction rcursive (exemple de Flatten) 2007 P. Van Roy. All rights reserved. 10 Rcursion terminale avec les listes 2007 P. Van Roy. All rights reserved. 11 La fonction Append Dfinissons une fonction {Append Xs Ys} qui construit une liste qui est la concatnation de Xs et Ys

Nous faisons un raisonnement inductif sur le premier argument Xs Le rsultat contient les lments de Xs suivi par les lments de Ys Si Xs==nil alors le rsultat est Ys Si Xs==X|Xr alors le rsultat est X|{Append Xr Ys} Faites un dessin pour comprendre cette induction! 2007 P. Van Roy. All rights reserved. 12

Excution dAppend {Append [1 2] [a b]} 1| {Append [2] [a b]} 1| 2| {Append nil [a b]} 1| 2| [a b] 2007 P. Van Roy. All rights reserved. 13 Dfinition dAppend Voici la dfinition de Append: fun {Append Xs Ys} case Xs

of nil then Ys [] X|Xr then X|{Append Xr Ys} end end Est-ce que cette dfinition fait la rcursion terminale? Pour le savoir, il faut la traduire en langage noyau 2007 P. Van Roy. All rights reserved. 14 Append en langage noyau (1) Voici une traduction nave de cette dfinition: proc {Append Xs Ys Zs} case Xs of nil then Zs=Ys [] X|Xr then local Zr in

{Append Xr Ys Zr} Zs=X|Zr end end end Lappel rcursif nest pas le dernier appel! 2007 P. Van Roy. All rights reserved. 15 Append en langage noyau (2) Voici la vraie traduction de la dfinition dAppend: proc {Append Xs Ys Zs} case Xs of nil then Zs=Ys [] X|Xr then local Zr in Zs=X|Zr {Append Xr Ys Zr}

end end end Lappel rcursif est le dernier appel! On peut faire Zs=X|Zr avant lappel parce que Zr est une variable qui nest pas encore lie (un trou dans la liste X|Zr) Technique: dans la construction de listes, on peut utiliser les variables non-lies pour assurer la rcursion terminale 2007 P. Van Roy. All rights reserved. 16 Les accumulateurs avec les listes 2007 P. Van Roy. All rights reserved.

17 La fonction Reverse Dfinissons une fonction qui prend une liste et qui renvoie une liste avec les lments dans lordre invers {Reverse [1 2 3]} = [3 2 1] Voici une dfinition qui utilise Append: fun {Reverse Xs} case Xs of nil then nil [] X|Xr then {Append {Reverse Xr} [X]} end end

Cette dfinition fait deux boucles imbriques Quelles sont ces boucles? 2007 P. Van Roy. All rights reserved. 18 Excution de Reverse Xs=[1 2 3 4] X|Xr=[1 2 3 4] X=1, Xr=[2 3 4] {Reverse Xr}=[4 3 2] {Append {Reverse Xr} [X]} {Append [4 3 2] [1]} [4 3 2 1] 2007 P. Van Roy. All rights reserved. 19

Complexit temporelle de Reverse La fonction {Reverse Xs} a un temps dexcution qui est O(n2) avec n=|Xs| Cest curieux que le calcul de linverse dune liste de longueur n prend un temps proportionnel au carr de n ! On peut faire beaucoup mieux en utilisant un accumulateur Notez que notre premire dfinition nutilise pas daccumulateur 2007 P. Van Roy. All rights reserved. 20 Reverse avec un accumulateur

Il faut un invariant Prenons linvariant suivant: L = reverse(L2) ++ L1 Ici, ++ et reverse sont des fonctions mathmatiques ++ fait la concatnation des listes Ce ne sont pas des fonctions crites en Oz! Rappel: un invariant est une formule mathmatique Nous avons donc une paire (L1, L2)

Quelles sont les transitions de cette paire? 2007 P. Van Roy. All rights reserved. 21 Vases communicants L1=[1 2 3 4], L2=nil L1=[2 3 4], L2=[1] L1=[3 4], L2=[2 1] L1=[4],

L2=[3 2 1] L1=nil, L2=[4 3 2 1] 2007 P. Van Roy. All rights reserved. 22 Transitions de laccumulateur Nous avons une paire (L1,L2) Ltat initial est (L,nil) La transition est: (X|L1,L2) (L1,X|L2)

Ceci est correct parce que si: L= reverse(L2)++(X|L1) alors nous pouvons vrifier que: L= reverse(X|L2)++L1 2007 P. Van Roy. All rights reserved. 23 Dfinition de Reverse avec un accumulateur Voici la nouvelle dfinition: fun {Reverse L1 L2} case L1 of nil then L2 [] X|M1 then {Reverse M1 X|L2} end end

Exemple dun appel: {Reverse [1 2 3] nil} La complexit de cette dfinition est O(n) avec n=|L1| 2007 P. Van Roy. All rights reserved. 24 Utiliser le type pour la rcursion 2007 P. Van Roy. All rights reserved. 25 La fonction Flatten Pour complter le parcours des trois techniques, voici une fonction un peu plus complique Nous voulons dfinir la fonction {Flatten Xs} qui prend une liste Xs qui peut contenir des

lments qui sont eux-mmes des listes, et ainsi de suite, et qui renvoie une liste de tous ces lments Exemple: {Flatten [a [[b]] [c nil d]]} = [a b c d] 2007 P. Van Roy. All rights reserved. 26 Utiliser un type pour dfinir une fonction Pour dfinir {Flatten Xs}, nous allons dabord dfinir le type de largument Xs, En suivant le type, la dfinition sera simple ::= nil | | | T | Pour que le choix de lalternatif soit non-ambigu, il faut que T ne soit ni nil ni une liste lmentaire (un cons)

fun {IsCons X} case X of _ | _ then true else false end end fun {IsList X} X==nil orelse {IsCons X} end 2007 P. Van Roy. All rights reserved. 27 Dfinition de Flatten Voici la dfinition: fun {Flatten Xs} case Xs of nil then nil

[] X|Xr andthen {IsList X} then {Append {Flatten X} {Flatten Xr}} [] X|Xr then X|{Flatten Xr} end end Pour les avertis: faites une version de Flatten qui utilise un accumulateur! 2007 P. Van Roy. All rights reserved. 28 Algorithmes de tri 2007 P. Van Roy. All rights reserved. 29 Algorithmes de tri Un algorithme de tri prend une liste

dlments et renvoie une liste avec les mmes lments rangs selon un ordre Il y a beaucoup dalgorithmes de tri diffrents Tri par slection, tri par insertion Mergesort (tri par divisions et fusions rcursives) Heapsort (tri par construction de tas (heap) ) Quicksort (tri par partitionnement rcursif) 2007 P. Van Roy. All rights reserved. 30 Mergesort Cet algorithme peut trier une liste de taille n en un temps maximal de O(n log n) Lalgorithme peut facilement tre programm

dans le modle dclaratif Lalgorithme utilise une technique gnrale appele diviser pour rgner Diviser la liste en deux listes Utiliser mergesort rcursivement pour trier les deux listes Fusionner les deux listes pour obtenir le rsultat 2007 P. Van Roy. All rights reserved. 31 Exemple de Mergesort (1) Prenons la liste L=[5 2 6 4 3] Diviser L en deux listes:

Trier chacune des deux listes: S1=[2 5], S2=[3 4 6] Fusionner les deux listes S1 et S2: L1=[5 2], L2=[6 4 3] Ceci est la cl de lalgorithme! On peut le faire en traversant chaque liste au maximum une fois (voir dessin sur le tableau)

Le rsultat est la liste trie S=[2 3 4 5 6] 2007 P. Van Roy. All rights reserved. 32 Exemple de Mergesort (2) L11 L1 split merge L12 L S11 S1 S12

split merge L21 L2 split Observez S21 merge L22 S S2 S22

comment est faite la rcursion! 2007 P. Van Roy. All rights reserved. 33 Dfinition de Mergesort fun {Mergesort Xs} case Xs of nil then nil [] [X] then [X] else Ys Zs in {Split Xs Ys Zs} {Merge {Mergesort Ys} {Mergesort Zs}} end end 2007 P. Van Roy. All rights reserved. 34 Dfinition de Split

proc {Split Xs Ys Zs} case Xs of nil then Ys=nil Zs=nil [] [X] then Ys=Xs Zs=nil [] X1|X2|Xr then Yr Zr in Ys=X1|Yr Zs=X2|Zr {Split Xr Yr Zr} end end 2007 P. Van Roy. All rights reserved. 35 Dfinition de Merge fun {Merge Xs Ys} case Xs#Ys of nil#Ys then Ys

[] Xs#nil then Xs [] (X|Xr)#(Y|Yr) then if X 36 Programmer avec des accumulateurs 2007 P. Van Roy. All rights reserved. 37 Cest quoi en fait un accumulateur?

Un accumulateur peut tre vu comme une paire de deux arguments, une entre et une sortie Par exemple, dans la fonction Reverse, nous avons (1) largument L2 et (2) le rsultat de la fonction: fun {Reverse L1 L2} {Reverse M1 X|L2} end On voit mieux les deux arguments si on crit Reverse en langage noyau: (comme toujours, on voit mieux en langage noyau!) proc {Reverse L1 L2 R2} {Reverse M1 X|L2 R2} end Laccumulateur est la paire (L2,R2) L2 est lentre, R2 est la sortie 2007 P. Van Roy. All rights reserved.

38 Programmer avec plusieurs accumulateurs Nous avons dj vu comment crire une fonction avec un seul accumulateur Laccumulateur = un des arguments de la fonction + le rsultat de la fonction En langage noyau, on voit bien quun accumulateur est une paire de deux arguments, une entre et une sortie

Nous avons vu que lutilisation dun accumulateur est une bonne ide pour lefficacit (rcursion terminale une boucle) Maintenant, nous allons voir comment on peut crire un programme avec plusieurs accumulateurs On verra plus tard que lutilisation daccumulateurs nest rien dautre que programmer avec un tat: chaque accumulateur correspond une variable affectation multiple 2007 P. Van Roy. All rights reserved. 39 Programmer avec accumulateurs = programmer avec un tat Ltat dun programme est lensemble de donnes importantes pour le programme un instant donn

Ltat est pass partout dans le programme et transform successivement pour obtenir un rsultat Ltat = la valeur de tous les accumulateurs Ltat S est fait de plusieurs parties, qui sont en fait des accumulateurs: S=(X,Y,Z, ) Pour chaque procdure P, lentte devient: proc {P Xin Xout Yin Yout Zin Zout } 2007 P. Van Roy. All rights reserved. 40 Schma gnral dune procdure (1)

Voici un diagramme qui montre une procdure P avec deux accumulateurs (quels sont ces accumulateurs?) P Xin Xout Yin Yout Etat lentre Etat la sortie 2007 P. Van Roy. All rights reserved. 41

Schma gnral dune procdure (2) Ltat S de cet exemple contient deux parties: S=(X,Y) Voici une dfinition possible de la procdure P: proc {P Xin Xout Yin Yout} {P1 Xin X1 Yin Y1} {P2 X1 X2 Y1 Y2} . {Pm Xn Xout Yn Yout} end Si le nombre daccumulateurs est plus grand quun, comme ici, alors il est plus facile dutiliser des procdures au lieu des fonctions 2007 P. Van Roy. All rights reserved.

42 Schma gnral dune procdure (3) Voici un diagramme qui montre la dfinition de la procdure P qui a deux accumulateurs P Xin Xin X1 P1 Yin Yin X2 P2

Y1 Y2 Xn Xout Xout Yout Yout Pm Yn 2007 P. Van Roy. All rights reserved.

43 Exemple avec deux accumulateurs Supposons quon dispose dune machine pile pour valuer des expressions arithmtiques Par exemple: (1+4)-3 La machine excute les instructions suivantes: push(1) push(4) 1 5 5 2 plus 4

3 push(3) minus Sommet de la pile 2007 P. Van Roy. All rights reserved. 44 Compilateur pour machine pile (1) Dfinissez une procdure qui prend une expression arithmtique, exprime comme une structure de donnes, et qui calcule deux rsultats: (1) une liste dinstructions pour une machine pile et (2) un compte du nombre dinstructions

Lexpression (1+4)-3 est exprime comme [[1 plus 4] minus 3] La procdure a lentte suivante: proc {ExprCode Expr Cin Cout Nin Nout} Il y a deux accumulateurs, C et N: Cin: liste dinstructions initiale Cout: liste dinstructions finale Nin: compte dinstructions initial Nout: compte dinstructions final 2007 P. Van Roy. All rights reserved. 45 Compilateur pour machine pile (2)

proc {ExprCode Expr C0 C N0 N} case Expr of [E1 plus E2] then C1 N1 in C1=plus|C0 N1=N0+1 {SeqCode [E2 E1] C1 C N1 N} [] [E1 minus E2] then C1 N1 in C1=minus|C0 N1=N0+1 {SeqCode [E2 E1] C1 C N1 N} [] I andthen {IsInt I} then C=push(I)|C0 N=N0+1 end end 2007 P. Van Roy. All rights reserved. 46 Compilateur pour machine pile (3)

proc {SeqCode Es C0 C N0 N} case Es of nil then C=C0 N=N0 [] E|Er then C1 N1 in {ExprCode E C0 C1 N0 N1} {SeqCode Er C1 C N1 N} end end 2007 P. Van Roy. All rights reserved. 47 Un autre exemple (1) On peut faire une version de Mergesort qui utilise un accumulateur proc {Mergesort1 N S0 S Xs}

N est un entier S0 est lentre: une liste trier S est la sortie: le reste de S0 aprs que les premiers N lments sont tris Xs est la liste trie des premiers N lments de S0 La paire (S0,S) est un accumulateur La dfinition utilise une syntaxe de procdure parce quelle a deux sorties, S et Xs 2007 P. Van Roy. All rights reserved. 48

Un autre exemple (2) fun {Mergesort Xs} Ys in {Mergesort1 {Length Xs} Xs _ Ys} Ys end proc {Mergesort1 N S0 S Xs} if N==0 then S=S0 Xs=nil elseif N==1 then case S0 of X|S1 then S=S1 Xs=[X] end else S1 Xs1 Xs2 NL NR in NL=N div 2 NR=N-NL {Mergesort1 NL S0 S1 Xs1} {Mergesort1 NR S1 S Xs2} Xs={Merge Xs1 Xs2} end end 2007 P. Van Roy. All rights reserved.

49 Rsum 2007 P. Van Roy. All rights reserved. 50 Rsum Techniques de programmation Algorithme de Mergesort

Utilisation dune variable non-lie pour construire une liste avec lappel rcursif en dernier Utilisation dun accumulateur pour augmenter lefficacit Utilisation dun type pour construire une fonction Exemple de diviser pour rgner Programmer avec plusieurs accumulateurs Programmer avec un tat qui est pass partout dans un programme Exemple dun compilateur pour machine pile 2007 P. Van Roy. All rights reserved. 51

Recently Viewed Presentations

  • Rotary International Global Grant Scholarships

    Rotary International Global Grant Scholarships

    Rotary International Global Grant Scholarships. ... District 5300 plans to offer up to two Rotary Scholarships through Global Grants for the 2014-2015 year. Each scholarship is a global grant project with a minimum budget of $30,000. The scholarship period can...
  • Practical Skills in Grant Writing ... - University of Florida

    Practical Skills in Grant Writing ... - University of Florida

    UF Clinical and Translational Science Institute KL2 Program K Writer's Workshop October 9, 2015
  • The sea is rarely still—row upon row of waves roll across its ...

    The sea is rarely still—row upon row of waves roll across its ...

    The sea is rarely still—row upon row of waves roll across its surface, seemingly endless and eternal. At turns soothing, exhilarating, and terrifying, waves carry the power and the beauty of the sea and let them loose upon the shore....
  • Mother Teresa - THE KV POWER POINT

    Mother Teresa - THE KV POWER POINT

    Mother Teresa -AGNES OR ANGEL Mother in prayer AND SERVICE Service to man is service to GOD Noble peace prize BHARAT RATNA FROM GOVT OF INDIA MOTHER PASSESS AWAY -1997 Mother Teresa -AGNES OR ANGEL Mother in prayer AND SERVICE...
  • Maybe youre one of those kids that have

    Maybe youre one of those kids that have

    Maybe you're one of those kids that have dropped over dead converting metrics. Here are two simple ways that will help you. First, draw a staircase.
  • Diapositive 1

    Diapositive 1

    LIN1720 Cours 15: Prosodie Dr Hélène Knoerr ILOB Université d'Ottawa * La partie de la phonologie qui s'occupe des phonèmes est la phonématique étudie les unités distinctives segmentales L'autre branche de la phonologie s'occupe de la prosodie étudie les traits...
  • ANSI TIA EIA 570 - godinweb

    ANSI TIA EIA 570 - godinweb

    Source: ANSI-TIA-EIA-570 Standard Cable Pathways Efforts should be made to conceal the cabling within the walls of the building especially in new construction and remodeling.
  • Debt, Deficits and Unemployment By Ken Schultz Discussants:

    Debt, Deficits and Unemployment By Ken Schultz Discussants:

    Modern Money Theory. Basic Principles of Macro Accounting. University of Massachusetts Study about Debt Ratio's and Growth. ... A 2010 study conducted by Ken Rogoff and Chairman Reinhart showed that growth slowed dramatically when the GDP to debt ratio exceeded...