Logica s, i structuri discrete

RecursivitateMarius Minea

marius@cs.upt.ro

http://cs.upt.ro/˜marius/curs/lsd/

2 octombrie 2017

Recapitulare

Am revazut: funct, ii (injective, surjective, bijective, inversabile)Am definit funct, ii ıntr-un limbaj de programare funct, ional.

Domeniul s, i codomeniul sunt tipuri ın limbajele de programare.

Tipurile ne spun pe ce fel de valori poate fi folosita o funct, ielet comp g f x = g (f x)val comp: (’a -> ’b) -> (’c -> ’a) -> ’c -> ’b = <fun>f are tipul ’c -> ’a s, i g are tipul ’a -> ’b⇒ domeniul de valori al lui f e domeniul de definit, ie al lui gcompunerea are tipul ’c -> ’b ’a, ’b, ’c pot fi orice tip

Funct, iile pot avea ca argumente s, i/sau rezultat alte funct, ii

Compunand funct, ii (g ◦ f ) rezolvam probleme mai complexe:f produce un rezultat, g ıl foloses, te mai departe

Ce putem face pana acum

Putem defini funct, ii simple:let max x y = if x > y then x else y

e de fapt predefinita, nu e nevoie s-o definim ınca o data

Putem compune de un numar dat de ori (numar fix de argumente)let max x1 x2 x3 = max x1 (max x2 x3)let max x1 x2 x3 x4 = max x1 (max x2 (max x3 x4))

Nu putem ınca:exprima ca vrem sa lucram cu N valori (lista, mult, ime, tablou)defini un calcul pentru un numar arbitrar de valori

Recursivitate

Recursivitatea e fundamentala ın informatica:daca o problema are solut, ie, se poate rezolva recursivreducand problema la un caz mai simplu al aceleias, i probleme

⇒ ınt, elegand recursivitatea, putem rezolva orice problema(daca e fezabila)

Def.:O not, iune e recursiva daca e folosita ın propria sa definit, ie.

Calculul expresilor aritmetice

O expresie (put, in mai) complicata:(2 + 3) ∗ (4 + 2 ∗ 3)− 5 ∗ 6/(7− 2) + (4 + 3− 2)/(7− 3)

Pentru a calcula, trebuie sa ınt, elegem structura expresiei(nu se vede tot timpul us, or ıntr-un s, ir de caractere)

E suma a doua subexpresii (+ e calculat ultimul):

(2 + 3) ∗ (4 + 2 ∗ 3)− 5 ∗ 6/(7− 2)+ (4 + 3− 2)/(7− 3)

Apoi calculam expresiile mai simple(2 + 3) ∗ (4 + 2 ∗ 3) – 5 ∗ 6/(7− 2) = 44(4 + 3− 2) / (7− 3) = 144 + 1 = 45

Calculul celor doua subexpresii: dupa aceleas, i reguli

Pas, i ın rezolvarea problemei

Ce ne-a permis sa calculam expresia complicata?

I Identificarea structurii recursiveexpresia e suma a doua expresii mai simplevom folosi tipuri de date definite recursiv

I Exprimam pas, ii de calcul elementari (cei mai simpli)putem aduna, ımpart, i, etc. doua numere

I Identificam condit, ia de oprirecand expresia e un simplu numar, nu mai trebuie facut nimic

Expresia ca not, iune recursiva

Ce e o expresie numerica?int + int 5 + 2int – int 2− 3int * int -1 * 4int / int 7 / 3

Se poate mai simplu? Da: int (5 e caz particular de expresie)

Se poate s, i mai complicat? Da:int * (int + int)(int - int) / int...

Putem scrie un numar finit de reguli ?

Expresia, definita recursiv

O expresie:

ıntregexpresie + expresieexpresie - expresieexpresie * expresieexpresie / expresie

Am descris expresia printr-o gramatica (nis, te reguli de scriere):as, a se descriu limbajele de programare

detalii despre gramatici ıntr-un alt cursurmarit, i diagramele de sintaxa la cursul de programare

ISO/IEC 9899:201x Committee Draft — April 12, 2011 N1570

