Erdélyi Magyar TudományEgyetem (EMTE

Sapientia - Erdélyi Magyar TudományEgyetem (EMTE) Csíkszereda IRT- 3. kurzus

TARTALOM: • Általánosságok • Algoritmusok ábrázolása: – Matematikai-logikai nyelvezet – Pszeudokód – Függőleges logikai sémák – Vízszintes logikai sémák – Fastruktúrák – Döntési táblák 1


Általánosságok 1. Algoritmizálunk a következő esetekben:  számítás volumene nagy  az aktivitás sokszor ismétlődik  az eredmények rövid időn belül szükségesek 2. A hangsúly azon van hogy ábrázoljuk és hogy építjük fel az algoritmust egy valós és nehéz probléma megoldásának érdekében 3. A legjobb algoritmus ? 4. A komplexitás időben csökkenő? 2

Algoritmusok elemzése Előre megadjuk, hogy milyen erőforrásokra lesz szüksége az algoritmusnak. A RAM (Random Access Memory)-közvetlen hozzáférésű memóriát vesszük alapul. A Processzorral együtt alkotja a közvetlen hozzáférésű gépet. Az utasítások egymás után hajtódnak végre, egyidejű műveletek nélkül. Meg kell fogalmazzuk a modell műveleteit és azok költségeit. Bemenet mérete: feladatfüggő • a tömb n elemszáma (rendezésnél) • Bitek száma (pl. számok szorzása esetén) • Gráf éleinek és csúcsainak száma Futási idő: egy bizonyos bemenetre a végrehajtott alapműveletek (lépések száma) 3

Beszúrásos rendezés algoritmusa 1

2

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

5

2

4

6

1

3

2

5

4

6

1

3

2

4

5

6

1

3

1

2

3

4

5

6

1

2

3

4

5

6

1

2

3

4

5

6

2

4

5

6

1

3

1

2

4

5

6

3

1

2

3

4

5

6

Költség végrehajtási szám

1 for j←2 to hossz[A] 2 do S←A[j] 3 ((A[j] beszúrása az A[1..j-1] rendezett sorba)) 4 i←j-1 5 while i>0 and A[i]>S 6 do A[i+1]←A[i] 7 i←i-1 8 A[i+1]←S n tj ahányszor 5-ös végrehajtódik a j-re

t j 2

C1 C2

n n-1

C4 C5 C6 C7 C8

n-1 n

 (t j 2

j

 1)

n-1

j 4

Legjobb eset 1

2

3

4

5

6

1

2

3

4

5

6

A 6-os és 7-es utasítás NEM hajtódik végre, az 5-ös feltétel nem teljesülése miatt, viszont az 5ös feltételt ellenőrzi minden ciklusban a program

T(n)=c1n+c2(n-1)+c4(n-1)+c5(n-1)+c8(n-1)=an+b lineáris függvény

1 for j←2 to hossz[A] 2 do S←A[j] 3 ((A[j] beszúrása az A[1..j-1] rendezett sorba)) 4 i←j-1 5 while i>0 és A[i]>S 6 do A[i+1]←A[i] 7 i←i-1 8 A[i+1]←S


C1 C2

n n-1

C4 C5 C6 C7 C8

n-1 n-1

n-1 5

Legroszabb eset 1

2

3

4

5

6

6

5

4

3

2

1

T(n)=an2+bn+c

négyzetes függvény

1 for j←2 to hossz[A] 2 do S←A[j] 3 ((A[j] beszúrása az A[1..j-1] rendezett sorba)) 4 i←j-1 5 while i>0 and A[i]>S 6 do A[i+1]←A[i] 7 i←i-1 8 A[i+1]←S


C1 C2

n n-1

C4 C5 C6 C7 C8

n-1 n-1 (n-1)*(n-1) (n-1)*(n-1) n-1

T(n)=c1n+(c2+c4+c5+c8)(n-1)+(c6+c7)(n2-2n+1)

6


1. Definíció: Azt mondjuk, hogy T(n)=O(f(n)) az algoritmus komplexitásának a mértéke ha léteznek c1 és c2 számok valamint n0 úgy, hogy: c1f(n) ≤ T(n) ≤ c2f(n), ()n ≥ n0. 2. Definíció: Azt mondjuk, hogy T(n)=O(f(n)) egy algoritmus komplexitásának nagyságrendje, ha létezik két pozitív konstans c, n0, úgy, hogy T(n) ≤ cf(n), ()n ≥ n0. 7

c2f(n) T(n)

T(n)=Θ(f(n)) A komplexitás mértéke c1f(n)

n0

n cf(n) T(n)

n0

n

T(n)=O(f(n)) A komplexitás nagyságrendje

8


• Az algoritmusok jellemzői (általánosság, végesség, egyediség, automatizmus ) • Szubalgoritmusok. (egymásratevődéses képzés, fokozatos képzés )

• Algoritmusosztályok

(Numerikus, nemnumerikus, feldolgozási) 9


1. Definíció: Egy algoritmust polinomiálisnak nevezünk, ha olyan temporális komplexitással rendelkezik, amelyik O(f(n)) alakú, ahol f(n) egy polinomiális függvény n hosszúságú bemenetekre. f(n)=a1n+a0 f(n)=a2n2+a1n+a0 f(n)=a16n16+a10n10+a5n5+a2n2+a1n+a0 f(n)=a6783n6783+a532n532+a5n5+a2n2+a1n+a0 10


2. Definíció: Ha egy algoritmus nem polinomiális komplexitású, akkor exponenciális; minden olyan algoritmus exponenciálisként van kezelve, amely komplexitása nlog n, habár sem nem polinomiálisak sem nem exponenciálisak matematikai értelemben. Utazóügynök probléma: Egy utazóügynök n várost kell meglátogasson bizonyos időn belül. Hogyan járja be a városokat, hogy a költsége minél kisebb legyen (legyen a költség=út hossza). Az utak bejárásának összes esete: n! n!=1.2.3.4….n>=2n-1 NEM polinomiális (exponenciális) 11


Algoritmusok ábrázolása • • • • • •

matematikai-logikai nyelvezet, pszeudokód, függőleges logikai sémák, vízszintes logikai sémák (Chapin), fastrúktúrák (Tabourier vagy Mills), döntési táblák. 12


Pszeudokód típusú nyelvek • • • • • • • • • •

Természetes nyelv, strukturált és egyszerűsített, Egy alternatívája a logikai sémának, Nem programozási nyelv, Sok változata van, Az algoritusok egymásutáni mondatokból épülnek fel, Mondatok lehetnek: egyszerűek (pl.: nyiss meg egy állományt, olvass egy bejegyzést fájlból); Komplex mondatok, logikai operátorokkal összekötve A # szimbólum az elkövetkezőkben kiterjesztett mondatra utal A mondat egy igével kezdődik (pl. Read változó,..) Megközelítés módja "top-down" tipúsú (fentről lefele) 13


Függőleges logikai séma • Az algoritmus grafikai ábrázolása, • Három fajta egységből áll (blokkból): 1) Funkcionális egység : Y=f(X) X Y 2) Döntési egység: Y Z = c(X) 3) Kötések (összeköttetések) 14


