Algoritmi si programare (AP)

Dorel Lucanuhttp://www.infoiasi.ro/~dlucanu/

Dorel Lucanu Algoritmica si programare

Obiective

Algoritmi: însuşirea unei gândiri algoritmicedezvoltarea abilitaţilor de proiectare de soluţii algoritmice însuşirea tehnicilor de utilizare a

principalelor structuri de date evaluarea timpului de execuţie in cazul cel mai nefavorabil

Programare iniţiere în utilizarea unui limbaj de programaredescrierea principalelor structuri de dateînsuşirea tehnicilor de bază în proiectarea programelor

Dorel Lucanu Algoritmica si programare

Agenda disciplina

AlgoritmiLimbaj algoritmic, tablouri, structuri statice, structuri înlănţuiteliste liniarearbori binari, heap-uri, union-findgrafuri (ca structuri de date)sortare, căutareparadigme

Programareprezentarea graduata a limbajului C (ISO Standard) cu accent pe implementareastructurilor de date si a soluţiilor prezentatein prima parte

Dorel Lucanu Algoritmica si programare

Evaluare

conditiiactivitatea la seminar (AS)activitatea la laborator (AL)testele scrise (TS)

criterii de promovareAS ≥ 5, AL ≥ 6, TS ≥ 4

formeAS: întrebări, participare la discuţii, soluţii

originaleAL: fiecare tema de laborator va fi notata cu note de la 1 la 10 TS: 2 teste scrise (săpt. 7,13), fiecare test conţinând 8 întrebări grilă şi o problemă.

Dorel Lucanu Algoritmica si programare

Nota finala

normele ECTS (European Credit Transfer System)Punctaj Final (PF) = 10% AS + 40% AL +50% TS≤ 4 daca sunt indeplinite conditiile si NU sunt indeplinite criteriile de promovare,= 10 daca PF este in primii 10% din cei promovati (A)= 9 urmatorii 25% din cei promovati (B)= 8 urmatorii 30% din cei promovati (C)= 7 urmatorii 25% din cei promovati (D)= 6 urmatorii 10% din cei promovati (D)= 5 daca criteriile nu sunt indeplinite cu o eroare de 3% si activitatea generala justifica totusi o promovare la limita (max 5% din cei promovati)

Dorel Lucanu Algoritmica si programare

Bibliografie

T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introducere in Algoritmi, Computer LibrisAgora, 2000Herbert Schildt: C Manual Complet, Bucuresti, Ed. Teora, 1998resurse electronice

a se consulta pagina cursuluihttp://thor.info.uaic.ro/~dlucanu/ap/ap.html

Dorel Lucanu Algoritmica si programare

Curs 1 - Agenda

limbaj algoritmictablouristructuricalculul unui programproblema rezolvata de un programtimpul de executie

Dorel Lucanu Algoritmica si programare

Algoritm

algoritm = o secventa finita de pasi aranjataintr-o ordine logica specifica cu proprietatea ca, atunci cand este executata, produce o solutiecorecta la o problema data.exemplu: reteta culinara

algoritm calculator (“computer algorithm”) = un algoritm pentru care secventa de pasi esteexecutata de un calculator

limbaj algoritmic = un limbaj cu care suntdescrisi algoritmii

Dorel Lucanu Algoritmica si programare

Tip de date: definitii

tip de date = colectie de entitati de tip data (obiecte reprezentabile in memoriacalculatorului) si un set de operatii pesteaceste obiecte

tip de date abstract = tip de data organizatin asa fel incat specificarea obiectelor sispecificarea operatiilor este independenta de reprezentarea obiectelor si implementareaoperatiilor

model standard = model utilizat pentruspecificarea tipurilor de data abstracte (bazatpe notatii matematice)

Dorel Lucanu Algoritmica si programare

Tip de date abstract: exemple

INTobiecte: int = {. . . –2, –1, 0, 1, 2, . . . }operatii:

adunareaintrare: a, b ∈ intiesire: a + b

. . .BOOL

obiecte: bool = {false, true}operatii:

conjunctiaintrare: a, b ∈ booliesire: a ∧ b (a and b)

. . .

Dorel Lucanu Algoritmica si programare

Limbaj algoritmic

modelarea memorieitipuri de date elementareinstructiunitipuri de date structurate de nivel joscalcultimpul de executie

Dorel Lucanu Algoritmica si programare