5 EXAMPLE 2 In the program fragment

char *s;/* ... */while (*s++ != '\0')

;

a null statement is used to supply an empty loop body to the iteration statement.

6 EXAMPLE 3 A null statement may also be used to carry a label just before the closing } of a compoundstatement.

while (loop1) {/* ... */while (loop2) {

/* ... */if (want_out)

goto end_loop1;/* ... */

}/* ... */

end_loop1: ;}

Forward references: iteration statements (6.8.5).

6.8.4 Selection statementsSyntax

1 selection-statement:if ( expression ) statementif ( expression ) statement else statementswitch ( expression ) statement

Semantics

2 A selection statement selects among a set of statements depending on the value of acontrolling expression.

3 A selection statement is a block whose scope is a strict subset of the scope of itsenclosing block. Each associated substatement is also a block whose scope is a strictsubset of the scope of the selection statement.

6.8.4.1 The if statement

Constraints

1 The controlling expression of an if statement shall have scalar type.

Semantics

2 In both forms, the first substatement is executed if the expression compares unequal to 0.In the else form, the second substatement is executed if the expression compares equal

148 Language §6.8.4.1

O problema nerezolvata: “problema 3 · n + 1”

Fie un numar pozitiv n:daca e par, ıl ımpart, im la 2: n/2daca e impar, ıl ınmult, im cu 3 s, i adunam 1: 3 · n + 1