Alap kontroll struktúrák-1

a) Lineáris struktúra jelölése  (s1,s2,...,sn) s1

s2

s3

s4

b) Alternatív struktúra jelölése  (c,s1,s2), C s1

s2

c) Előfeltételes repetitív struktúra jelölése  (c,s) d) /\ Struktúra (Üres blokk) C

s

15


Alap kontroll struktúrák-2

• Utófeltételes repetitív struktúra jelölése  '(c,s) s

C

• Pszeudo-alternatív struktúra jelölése  '(c,s) C s2

• Általánosított alternatív struktúra jelölése  ' '(c,s1,s2,...sn) s1

s2

sn

16


Összefüggések • • • • • •

Π(s1,s2) = (BLOCK,s1,s2); Δ (c,s1,s2) = (IF-THEN-ELSE, c,s1,s2); Ω (c,s) = (DO-WHILE,c,s) Ω ' (c,s) = (DO-UNTIL,c,s) Δ'(c,s) = (IF-THEN,c,s) Δ' '(i,s1,s2,...sn) = (CASE-OF,i,s1,s2,...,sn).

17

Beszúrásos rendezés algoritmusa 1

2

3

4

5

6

5

2

4

6

1

3

1 for j←2 to hossz[A] 2 do S←A[j] 3 i←j-1 4 while i>0 and A[i]>S 5 do A[i+1]←A[i] 6 i←i-1 7 A[i+1]←S