variabila = (nume, atribute, adresa)

Modelarea memoriei

xadr

int

*p int

p int*

adradr

pointer

Dorel Lucanu Algoritmica si programare

notatia grafica scurta

Modelarea memoriei

xadr

int

adr

*p int

p int*adr

Dorel Lucanu Algoritmica si programare

Tipuri de date elementare

numere intreginumere rationalevalori booleenepointeri...

Dorel Lucanu Algoritmica si programare

Atribuirea

sintaxa⟨variabila⟩ ← ⟨expresie⟩

latura ← 217lung_drum ← sqrt(5.0)*latura

latura int

lung_drum real

217sqrt(5.0)*217485.2267

Dorel Lucanu Algoritmica si programare

Atribuirea

Cazul pointerilor*p ← 147

adr

*p int

p int*adr

147

Dorel Lucanu Algoritmica si programare

if

sintaxaif ⟨expresie⟩then ⟨secventa_instructiuni⟩else ⟨secventa_instructiuni⟩

semanticaif ethen i1else i2

1. se evalueaza e2. daca rezultatul este adevarat atunci executa

i1altfel executa i2

Dorel Lucanu Algoritmica si programare

if - exemple

calcululul min(a,b) - varianta 1if (a < b)then min ← aelse min ← b

calcululul min(a,b) - varianta 1min ← aif (b < a) then min ← b

Dorel Lucanu Algoritmica si programare

while

sintaxawhile (⟨expresie⟩) do

⟨secventa_instructiuni⟩semanticawhile (e) do

i1...ik

1. se evalueaza e2. daca rezultatul este adevarat

a) se executa instructiunile i1, ..., ikb) se reia procesul de la pasul 1

3. altfel, executia instructiunii while se termina

Dorel Lucanu Algoritmica si programare

while - exemple

cel mai mic k a.i. 7k ≥ n pentru un n datk ← 0sapte_la_k ← 1while (sapte_la_k < n) do

k ← k+1sapte_la_k ← sapte_la_k * 7

Dorel Lucanu Algoritmica si programare

repeat

sintaxarepeat

⟨secventa_instructiuni⟩until ⟨expresie⟩

semanticarepeat

i1...ik

until (e)1. se executa instructiunile i1, ..., ik2. se evalueaza e3. daca rezultatul este fals, se reia procesul

de la pasul 14. altfel, executia instructiunii repeat se

termina

Dorel Lucanu Algoritmica si programare

repeat - exemple

7k - inlocuirea lui while cu repeat k ← 0sapte_la_k ← 1repeat

k ← k+1sapte_la_k ← sapte_la_k * 7

until (sapte_la_k ≥ n)

pentru n = 0 nu mai obtinem rezultatul corect

Dorel Lucanu Algoritmica si programare

for – versiunea 1

sintaxafor ⟨variabila⟩ ← ⟨expresie1⟩ to ⟨expresie2⟩ do

⟨secventa_instructiuni⟩semantica

for i ← e1 to e2 doi1...ik

i ← e1while (i <= e2) doi1...iki ← succ(i)

Dorel Lucanu Algoritmica si programare

for - exemple

Exemplu: s = 1 + 2 + ... + ns ← 0for i ← 1 to n do

s ← s + i Exemplu: a = 2k

a ← 1for i ← 1 to k do

a ← a * 2

Dorel Lucanu Algoritmica si programare

for – versiunea 2

for ⟨variabila⟩ ← ⟨expresie1⟩ downto ⟨expresie2⟩ do⟨secventa_instructiuni⟩

semantica

for i ← e1 downto e2 doi1...ik

i ← e1while (i >= e2) do

i1...iki ← pred(i)

Dorel Lucanu Algoritmica si programare

for - exemple

Exemplu: s = n + n-1 + ... + 1s ← 0for i ← n downto 1 do

s ← s + i

Dorel Lucanu Algoritmica si programare

Subprograme - proceduri

sintaxaprocedure ⟨nume⟩(⟨parametri⟩)

⟨secventa_instructiuni⟩end

clasificarea parametrilor:de intrarede iesirede intrare/iesire

Dorel Lucanu Algoritmica si programare

Subprograme - exemple

interschimbarea valorilor a doua variabileprocedure swap (a, b)temp ← aa ← bb ← temp

endutilizarex ← 7y ← 23swap(x,y)// x = 23, y =7

