060220 Shrnutí řešení: -upřesnění zadání -zdůvodněná volba algoritmu -representace dat -dekompozice programu (rozklad na části) -diskuze
Vnější třídění
Dvoucestne dvoufázové (přirozené) slučování Slévání: Běhy - uspořádané podposloupnosti rozdělím soubor na dva (v prvním jsou sudé běhy, a v druhém liché) a pak je zase sliju složitost - N log2N (nejhorší případ - samé jednoprvkové běhy) Vylepšení -> jednofázové - při slučování je rovnou rozdělujeme (zrychlení 2x); vícecestné - na víc proudů (změní se základ logaritmu); můžeme si je na začátku setřídit v paměti (po částech)(zrychlení pouze o něco) Předtřídění v paměti 1) načíst (M záznamů), setřídit & zapsat ⇒ M 2) použít haldu 3) dvě haldy je rozumné použít pole souborů array[1..N] of text; record f:text; x:typ; platna end; imin A[imin].x {výběr minima:} min:=Velika;imin:=0; for i:=1 to N do if (A[i].x>Minula) and (A[i].x>=Minula) and (A[i].x < min) then begin min:=A[i].x; imin:=i end; 1
if imin<>0 then begin Vystup(min); Minula:=A[i].x; if eof(A[i].f) then A[i].platna:=false else read(A[i].f,A[i].x) end; imin:=0; min:=neznam; for i:= 2 to
060227 jednofázové třídění - 2k otevřených souborů dvojfázové třídění - k+1 otevřených souborů (ale zapisuje se 2x) => dilema => jiný algoritmus - polyfázové třídění - 3 soubory, když se jeden ukončí, tak se začnou slévat druhé dva - k+1 soubroů; nemám fázi rozdělování
Stromy (souvislý, acyklický graf) - budeme ale chtít víc - budeme chtít mít kořen; uspořádaný, zakořeněný strom uspořádaný - synové jsou uspořádaní - a
a
b c c b binární strom - každý vrchol má nanejvýš dva syny rodokmen je binární strom PRodokmen=^TRodokmen; TRodokmen=record jméno.string otec,matka:PRodokmen end; Binární vyhledávací strom pro každý vrchol platí: pokud má vrchol hodnotu x, tak v levém podstromu je hodnota <x a v pravém podstromu je hodnota >x
• 10
20
5 1
8
3 7
2
vyhledávání: přidání - jako vyhledávání, akorát když hledání skončí NILem, tak tam ten prvek zařadím type PVrchol=^TVrchol; TVrchol=record x:ordinální; L,P:PVrchol end; function Obsahuje(Kde:PVrchol;H:ordinální):PVrchol; begin if Kde=NIL then Obsahuje:=NIL else if H
Kde.x then Obsahuje:=Obsahuje(Kde^.P,H) else Obsahuje:=Kde; end; function Obsahuje(Kde:PVrchol;H:ordinální):PVRchol; begin {zkrácené vyhodnocování}{$B-} while (Kde<>NIL) and (Kde^.x<>H) do if HKam^.x then Přidej(Kam^.P,H) else ? end; procedure Přidej(var Kde:PVrchol;H:ordinální); var n,p,min:PPrvek; begin new(n); n^.x:=H; n^.L:=NIL; n^.P:=NIL; if Kde=NIL then Kde:=n 3
else begin min:=NIL; p:=Kde; while (p<>NIL) and (p^.x<>H) do begin min:=p; if HNIL then ? {co udělat s prvkem n^?} if H<min^.x then min^.L:=n else min^.P:=n; end;
odebírání: 1) vrchol nemá syny 2) vrchol má 1 syna 3) vrchol má 2 syny nejlevjejšího z pravého nebo nejpravější z levého procedure Zruš(var K:PPrvek); begin if K^.L=NIL then begin q:=K; K:=K^.P end else if K^.P=NIL then begin q:=K; K:=K^.L end else begin p:=K^.L; q:=p; while q^.P<>NIL do begin p:=q; q:=q^.P end; K^.x:=q^.x; if p<>q then p^.P:=q^.L !else K^.L:=P^.L! end; dispose(q) end; na stránkách jsou animace ve flash
0603006 Objektově orientované programování typ ................... proměnná (instance) 4
CLASS...............OBJECT TŘÍDA................OBJEKT
ENCAPSULATION = ZAPOUZDŘENÍ
možnost oddělit co to dělá od toho, jak se to dělá
Dědění: typ TVelkyPes=object(TPes) druhy metod: −
statická - při překladu se tam adresy metod natvrdo
−
virtuální - při každém volání se zjišťuje, co vlastně máme volat - pro každý typ se pamatuje tabulka adres metod (tabulka virtuálních metod)
constructor - zvláštní typ procedury, který navíc nastaví ukazatel na tabulku virtuálních metod rozšířená syntaxe new: new(PPes,Dosad(’alik’,5); další rozšíření: pP:=New(PVelkyPes,Dosad(’alik’,5)); na VelkéhoPsa
—– můžu si ukazatelem na Psa ukázat
polymorfizmus: Psinec:array[1..10] of PPes; Psinec[1]:=New(PVelkyPes, Dosad(’alik’,5)); Psinec[2]:=New(PPes, Dosad(’brok’,3)); . . . for i:=1 to 10 do Psinec[i]^.Zastekej;
Self - vlastní objekt @Self nebo addr(self) vrátí adresu vlastního objektu
metody, které musím uvést, kvůli odvozeným objektům, ale nebudu ji volat se říká abstraktní v delphách se dává kl. slovo abstract, v pascalu se dává chyba RunError(211)
060313 Programování řízené událostmi vlastnosti - pro zápis je definována funkce, a pro čtení procedura 5
vlastnosti viditelné komponenty - left, top, ShowMessage Sender - co to zavolalo (Sender as TButton).Caption - bezpečné přetypování TButton(Sender).Caption - nebezpečné přetypování sender is TButton - je pravda, pokud je sender TButton, nebo odvozené
chráněný blok: - ochrana proti chybám i:=0; try i:=1 div i; i:=59+i; except on EDivByZero do i:=77; on Exception do i:=78; end;
060320 Vyvážené stromy: 1) Pro ∀ vrcholy platí: Počet prvků v obou podstromech se ličí maximálně o 1 - dokonale vyvážený strom AVL sromy Pro ∀ vrchol platí, že výška obou podstromů se ličí nejvýše o 1 (Fibonacciho stromy) P0 = 0 P1 = 1 PK = 1 + PK −1 + PK −2, k ≥ 2 v každém vrcholu - údaj o vyvážení (-1,0,+1)
pokud přidáváme, tak pošleme příznak. Pokud dostaneme příznak, tak PR:=false +1 ->0 pokud je údaj o vyvážení 0 ->-1 PR:=true -1 musíme změnit strom pomocí rotací PR:=false Jednoduchá RR-rotace 6
Dvojitá LR-rotace vždy jen jedna rotace Mazání: někdy je nutné log n rotací
snaha - snížit množství diskových operací B-strom stupně N -každý vrchol obsahuje N 2N hodnot, kromě kořene -pokud uzel obsahuje k hodnot, má k + 1 synů -všechny listy jsou na stejné úrovni
060403 simulační model spojitá x diskrétní simulace spojitá - po pravidelných krocích diskrétní - modelujeme změnu stavu
stav zahrnuje - čas (simulační čas), automobily(co dělá(čeká, nakládá, jede A->B, vykládá jede B->A, nic), kolik písku v B/A, simulační kalendář(události(kdy,kdo,co))
Proces Begin inicializujModel; while not Konec do vyberZKalendáře(U); Čas:=U.kdy; U.kdo.Zpracuj(U.co) end; end;
type TCo=(udStart,udNaloženo,udJeVB,udVyloženo,udJeVA); TProces=object procedure ZpracujUdalost(Co:TCo);virtual; end; TAuto=object(TProces) v,u,dn,dv:real; procedure ZpracujUdalost(Co:TCo);virtual; constructor Init(-r,-u,-dn,-dv:real); end; 7
udStart: if Čas>KBMZNDA then zn:=Čas else zn:=KBMZNDA; plán(@self,zn+dn,udNaloženo); KBMZNDA:=zn+dn; udNaloženo: plán(@self,Čas+VzdAB(v,vdJeVB), if PiskvA>nosnost then veze:=nosnost else veze:=PisekvA; PisekvA:=PisekvA-veze; udVyloženo PisekVB:=PisekVB+veze; if PisekVB>........ then Plan(@self,vzdABv,udStart); udJeVB: Plan(@self,Čas+dv,udVyloženo); !Úkolem Simulace NENÍ optimalizovat!
060410 Dynamické programování
optimální řešení má jako řešení svých podúloh opět optimální řešení
dělají se tabulky - postupuje se od nejjednodušších případů, a zaznamenávají se jejich hodnoty
Form2.Show - pouze vyvolá okno Form2.ShowModal - čeká na ukončení okna
060424 Grafy Reprezentace -Matice sousednosti - Mij =
0 jinak 1 p okud (i, j) ∈ H
-Matice vzdáleností (podobné) 8
-Matice incidence Iij i ∈ V j ∈ H
0 1 pokud hrana j = (i, ∗ ) or j = ( ∗ , i)
- používá se pro řídký graf
-Seznamy následníků - ukládání by bylo neefektivní - je lepší to uložit všechny následníky do jednoho pole, a do druhého pole si pamatovat, kde začínají - kde končí se určí z toho, kde začínají další následníci - tento trik se dá použít i pro ukládání stringů
Grafové algoritmy Nejkratší cesta -Dijkstrův algoritmus - vhodná reprezentace grafu - seznam následníků - složitost N 2 -Floydův algoritmus Mij ...matice vzdáleností ≥ 0 tam, kde nevede hrana je Mij = + ∞ 1..N vrcholy for i:=1 to N do for j:=1 to N do for k:=1 to N do if Mij > Mik + Mk j then Mij : = Mik + Mkj ; složitost N 3 Test acykličnosti - Topologické uspořádání - takové uspořádání vrcholů (U = {1..N }| π: {1..N } → {1..N } že platí: Pokud (i, j) ∈ H, potom π(i) < π(j) Opakuj dokud je graf neprázdný -najdi vrchol, který nemá předchůdce (pokud se nepodaří, graf obsahuje cyklus) -ten vrchol vypiš (zařaď do π) -vymaž z grafu (včetně hran)
-Hledání nejkratších cest v topologicky uspořádaném grafupro každý vrchol (kromě prvního) zkoumám, jak se do něj dostanu nejlíp (zkomám všechny vrcholy z kterých vede hrana) - vhodná reprezentace - seznam následníků + počet předchůdců heuristika - pamatujeme si seznam vrcholů s nulovým počtem předchůdců složitost - počet hran Určování komponent souvislosti -postupné procházení -faktorová množina - pro každý vrchol si pamatuju, do které množiny patří (začínám s tím, že každý vrchol patří do jedné komponenty); pro každou hranu sloučím obě komponenty
Delphi Dialogy - okna, co se spustí čekají na odezvu, a ukončí se TMemo 9
TStrings LoadFromFile SaveToFile if OpenDialog1.Execute then Memo1.Lines.LoadFromFile(OpenDialog1.FileName);
061505 type PVrchol=^TVrchol; TVrcol=record x:THodnota; L,P:PVrchol end; //pre-order: ->prefix procedure Projdi(p:PVrchol); begin ProjdiVrchol(x) Projdi(P^.L); Projdi(P^.P); end; //in-order: ->infix procedure Projdi(p:PVrchol); begin Projdi(P^.L); Projdi(P^.P); ProjdiVrchol(x) end; //post-order: ->postfix procedure Projdi(p:PVrchol); begin Projdi(P^.L); ProjdiVrchol(x) Projdi(P^.P); end; //procházení prefixu: function H:integer; var c:char; begin read(c); case c of ’+’:H:=H+H; ’-’:H:=H-H; ’*’:H:=H*H; ’/’:H div H; ’0’..’9’:H:=ord(c)-ord(’0’) end; end; // function S:PVrchol; var p:PVrchol; 10
begin new(p); read(p^.x); if p^.x in [’+’,’-’,’*’,’/’] then begin p^.L:=S;p^.P:=S; end else begin p^.L:=NIL;p^.P:=NIL end; S:=P; end; Hlední k-tého prvku: N čísel chceme najít k-tý největší/nejmenší 1) postupně vyhledávat nejmenší, a zahazovat - kn 2) setřídit - n log n 3) postavit haldu - n + (k − 1)log n 4) postavit haldu z n − (k − 1) prvků - (n − (k − 1)) + (k − 1) log(n − (k − 1)) 5) quicksort-like algoritmus - pokud by jsme uměli hledat pivota v půlce - 2n 6) lineární algoritmus -prvky rozdělíme do sedmic; každou sedmici setřídíme(3n) tvrzení - k-tý prvek z n lze nalézt na 28n porovnání. dk - indukcí pro n ≤ 57 to platí ( = n28). Předpokládejme, že pro n − 1 už to platí.
56 n2
57 ∗ 56 2
=
n
-najdeme prostřední prvek z mediánů ( 7 28 = 4n) <M ⊂A
-prvky projdeme a rozdělíme = M ⊂ B (1n) >M ⊂C
-když k < |A| potom hledej v A, jinak když |A| < K ≤ |A| + |B |, potom vrať M , jinak hledej v C
zadání: vstup: -lístky(1 000 000) - předmět; učitel; hodnocení .... -učitel - jméno (1000); katedra (100) nesetříděné výstup: -nástěnka - učitel; předmět; průměr; odchylka (střední kvadratická) - s. podle učitelů + předm. -katedra -
————————||——————————————— - s. podle kat. + uč. + př.
nevejde se do paměti
-setřídit podle učitelů předmětůP-> setříděný soubor - dokážeme spočítat průměr, odchylku P P 2 + P ( (ai − R)2 = ai − R 2ai + R2) (jedním průchodem) 11
->uč,př,prům,odch setř podle uč+př = V1
-katedry setřídit podle uč
->join V1 a setř. katr. ->Nástěnka+katedra->setřídit podle kat->nástěnka+katedra kat->
=> může být užitečné si to nakreslit
060522 - hashování Máte-li úlohu, kterou nechcete nebo neumíte řešit, řešte jinou úlohu. Hezké nakreslení grafu => odpuzující se body Genetické algoritmy množina řešení - populace ohodnocovací fce, která řekne, jak moc je který prvek dobrý (fitness funkce) -selekce - je dobré dát malou příležitost i těm ostatním -křížení -mutace - je nutná, protože jinak vznikne stejná populace; pokud je velká, tak se budou obměňovat stále jen ti nejhorší ->nová populace -hledání neznámého obrázku -broučci 1,2
občas je dobré poodstoupit od úlohy (páska + otáčkoměr)
Zkuste hledat řešení v nějakém určitém tvaru OCR víc částí - rozdělit stránku na bloky textu; na řádky ->na písmena
úloha - rozpoznat písmeno - hledám 5 bodů (desetici souřadnic), které jsou takové, že pomocí nich jde rozpoznat všech 26 písmen -> hledám desetici písmen -> máme fittnes funkci χ, která říká, kolik písmen je pro naši desetici stejných .../jinak
12