Start

j=2

s1

Rendez

s2

j=j+1

s3

j<6

c2

П(s1,Ω’(c2,П(s2,s3))) Vége

18

j=2

s1

S=A[j]

s2=П(s4,П(s5,X))

s4 s2=П(s4,П(s5,П(Y,s8))) s5

i=j-1

i=i-1

s6 Y=Ω(c3,П(s7,s6))

i>0 and A[i]>S

A[i+1]=A[i]

s7

c3 A[i+1]=S

s8

j=j+1

s3

s2=П(s4,П(s5,П(Ω(c3,П(s7,s6)),s8)))

c2 F= П(s1,Ω’(c2,П(П(s4,П(s5,П(Ω(c3,П(s7,s6)),s8))),s3))) j
19


Alapstruktúrák tulajdonságai. 1) Π struktúra általában nem kommutatív: Π (s1,s2)  Π (s2,s1). 2) Π struktúra asszociatív: Π (s1, Π (s2,s3)= Π (Π (s1,s2),s3). 3) Az üres /\ elem semleges a szekvenciális struktúra szempontjából : Π (s,/\)= Π (/\,s). 4) Π struktúra jobb oldalról disztributív az alternatív strukturára nézve: Π (Δ (c,s1,s2),s3)= Δ (c, Π (s1,s3), Π (s2,s3)). 20


Alapstruktúrák tulajdonságai. 5) Π struktúra disztributív balról az alternatív struktúrára nézve : Π (s1, Δ (c,s2,s3))= Δ (c, Π (s1,s2), Π (s1,s3)). 6)  struktúra átalakítható az alternatív bennfoglalási struktúrákra:  (c,s)= (c, Π (s,  (c,s)),/\)= Δ (c, Π (s, Δ (c, Π (s,  (c,s) )),/\)),/\)=... 7) Δ ', Δ ", Ω' struktúrák átalakíthatóak a Π , Δ, Ω struktúrákra : Ω '(c,s)= Π (s, Ω (c,s));, Δ '(c,s)= Δ (c,s,/\); Δ '(c,s)= Δ (c,s, Ω (c,s)); Δ '(c,s1,s2,...sn)= Δ (c1,s1, Δ (c2,s2,...)), 21


Strukturált Program Definíció: Strukturált programnak nevezünk bármely olyan programot amelynek kontroll struktúrája megvalósítása esetén kizárólag szekvenciálisan strukturált blokkokat használunk, két ágú alternatív struktúrát és előfeltételes alternatív struktúrát. Boehm és Jacopini struktúra tétele Adott három új funkcionális blokk T,F,K T F T x--->(t,x) ; x--->(f,x) ; x--->(t,(t,x)). K K (v,x)--->x ; (t,(f,(t,x)))--->(f,(t,x)). W[(v,x)]=t <=> v=t 22


A struktúra tétele • A struktúra tétel (Boehm és Jacopini) Ha egy x-->x' alkalmazás logikai úton ábrázolható úgy, hogy az s1,s2,... akciókat tartalmazza és a c1,c2,... predikátumokat ugyanúgy reprezentálható egy logikai séma által amelyik felbomlik Π, Δ şi Ω -ra és amelyik tartalmazza ugyanazokat a blokkokat mint az eredeti séma, és még T, F, K és W tipúsú blokkokat. • Bizonyítás: indukcióval n- blokkok száma 23