Dorel Lucanu Algoritmica si programare

Subprograme - functii

sintaxafunction ⟨nume⟩(⟨parametri⟩)

⟨secventa_instructiuni⟩return ⟨expresie⟩

endpot exista mai multe instructiuni return

Dorel Lucanu Algoritmica si programare

Subprograme - exemple

functia care intoarce sumafunction suma(n)

s ← 0for i ← 1 to n do

s ← s + ireturn s

endutilizarev ← suma(m) – m/2

Dorel Lucanu Algoritmica si programare

Exceptii

sintaxathrow ⟨mesaj⟩if ⟨expresie⟩ then throw ⟨mesaj⟩

exempluif (b = 0) then throw “impartire prin 0”x ← a/b

Dorel Lucanu Algoritmica si programare

Calculul unui program

x ← 1i ← 2while (i < 4) do

x ← X*ii ← i+1

fiecare instructiune= o unitate de timptimpul de executieT = 9

32i < 46

21i < 43

46i < 49

36i ← i+18

32x ← x*i7

22i ← i+15

21x ← x*i4

-1i ← 22

--x ← 11

ixInstruct./exppas

Dorel Lucanu Algoritmica si programare

Calculul unui program

linie in tabel = configuratie (c)obtinerea unei linii din precedenta = relatie de tranzitie: ci-1 → ci

calculfinit: c0 → c1 → c2 →… → cn

infinit: c0 → c1 → c2 →…problema

(intrare, iesire)un caz particular de intrare se numeste instanta

calcul generat de instantao instanta det. c0 si c0 det. unic un calcul

problema rezolvata de un programcalculul generat de c0 este finitconfiguratia finala cn contine iesirea

Dorel Lucanu Algoritmica si programare

Tablouri

a int[3]

a[0] int

a[1] int

a[2] int

a[1] ← 7a[2] ← a[1] * 2

int a[3]

7 14

Dorel Lucanu Algoritmica si programare

Tablouri - exemple

suma primelor n elemente dintr-un tablous ← 0for i ← 0 to n-1 do

s ← s + a[i]cautarea unui element x intr-un tablou

i ← 0while (i < n-1 and a[i] != x) do

i ← i + 1if (a[i] = x)then poz ← ielse poz ← -1

Dorel Lucanu Algoritmica si programare

Structuri statice (articole)

d data

d.zi 1..31

d.ln 1..12

d.an int

data calendaristica: zi, luna, an

d.ln ← 11d.zi ← 6d.an ← 2004

116 2004

Dorel Lucanu Algoritmica si programare

Structuri si pointeri

*pd data

p->zi 1..31

p->ln 1..12

p->an int

pd data*

Dorel Lucanu Algoritmica si programare

Liste simplu inlantuite

un nod v este o structura cu doua campuri:v.inf - memoreaza informatia din nodv.succ – adresa nodului urmatoro lista este identificata de 2 pointeri: prim siultimla un moment dat se proceseaza nodul curentoperatii: inserare/eliminare noduri, parcurgere

e0 ei en-1…

prim

curent

ultim

…

Dorel Lucanu Algoritmica si programare

Timpul de executie in cazul cel mai nefavorabil

i ← 0while (i < n-1 and a[i] != x) do

i ← i + 1if (a[i] = x)then poz ← ielse poz ← -1a = (4, 1, 5, 9, 6)daca x = 4, atunci T = 1 + 1 + 2 = 4 (cel maifavorabil)daca x = 6 sau x = 3, atunciT = 1 + 4*2 + 2 = 11 (cel mai nefavorabil)in general: T(n) = 1 + 2*(n-1) + 2 = 2*n+1 n – dimensiunea instantei problemei

Dorel Lucanu Algoritmica si programare

Notatia O(f(n))

functii f(n) de argument numar natural si valorinumere reale pozitiveO(f(n)) = clasa functiilor marginite superior de f(n)

g(n) ∈ O(f(n)) daca exista c > 0, n0 a.i.g(n) <= c*f(n) pentru orice n >= n0

functiile constante ∈ O(1)polinoamele de grad 1 ∈ O(n) polinoamele de grad 2 ∈ O(n2)functii logaritmice ∈ O(log n)

Pentru cautarea in tablou: T(n) = O(n)notatie: T(n) = O(n) in loc de T(n) ∈ O(n)