f (n) ={

n/2 daca n ≡ 0 mod 23 · n + 1 altfel (daca n ≡ 1 mod 2)

Se ajunge la 1 pornind de la orice numar pozitiv ?

= Conjectura lui Collatz (1937), cunoscuta sub multe alte nume

Exemple:3→10→5→16→8→4→2→111→34→17→52→26→13→40→20→10→5→16→8→4→2→1

Cat, i pas, i pana la oprire?

Definim funct, ia p : N∗ → N care numara pas, ii pana la oprire:pentru 3→10→5→16→8→4→2→1 avem 7 pas, i

Nu avem o formula cu care sa definim p(n) direct.

Dar daca s, irul n, f (n), f (f (n)), . . . ajunge la 1,atunci numarul de pas, i parcurs, i de la n (mai sus: 3)e cu unul mai mare decat continuand de la f (n) (aici: 10)

p(n) ={

0 daca n = 1 (am ajuns)1 + p(f (n)) altfel (daca n > 1)

Funct, ia p a fost definita recursiv: e folosita ın propria definit, ie

Problema 3 · n + 1 ın ML

let f n = if n mod 2 = 0 then n / 2 else 3 * n + 1

Revedem: if c then e1 else e2 e o expresie condit, ionaladaca c e adevarata, are valoarea lui e1, altfel valoarea lui e2

let rec p n = if n = 1 then 0 else 1 + p (f n)

Cuvintele cheie let rec introduc o definit, ie recursiva:funct, ia p e folosita (apelata) ın propria definit, ie

Fara rec, fie p din dreapta ar fi necunoscut (eroare), fie s-ar folosio eventuala definit, ie anterioara (deci nu ar fi recursiva).

Mecanismul apelului recursiv

In interpretor, vizualizam apelurile s, i revenirea cu directiva#trace numefunct, ierevenim la normal cu #untrace numefunct, ie

In calculul recursiv:

Fiecare apel face “ın cascada” un nou apel, pana la cazul de baza

Fiecare apel executa acelas, i cod, dar cu alte date(valori proprii pentru parametri)

Ajuns, i la cazul de baza, toate apelurile facute sunt ınca neterminate(fiecare mai are de facut adunarea cu rezultatul apelului efectuat)

Revenirea se face ın ordine inversa apelarii(ultimul apelul revine primul, apoi revine penultimul apel, etc.)

Sintaxa: Potrivirea de tipare

Putem scrie funct, ia s, i as, a:let rec p = function

| 1 -> 0| n -> 1 + p (f n)

Sageata sugereaza funct, ia definita ca diagrama. Citim astfel:p e o funct, ie:

– daca argumentul e 1, valoarea funct, iei e 0– daca argumentul are orice alta valoare (o notam n), valoarea

funct, iei e 1 + p (f n)

Cuvintele cheie fun s, i function se folosesc diferit!cu fun x1 x2 ... -> expresie putem scrie orice funct, ie

cu oricat, i parametri x1, x2 ...

cu function definim o funct, ie prin potrivire de tipare,cu un parametru implicit (NU scriem let p n = ...)

Fiecare ramura defines, te ın stanga lui -> un tipar s, i ın dreaptarezultatul (putem folosi numele introduse ın tiparul din stanga)

Potrivirea de tipare (cont.)Argumentul implicit care e potrivit cu tiparul poate fi:

o constanta (aici, 1)o valoare structurata (pereche, lista cu cap/coada, etc.)

perechile se noteaza (x, y) ca ın matematicatriplete: (a, b, c), etc

un identificator (nume) care indica tot argumentul (oricare ar fi)Nu putem avea ca tipar (doar) o condit, ie x > 5

Potrivirile se ıncearca ın ordinea indicata, pana la prima reus, ita.

Identificatorul special _ (linie de subliniere) se potrives, te cu oriceIl folosim daca nu avem nevoie de valoarea respectiva.

let pozitie = function| (0, 0) -> print_string "origine"| (_, 0) -> print_string "pe axa x"| (0, y) -> Printf.printf "pe axa y la %d" y| (_, _) -> print_string "nu e pe axe"

Potrivirea de tipare: exemple

Ex.: o funct, ie care ia triplete de ıntregi s, i da suma componentelorpana la primul zero.

let sumto0 = function| (0, _, _) -> 0| (x, 0, _) -> x| (x, y, z) -> x + y + z

daca prima componenta e 0, rezultatul e 0, indiferent de celelaltealtfel, daca a doua componenta e 0, adunam doar prima (nu s, i a treia)altfel, primele doua sunt nenule, s, i le sumam pe toate trei

Daca am uitat un tipar posibil, compilatorul ne avertizeaza.

Rescriere echivalenta cu if-then-else:

let sumto0 (x, y, z) =if x = 0 then 0 else if y = 0 then x else x + y + z

Sintaxa: Definit, ii localePana acum: definit, ii globale: let identificator = expresie

let fct arg1 ... argN = expresieUneori sunt utile definit, ii auxiliare. Am vrea sa scriem:Definim funct, ia arie(a, b, c) astfel: (a, b, c = laturile triunghiului)

ıntai definim p = (a + b + c)/2cu aceasta notat, ie, aria e

√p(p − a)(p − b)(p − c)

let arie a b c = (* traducem in ML *)let p = (a +. b +. c) /. 2. insqrt (p *. (p -. a) *. (p -. b) *. (p -. c))

Definit, ia e tot de forma let funct, ie arg1 ... argN = expresiedar expresie are noua forma: let id aux = expr aux in expr valExpresia are valoarea lui expr val,

√p(p − a)(p − b)(p − c), unde

id aux (p) din stanga lui = are sensul din dreapta, p =(a+b+c)/2.

Astfel dam un nume, p, pentru o expresie folosita de mai multe ori,(a + b + c)/2, scriind mai concis s, i evitand recalcularea.

S, iruri recurente

progresie aritmetica:{x0 = b (adica: xn = b pentru n = 0)xn = xn−1 + r pentru n > 0

Exemplu: 1, 4, 7, 10, 13, . . . (b = 1, r = 3)

progresie geometrica:{x0 = b (adica: xn = b pentru n = 0)xn = xn−1 · r pentru n > 0

Exemplu: 3, 6, 12, 24, 48, . . . (b = 3, r = 2)

Definit, iile de mai sus nu calculeaza xn direct (des, i se poate)ci din aproape ın aproape, folosind xn−1.

s, irul xn e folosit ın propria definit, ie ⇒ recursivitate / recurent, a

Programam: progresia aritmetica

Scriem ıntai o progresie aritmetica cu baza s, i rat, ia fixate:x0 = 3, xn = xn−1 + 2 (pentru n > 0)

Not, iunea recursiva (s, irul) devine o funct, ieValoarea de care depinde (indicele) devine argumentul funct, iei

let rec aritpr_3_2 = function| 0 -> 3| n -> 2 + aritpr_3_2 (n-1)

sau, echivalent

let rec aritpr_3_2 n =if n = 0 then 3 else 2 + aritpr_3_2 (n-1)

Cum parametrizam funct, ia cu baza s, i rat, ie ?

Exemplu: generalizam progresia aritmetica

Putem scrie o funct, ie care are baza s, i rat, ia ca parametri:let rec aritpr baza ratie = function (* mai ia un indice *)| 0 -> baza| n -> ratie + aritpr baza ratie (n-1)

sau echivalentlet rec aritpr baza ratie n =

if n = 0 then baza else ratie + aritpr baza ratie (n-1)

Putem defini apoi funct, ii care corespund unor progresii individuale:let aritpr_3_2 = aritpr 3 2 (* baza 3, ratia 2 *)# aritpr_3_2 4- : int = 11 (* termenul de indice 4 *)

Rescriem cu definit, ii localelet rec aritpr baza ratie = function| 0 -> baza| n -> ratie + aritpr baza ratie (n-1)

Apare de doua ori expresia aritpr baza ratie , o funct, ie de unargument (indicele), ın care baza s, i ratie sunt deja fixate.Rescriem dand un nume ap1pentru expresia comuna(definit, ie locala pentru ap1)In exterior definim funct, ia init, ialaaritpr baza rat, ie egala cu ap1

let aritpr baza ratie =let rec ap1 = function

| 0 -> baza| n -> ratie + ap1 (n-1)

in ap1

Citim: let (fie) aritpr baza ratie definita astfel:– definim funct, ia ap1 (folosind parametrii lui aritpr: baza, ratie;

ap1 ia indicele n s, i da valoarea termenului al n-lea)– atunci aritpr baza ratie e chiar ap1 (expresia de dupa in)

ap1 are rol ajutator, nu e vizibil ın afara definit, iei lui aritpr

Recursivitate: exemple

Recursivitatea e fundamentala ın informatica:reduce o problema la un caz mai simplu al aceleias, i probleme

obiecte: un s, ir e{

un singur element © s, irun element urmat de un s, ir ©

︷ ︸︸ ︷©©©

ex. cuvant (s, ir de litere); numar (s, ir de cifre zecimale)

act, iuni: un drum e{un pas −→ drumun drum urmat de un pas ︷ ︸︸ ︷−→−→−→ −→

ex. parcurgerea unei cai ıntr-un graf

Tipuri recursivePentru a reprezenta structura recursiva a unei probleme, ne trebuieadesea date definite recursiv. In ML putem construi tipuri recursive.

Un tip recursiv pentru expresii (incluzand operatorii de calcul):

type expr = I of int| Add of expr * expr | Sub of expr * expr| Mul of expr * expr | Div of expr * expr

Am definit un tip cu mai multe variante.Fiecare din ele trebuie scrisa cu un constructor de tip (eticheta),ales de noi: I, Add, etc. (orice identificator cu litera mare)

Notat, ia expr * expr reprezinta produsul cartezian,deci o pereche de doua valori de tipul expr

Tipul expr e recursiv (o valoare de tip expresie poate cont, ine larandul ei componente de tip expresie)

Expresia (2 + 3) * 7 se reprezinta: Mul (Add(I 2, I 3), I 7)

Evaluarea recursiva a unei expresii

Lucrul cu o valoare de tip recursiv se face prin potrivire de tipare(engl. pattern matching), pentru fiecare varianta din tip

let rec eval = function| I i -> i| Add (e1, e2) -> eval e1 + eval e2| Sub (e1, e2) -> eval e1 - eval e2| Mul (e1, e2) -> eval e1 * eval e2| Div (e1, e2) -> eval e1 / eval e2

Evaluand expresia eval (Mul (Add(I 2, I 3), I 7)) da 35.e nevoie de paranteze, pentru a grupa Mul s, i perechea de dupa

Pentru tipuri definite recursivfunct, iile care ıl prelucreaza vor fi natural recursivedeobicei cu cate un caz pentru fiecare varianta a tipului respectiv

Elementele unei definit, ii recursive

1. Cazul de baza (NU necesita apel recursiv)= cel mai simplu caz pentru definit, ia (not, iunea) data, definit direct

termenul init, ial dintr-un s, ir recurent: x0un element, ın definit, ia: s, ir = element sau s, ir + element

E o EROARE daca lipses, te cazul de baza (apel recursiv infinit!)

2. Relat, ia de recurent, a propriu-zisa– defines, te not, iunea, folosind un caz mai simplu al aceleias, i not, iuni

3. Demonstrat, ie de oprire a recursivitat, ii dupa numar finit de pas, i(ex. o marime nenegativa care descres, te cand aplicam definit, ia)– la s, iruri recurente: indicele (≥ 0 dar mai mic ın corpul definit, iei)– la obiecte: dimensiunea (definim obiectul prin alt obiect mai mic)

Sunt recursive, s, i corecte, urmatoarele definit, ii ?

? xn+1 = 2 · xn? xn = xn+1 − 3? an = a · a · . . . · a (de n ori)? o fraza e o ıns, iruire de cuvinte? un s, ir e un s, ir mai mic urmat de un alt s, ir mai mic? un s, ir e un caracter urmat de un s, ir

O definit, ie recursiva trebuie sa fie bine formata (v. condit, iile 1-3)ceva nu se poate defini doar ın funct, ie de sine ınsus, ise pot utiliza doar not, iuni deja definitenu se poate genera un calcul infinit (trebuie sa se opreasca)

De s, tiut

Sa recunoas, tem s, i definim not, iuni recursive

Sa recunoas, tem daca o definit, ie recursiva e corecta(are caz de baza? se opres, te recursivitatea?)

Sa rezolvam probleme scriind funct, ii recursivecazul de baza + pasul de reducere la o problema mai simpla

Sa definim s, i folosim tipuri recursive

Fractali (opt, ional)

Figuri geometrice ın care o parte a figurii e similara ıntreguluiacesta e aspectul recursiv

Apar ın natura, sau pot simula artificial figuri din natura

Analiza lor are aplicat, ii ın diverse domenii: geografie/geologie,medicina, prelucrarea semnalelor, electrotehnica (microantene), etc.

Exemple simple de fractali

Imagine: http://mathworld.wolfram.com/Fractal.html

Generarea recursiva a unui fractal

Scriem o funct, ie pentru not, iunea recursiva (figura)

Punctul cheie: funct, ia recursiva e figura (nu: triunghi, patrat, etc.)acestea sunt doar cazurile de baza

Caracteristicile figurii devin parametrii funct, ieidimensiunea, pozit, ia (coordonatele), orientarea, etc.

Apelul funct, iei va desena figura(sau va produce comenzile de desenare)

Desene simple ın format vectorial

SVG = Scalable Vector Graphics:un format de imagine bazat pe XMLare un cadru standard, specificand ca e ın format SVGs, i comenzile de desenare propriu-zise

Comenzi simple:m x y (moveto): muta punctul curent

l x y (lineto): deseneaza linie din punctul curent ın cel indicat

versiuni cu coordonate absolute (M, L) s, i relative (m, l)

caz particular:h x linie orizontala (de lungime x)v y linie verticala (de lungime y)

Scrierea/tiparirea ın OCaml

Funct, ii dedicate pentru fiecare tip:print_int, print_float, print_string etc.

print_int 5print_float 3.4

Funct, ia de tiparire formatata Printf.printf (asemanator cu C)Daca o folosim des, deschidem modulul Printf s, i scriem simplu:

open Printfprintf "un intreg: %d\n" 5printf "un real %f si inca unul: %f\n" 2.3 4.7

Putem defini atunci:let lineto x y = printf "l %.2f %.2f" x y(tipares, te coordonatele cu doua zecimale)sau mai simplu: let lineto = printf "l %.2f %.2f"