„Top-down„ folyomány • „Top-down„ folyomány („fentről lefele"). • Egy strukturált program ekvivalens egy olyan programmal amelyik a következő formákat veheti fel: • P = Π (s1,s2), P = Δ (c,s1,s2) • P = Ω (c,s), P = Ω '(c,s) • ahol c állítmány, és s, s1, s2 strukturált procedúrák vagy a program funkciói. 24


Fastruktúra diagramm • a) Tabourier variáns a 3.14 ábra reprezentációit használja a következő struktúrákra: • • • • • •

szekvenciális – Π(s1,s2)=(BLOCK, s1,s2) alternatív – Δ (c,s1,s2) (IFTHENELSE,c,s1,s2) előfeltételes repetitív – jelölése (WHILEDO,c,s) pszeudoalternatív – jelölése (IFTHEN, c,s) többszörösen alternatív – jelölése (CASEOF, c,s1,s2,...,sn) utófeltételes repetitív – jelölése (DOUNTIL,s,c), 25


Tabourier variáns BLOCK

S1

IFTHENELSE

IFTHEN

S2

c c

S1

CASEOF

WHILEDO

c

S1

S2

S1

c

S1

S2

DOUNTIL

Sn

S1

c

26

BLOCK j=2

DOUNTIL BLOCK

S=A[j] i=j-1

J>hosszA

BLOCK BLOCK WHILEDO

i>0 and A[i]>S

1 for j←2 to hossz[A] 2 do S←A[j] 3 i←j-1 4 while i>0 and A[i]>S 5 do A[i+1]←A[i] 6 i←i-1 7 A[i+1]←S

BLOCK

A[i+1]=A[i]

BLOCK A[i+1]=S

j=j+1

i=i-1 27


Mills variáns WHILE DO

IF THEN ELSE C1

C1

BLOCK

S1

S2

S3

28


Döntési táblák Az első r sorra (IGEN, NEM tipús; <, =, > tipús; 0,1,2,... tipús) Az m eset száma m=n1*n2*…nr 0

c2

c1

1

c2

0

00

s1

1

01

s2

2 0

02 00

s3 s4

1

01

s5

2

02

s6

3.18.b. ábra Az esetek meghatározása

29


Döntési táblák • Hatásvonal környéke * az Sj feltételek esetében az Ai akció végrehajtásra kerül

tij= üres ha az Ai akció nem hajtódik végre az Sj esetben

• A döntési táblák három tipúsúak lehetnek : a) korlátozott bemenettel (minden feltétel az L2={0,1} halmaz elemeiből vesz értéket); b) kiterjesztett bemenettel (vagyis a feltételek értelmezési tartománya Ln, n>2 halmaz); c) vegyes bemenettel (egyes feltételek az L2 –n vannak értelmezve mások az Ln, n>2. 30


Döntési táblák •

A feladatok szekvenciája: - döntési tábla feltételeinek megállapítása - szabályok megállapítása - lehetséges akciók meghatározása - döntési tábla elkészítése - az ellentmondások és a redundancia kiküszöbölése - a kapott tábla egyszerűsítése 31


Ismétlő kérdések • • • • • • • • • •

Milyen esetekben algoritmizáluk A komplexitás definíciója Algoritmusok tulajdonságai és osztályai Mi egy polinomiális és egy nempolinomiális algoritmus Pszeudokód tipúsú nyelvek Függőleges logikai sémák Alapstruktúrák tulajdonságai Strukturált program , Boehm-Jacopini tétele Fastruktúrák (Tabourie, Mills) 32 Döntési táblák. Felépítés és egyszerűsítés

Erdélyi Magyar TudományEgyetem (EMTE

Recommend Documents