Toto je cast zapisku z predmetu programovani II, odprednaseno Tomasem Holanem. Za chyby v nasledujicich dokumentech samozrejme prednasejici neruci - nasekala jsem je tam ja :) Kdyby jste tedy na nejake narazili, budu rada, kdyz me na ne upozornite.
AVL STROMY
03-24-2005
==========
-=[ dokonale vyvazeny strom - AVL ]=-
pro kazdy vrchol plati, ze pocet synu v levem a pravem podstromu se lisi
maximalne o jeden => AVL stromy
B
/ \
A Z
/ \
X Y
- pamatujeme si hloubky stromu (staci ktery hlubsi) napr.:
1...pravej hlubsi
-1...levej hlubsi
0...stejny
-=[ pridavani ]=-
po pridani si overime, zda se zvysila hloubka a jestli nam to uz vadi.
-=[ rotace ]=-
--prodlouzil se X:
B A
/ \ / \
A Z -> X B
/ \ / \
X Y Y Z
znaceni:
K...koren stromu
L...levy syn K
P...pravy syn K
je treba zmenit hodnoty(todle neni spravny poradi,mozna :):
K=K->L;
K->L->P=K;
K->L=K->L->P;
--prodlouzil se Y - dvojita rotace (doleva a pak doprava):
B B C
/ \ / \ / \
A Z -> C Z -> A B
/ \ / \ / \ / \
X C A Y X W Y Z
/ \ / \
W Y X W
vrchol C musel mit pred pridavanim vyvazeni 0, jinak by se bud neprodlouzil,
nebo bysme to resili uz driv.
--ostatni priklady symetricky
je vhodnejsi misto ukazatelu na leve a prave syny mit dvouprvkove pole. tim
se vyhneme opakovani stejneho kodu.
-=[ mazani ]=-
jako u normalnich BVS, ale musime posilat nahoru info,jak se zkracuji
podstromy. takze obcas musime vyvazovat nekolikrat, treba az do korene.
OPTIMALNI STROMY
03-24-2005
================
chceme vyrobit vyhledavaci strom, mame hodnoty A,B,C. nebudem tam uz pak
provadet zadny operace, jen vyhledavat. tak to dame treba takle:
B
/ \
A C
ale kdo rika, ze je budem potrebovat vsecky stejne casto? rekneme, ze A budeme
potrebovat napr. 2x, B 1x a C 10x.
-=[ optimalni vyhledvaci strom ]=-
je takovy strom, ve kterym je soucet vsech Pi a Hi minimalni, kde Pi je
pravdepodobnost, ze ten prvek budu chtit a Hi je jeho hloubka ve stromu.
udelame si tabulku:
+---+---+------- pravdepodobnost A,B a C
A | | |
\ v v v
B -> 34 = 2*1+1*2+10*3
\ ^ ^ ^
C | | |
+---+----+---- hloubka ve stromu (A,B a C)
A
\
C -> 25 = 2*1+10*2+1*3
/ | | | | | |
B +-+ +--+ +-+
A C B
C
/
A -> 17 = 10*1+2*2+1*3
\ | | | | | |
B +--+ +-+ +-+
C A B
B
/ \ -> 25 = 1*1+2*2+10*2
A C
C
/
B -> 18 = 10*1+1*2+2*3
/
A
takze nejlepsi je ten se 17 :)
uvedomme si dve zajimave vlastnosti:
1\ kazdy podstrom obsahuje souvislou mnozinu tech cisel. to je diky tomu, ze
je to BVS, ze nam kady vrchol puli mnozinu svych potomku. takze dybych
chtela projit vsecky podstromy, tak tech useku bude mene nez N^2, kde N
je pocet prvku.
2\ kdyz si predstavim, ze mam nejaky ten optimalni strom, tak co muzu rict o
jeho podstromech? napr. mam cisla 1...100
57
/ \
A B
tak podstormy A i B jsou (musej bejt) taky optimalni.
-=[ sestaveni optimalniho vyhledavaciho stromu ]=-
jak teda optimalni strom sestavit?
pocet prvku | stromecky s koreny
| A | B | C | D
============+==================================================================
1 | A | B | C | D
| => 2 porovnani | => 1 porovnani| => 10porovnani | => 7 porovnani
------------+----------------+---------------+----------------+----------------
jaky bude nejlepsi podstrom, pro cisla od 37 do 69? kolik operaci budu na to
potrebovat? strom bude pokryvat 33 prvku. vsechny mensi stromy uz mam
prozkoumany. takze budu postupne brat ty prvky a budu se ptat, jaky by to
bylo, dyby byl korenem (jaky bude nejlepsi podstrom jeho leveho a praveho syna
- coz budu delat podle tabulky) => optimalni strom dokazu sestrojit se
slozitosti N^3
ted pro 2 prvky:
vezmeme si
A
\
B
tim, ze pripojim B, je mi v B ke kazdemu prvku prodlouzi cesta o 1. takze k ty
sume budu muset pricist pro kazdy prvek jeho cetnost. a jeste pristu cetnost
korene. to samy udelam s levym synem (kdyz tam je).
tedy sectu narocnosti podstromu a prictu narocnosti vsech jeho prvku a korene.
pro nas pripad teda pricitame 1 (pro B) a 2(pro A).
pro strom zacinajici B pricitam 1 a 10. takze na C visi B.
atd...
------------+----------------+---------------+----------------+----------------
| 1+(2+1) nebo | (10+1)+1 | 7+(10+7) |
| 2+(2+1) | | |
2 | 4 porovnani | 12 porovnani | 24 porovnani |
------------+----------------+---------------+----------------+----------------
--pro triprvkove stromy:
pro trojici ABC:
nejdriv korenem urcime A, pravy podstrom nejlepsi pro BC takze 12+13(cetnosti
A,B a C)=25;
korenem bude B: nalevo nejlepsi podstrom pro A a napravo nejlepsi pro C takze:
2+10+13=25;
korenem bude C, jako levej nejlepsi podstrom pro AB: 4+13(ABC)=17;
takze nejlepsi, kdyz korenem bude C.
pro trojici BCD:
korenem B, napravo DC: 24+18=42;
v koreni C, nalevo B, napravo D: 8+18=26;
koren D, nalevo BD: 12+18=30;
takze nejlepsi, kdyz korenem je C.
ABC, koren C BCD, koren C
------------+----------------+---------------+----------------+----------------
3 | 17 porovnani | 26 porovnani |
------------+----------------+---------------+----------------+----------------
--pro ctyrprvkove stromy:
koren A, pravy syn nejlepsi pro BCD: 26+20=46;
koren B, nalevo pro A, nalevo pro CD: 2+24+20=46;
koren C, nalevo nejlepsi pro AB, nalevo D: 4+7+20=31;
koren D, nalevo nejlepsi pro ABC: 17+20=37;
takze nejlepsi je s korenem v C.
ABCD, koren C
------------+----------------+---------------+----------------+----------------
4 | 31 porovnani |
------------+----------------+---------------+----------------+----------------
takze nejlepsi:
C
/ \
A D
\
B
tabulka cetnosti vyhledavani:
A -> 2
B -> 1
C -> 10
D -> 7
a dotazy na prvky, ktery tam nejsou:
a -> 3
b -> 1
c -> 1
d -> 10
-=[ shrnuti ]=-
tabulka metod:
metoda | INS | DEL | FIND | MIN
=====================+===============+=============+==============+=============
pole | O(1) (nakonec)| O(1) | O(N) | O(n)
---------------------+---------------+-------------+--------------+-------------
setridene pole | O(N) | O(N) | O(log N) | O(1)
---------------------+---------------+-------------+--------------+-------------
halda | O(log N) | O(log N) | O(N) | O(1)
---------------------+---------------+-------------+--------------+-------------
AVL tree | O(log N) | O(log N) | O(log N) | O(log N)
HASHOVANI
03-24-2005
==========
-=[ hashovani - metoda transformace klice ]=-
funkce f(P) - prohledne si prvek a da index, kam ma prvek vlozit.
+-------------------------+
| |
+-------------------------+
| |
+-------------------------+
| |
+-------------------------+
| P1 | <------------------------------- f(P1)
+-------------------------+
| |
+-------------------------+
| |
+-------------------------+
| |
+-------------------------+
| | +-------- f(P3) // kolize
+-------------------------+ |
| | |
+-------------------------+ v
| P2 | <------------------------------- f(P2)
+-------------------------+
| P3 (pri reseni kolizi |
| metodou 1\) |
+-------------------------+
| |
+-------------------------+
o hashovaci fci:
mela by vyloucit jakoukoli logiku tech dat, aby se nam nekde nenakupily.
reseni kolizi:
1\ dame prvek hned vedle. tim ale muzeme obsadit misto, ktere bude potreba,
patri tam jiny prvek
2\ retezeni prvku
mazani:
pri reseni kolizi podle 1\: nemuzu jen tak smazat, ze jo:)
PREFIX, POSTFIX, INFIX
04-07-2005
======================
type
TPrvek=record
...
c:integer;
L,P:PPrvek;
end;
-=( poradi prochazeni stromu )=-
PRE-ORDER:
procedure Projdi(K:PPrvek); //K...koren
begin
ProjdiPrvek(K);
Projdi(K^.L);
Projdi(K^.P);
end;
IN-ORDER:
procedure Projdi(K:PPrvek); //K...koren
begin
Projdi(K^.L);
ProjdiPrvek(K);
Projdi(K^.P);
end;
POST-ORDER:
procedure Projdi(K:PPrvek); //K...koren
begin
Projdi(K^.L);
Projdi(K^.P);
ProjdiPrvek(K);
end;
*
/ \
+ -
/ \ / \
1 2 3 4
pro-order: *+12-34 -> PREFIX (nejde prodlouzitm, musime znat delku)
in-order: 1+2*3-4 -> INFIX (jde prodlouzit)
post-order: 12+34-* -> POSTFIX (jde prodlouzit)
-=( jednoznacnost )=-
zapis 1-2+3 jsme mohli dostat ze dvou ruznych stromu:
- +
/ \ / \
1 + nebo - 3
/ \ / \
2 3 1 2
zatimco u prefixu a postfixu takovato nejednoznacnost neexistuje.
-=( postfix )=-
strkame to do zasobniku a pak to vybirame. pro vyraz (1+2)*(3-4)
| | | | |-| | | | | | |
|+| | | |4| | | | *| | |
|2| | | |3| |-1| |-1| | |
|1| |3| |3| | 3| | 3| |-3|
+-+ +-+ +-+ +--+ +--+ +--+
-=( prefix )=-
function Hodnota:TYP;
var
c:char; // prvek vstupu
begin
read(c);
if JeCislo(c) then Hodnota:=H(c);
else
case c of
'+':Hodnota:=Hodnota+Hodnota; //volame fci Hodnota pro dalsi c
'-':...
'*':...
'/':...
end;
end;
-=( prevody mezi jednotlivymi *fixy )=-
nejjednodussi cesta je postavit strom:
// z prefixu (na stromecek)
function Strom:PPrvek;
var
c:char;
p:PPrvek;
begin
new(p);
read(c);
p^.c:=c;
if c in ['+','-','*','/'] then
begin
p^.L:=Strom;
p^.P:=Strom;
end
else
begin
p^.L:=nil;
p^.P:=nil;
end;
Strom:=p;
end;
// z postfixu (na stromecek)
var
Z:array[1..MAX] of PPrvek; // zasobnik
xZ:integer; // pocet prvku v zasobniku
P:PPrvek;
begin
xZ:=0;
while not eof(soubor) do
begin
read(c);
new(P);
if c in ['+','-','*','/'] then // je operace
begin
P^.L:=Z[xZ-1];
P^.P:=Z[xZ];
Dec(xZ,2);
end;
else // neni operace
begin
P^.L:=nil;
P^.P:=nil;
end;
Inc(xZ); // vlozeni do zasobniku
Z[xZ]:=p;
end;
end;
VYJIMKY V DELPHACH
04-07-2005
==================
-=( chranene bloky )=-
try
.
. // todle se zkusi
.
except
. // dyz se to nepovede, tak se udela todle
.
.
end;
nebo
try
.
. // todle se zkusi udelat
.
finaly
. // todle se udela kazdopadne
.
.
end;
-=( priklad 1 )=-
try
try
i:=0;
i:=i div i;
ShowMessage(IntoStr(i));
finaly
ShowMessage('finaly');
end;
except
ShowMessge('vyjimka');
end;
-=( priklad 2 )=-
i:=0;
i:=i+1;
Abort; // pusobi jako vyjimka, ukonci provadeni prikazu,
// ale nedava zadny hlaseni
// napr. pri kliku na CANCEL
i:=i*1;
ShowMessage(IntoStr(i));
-=( priklad 3 )=-
ShowMwssage((Sender as TButton).Caption); // bezpecne pretypovani
diskretni simulace
04-21-2005
==================
hromada pisku
_
/.\
/...\
/.....\
/.......\
---------
+-------------------------------------------------+
mesto A mesto B
+---+_
|___|_| ------>
OO O
xcene prevyst tu hromadu pisku z mesta A do mesta B
nakladak:
nosnost: 10t
rychlost: 60km/h
doba nakladky: 1h
doba vykladky: 29s
|AB|=60km
za jak dlouho to stiheme?
100+100+99+100*20s = 299h a 2000s
co kdybychom meli ty auta dve, uplne stejne? prvni odhad je polovina casu. je
to 149h a 1000s.
-=( ted to zkomplikujeme )=-
nakladak 1:
nosnost: 10t
rychlost: 60km/h
doba nakladky: 1h
doba vykladky: 20s
nakladak 2:
nosnost: 15t
rychlost: 90km/h
doba nakladky: 1.5h
doba vykladky: 50s
nakladak 3:
nosnost: 10kg
rychlost: 250km/h
doba nakladky: 5s
doba vykladky: 1s
-=( casovy sled udalosti )=-
00:00:00 N1 naklada
N2 naklada
N3 naklada
00:00:05 A3 odjizdi
00:15:05 A3 vyklada
00:15:06 A3 odjizdi z B
01:00:00 A1 odjizdi
01:30:00 A2 odjizdi
-=( planovaci kalendar )=-
je cas 00:15:05. vezmeme nejblizsi udalost, co v kalendari mame z zpracujeme
ji. tomu se rika DISKRETNI SIMULACE. vime, kdy se stane dalsi udalost, cili
zname casovy intervaly, ve kterych se nic nedeje. jako vypravci na maly
stanici vi, kdy prijede vlak, nasadi cepici, zamava mu, sunda cepici, nastavi
si budika na dalsi vlak a de spat .)
jakou datovou strukturu je nejlepsi pouzit na ten kalendar? haldu. pac vsecky
potrebny veci tam muzem delat v logaritmickym case.
DISKRETNI SIMULACE
04-28-2005
==================
-=( priklad s piskem z minule hodiny - pokracovani )=-
potize:
- maji stejny cas:
+ zajistit, aby nemeli stejny cas
+ ty se stejnym casem brat lexikograficky
- ve stejnem case smi nakladat jen jedno auto
+ muzeme udelat frontu
+ lepsi je si pamatovat, od kolika hodin je osoba s lopatou volna. prijede
auto v 800, na tabuli je napsano, ze delnik je volny od 800, jede za nim,
prepise tabuli, ze delnik bude volny az v 810... kdyz prijede auto a
prijede driv, nez ma delnik volno, tak si naplanuje udalost nakaldani na
ten cas na tabuly a zmeni ho pro dalsi auta...
- na nejakem useku dalnice je zakazano predjizdet
+ kdyz tam neni pomalejsi auto, tak dojede normalne. pokud potka nejake
pomalejsi auto, tak se za nej zaradi a dojede spolecne s nim. takze kazde
auto napise na tabuli, v kolik tam dojede, za nim jedouci auta se na to
podivaj a pokud by meli dojet driv, tak dojedou stejne jako ono, pokud by
meli dojet pozdejs, tak dojedou normalne podle sveho planu.
-=( uloha s obchodnim domem )=-
mame obchodni dum s nekolika potry a oddelenimy, seznam zakazniku a casy,
kdy prijdou nakoupit a co budou kupovat:
zakaznici:
- jmeno zakaznika
- cas prichodu
- trpelivost (jak dlouho je oxoten cekat ve fronte)
- seznam oddeleni (ktery xe navstivit. kdyz uz mu zbyva posledni oddeleni,
co xe navstivit, tak i dyz ztrati trpelivost, tak neodejde)
oddeleni:
- id
- rychlost (za jak dlouho obslouzi zakaznika)
- patro
vytahy:
- id
- doba nastupu
- doba vystupu
- doba prejezdu z patra do patra
- nostnost
kdy odejde posledni zakaznik?
-=( reseni )=-
navrhneme zase diskretni simulaci, potrebujeme zjistit:
- jake tam budou procesy
- stavy procesu
- jake budou udalosti
- jak bude ktery proces reagovat na jakou udalost
oddeleni:
U...udalost
- na zacatku oddeleni nedela nic, tedy vchozi stav
- prave ted obsluhuje zakaznika
+ jak se dozvi oddeleni, ze ma obsluhovat zakzanika? pac zakaznik probudi
prodavacku :) prodovacka, dyz ho zacina obsluhovat, tak naplanuje sama sebe
na dobu, kdy ho doobslouzi. taky naplanuje zakaznika, do kdy ho obslouzi.
nemuze ten zakaznik se naplanovat sam? nemuze, pac zakaznik nevi, za jak
dlouho se dostane na radu, pac fronta pred nim je treba dlouha, ale spouste
lidi treba dojde trpelivost a odejdou z fronty. kdyz zakaznikovy dojde
trpelivost, musi prodovacka zrusit jeho udalost
+--------------+
| vychozi stav |
+--------------+
| ^
| |
U-konec zakaznik
obsluhy prisel do
| oddeleni
| |
v |
+-----------+
| obsluhuje |
+-----------+
zakaznik:
- muze prijit do oddeleni (vyxozi)
- zaradit se do fronty a naplanovat si, kdy mu dojede trpelivost(U), pripadne
vzbudit prodavacku, odejit
- jit k vytahu, tam cekat frontu
+--------+---------------+
+------| vyxozi | v
| +--------+ +------------+
sam se ^ ^ | prichod do |
zaradi do | | | fronty |
fronty | | +------------+
pripadne | | |
probudi vytah | +------U-konec----+
| | obsluhy
v |
+----------+ |
| prechod | |
| k vytahu | |
+----------+ |
| |
vytah |
| |
v |
+---------+ |
| jizda |-----+
| vytahem |
+---------+
vytah:
- vychozi stav
- lidi nastupuji
- lidi vystupuji
- vytah jede
+-------+
+-------| start |<--------+
| +-------+ |
| |
v |
+--------+ |
| nastup | |
| lidi |<------------------+--------+
+--------+ | vystup |
| | lidi |
| +--------+
| ^
| +------+ |
+->| jede |---------------+
+------+
otazka ale je, jak se bude vytah chovat, dyz ma na kadym patre spoustu lidi a
vevnitr lidi... kam ma jet? tak rekneme, ze nejdriv obslouzi ty lidi, co sou
uvnitr. a co dal? dybysme sli tam, tam co je to nejbliz, tak ty lidi v hornich
a spodnich patrech by se moc nedockali. tedy pouzijeme algoritmu vytahu: pojede
tam, kde si ho zavolaji a potom bude pokracovat ve stejnym smeru, dokud v tom
smeru budou pozadavky.
-=( poznamky k holanove implementaci )=-
+ fronta - spojak
+ promenna CAS - simuleje cas v modelu
+ proces: id, patro, fce SAY (vypise cas a id objektu, patro)
- ten zelenej sajrajt(asm) ceka na stisk klavesy bez pouziti unicty crt :))
+ zaznam planu: kdy, kdo, udalost
+ vyrad z planu (kdyz zakaznikovi dojde trpelivost)
+ zakaznik: od(jake oddeleni ma ted na rade)
+ vytah: cekajici(fronta lidi, co cekaj), pasazeri(lidi uvnitr)
DYNAMICKE PROGRAMOVANI
05-05-2005
======================
texnika slouzici k hledani nejakeho minimalniho nebo maximalniho reseni, resime
male podulohy. potrebujeme prozkoumat secky moznosti, jak ulohu rozdelime.
hledame nejmensi nebo nejvetsi prvek z exponencialne velike mnoziny a pritom
to zmaknem v polynomialnim casem. misto abysme to dali shora, tak zacneme
odspoda, tema nejmensima ulohama a skaldame z nich vetsi.
-=( nasobeni rady matic )=-
A1 * A2 * A3 * ... * An
Ak: velikosti ak x bk
mam matici 2x3 * 3x5 * 5x2
mam dve moznosti uzavorkovani, dostabu dycky stejny vysledek, kuli asociativite,
ale bude mi to trvat ruzne dlouho.
1/ (2x3 * 3x5) * 5x2 -> 2*3*5+@*5*2=30+20=50
2/ 2x3 * (3x5 * 5x2) -> 30+12=42
budeme si ukladat mezivysledky do tabulky, budeme si ukladat kolik potrebujeme
operaci na nasobeni:
mame matice rozmeru:
2x3, 3x7, 7x4, 4x5
A B C D
a xceme je nasobit v zadanym poradi.
+----------------+---------------------------------------+
| souciny vsech | kerou zacina |
| +---------+---------+---------+---------+
| k-tic | A | B | C | D |
+----------------+---------+---------+---------+---------+
| 1 | 0 | 0 | 0 | 0 |
+----------------+---------+---------+---------+---------+
| 2 |2*3*7=42 |3*7*4=84 |7*4*5=140|
+----------------+---------+---------+---------+
| 3 |98 (AB)C |144 (BC)D|
+----------------+=========+---------+
| 4 | 138 |
| |((AB)C)D |
+----------------+=========+
kdyz budu zkoumat, jak nejlepe vynasobit trojice, tak uz mam 2 moznosti, jak
to uzavorkovat. vyuziju predchozi vysledky z tabulky, prozkoumam obe moznosti:
(A*B)*C=42+56=98
A*(B*C)=84+24=108
lepsi je ta prvni moznost, takze si ji ulozim.
zacina B:
(B*C)*D=84+60=144
B*(C*D)=140+...=vetsi je to urcite
celkove:
A(BCD)=144+30=174
(AB)(CD)=42+140+70=252
(ABC)D=98+40=138
pametova slozitost je O(n^2), casova O(n^3).
-=( uloha s retezci )=-
mam dva retezce, xi najit nejdelsi spolecny potretezec.
S: abaccbaabcabc
T: bbcca
trosku si zmenime zadani: definujeme si fci:
f(i,j) = delka nejdelsiho spolecnyho podretezec retezcu S a T zkracenych na
delky i(retezec S) a j(retezec T).
takze hledame vlastne f(delka S, delka T), to je to puvodni zadani.
co o ni vime:
f(0,0) = 0
ta hodnota se mi muze zvetsit jen pokud se shoduji i ty pridany hodnoty.
f(i,j) = +- f(i-1,j-1)+1 pro S[i]==T[j]
+- f(i-1,j) nebo f(i,j-1) dyz se posledni znak neshoduje
do tabulky:
+--------+--------+-----+-----+-----+-----+-----+-----+-----+-----+
| | neco | a | b | a | a | b | c | b | a |
| | jinyho | | | | | | | | |
+--------+--------+-----+-----+-----+-----+-----+-----+-----+-----+
| neco | | | | | | | | | |
| jinyho | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+--------+--------+-----+-----+-----+-----+-----+-----+-----+-----+
| b | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | <- delka 1
+--------+--------+-----+-----+-----+-----+-----+-----+-----+-----+
| b | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | <- delka 2
+--------+--------+-----+-----+-----+-----+-----+-----+-----+-----+
| a | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 3 | <- delka 3
+--------+--------+-----+-----+-----+-----+-----+-----+-----+-----+
| a | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 3 | 3 | <- delka 4
+--------+--------+-----+-----+-----+-----+-----+-----+-----+=====+
| c | 0 | 1 | 1 | 2 | 3 | 3 | 4 | 4 | 4 | <- delka 5
+--------+--------+-----+-----+-----+-----+-----+-----+-----+=====+
takze nejdelsi spolecny retezec ma delku 4. slozitost je O(n*m) - rozmery
tabulky, co sme museli vyplnit. pametova: nepotrebuju si ji pamatovat celou,
pac mi staci znat jen sousedy. retezc pak najdu tak, ze si pamatuju, jak sem
k tomu konecnymu vysledku dosla: baac.
ZEFEKTIVNOVANI VYPOCTU
05-05-2005
======================
-=( zabraneni opakovanym vypoctum )=-
jednim ze zpusobu je prave pamatovani si predchozich vysledku. to muze i zmenit
slozitost. ale v nekterych pripadech je tech udaji moooc a tak si je nemuzem
pamatovat, treba v dame nebo sachach. tam si muzem pamatovat treba jenom
nektery. ale jak?
cache:
vytvorime si hashovaci tabulku. z te aktualni pozice si spocitame hash. kolize
se neresi, proste se to prepise, pac moznosti si stejne pamatujem jen malo,
takze je skoro jedno, kery. takze si stav zahashujem, najdem v tabulce,
zjistime, zda se shoduji a pripadne to pouzijem a ulozime do tabulky.
-=( prime generovani )=-
treba u erathostenova sita, nebo:
mame kalkulacku se dvama tlacitky, na zacatku je tam 1. jedno tlacitko to cislo
vynasobi 2 a pricte 1 a druhy to vynasobi trema a pricte 1. zjisteme, zda cislo
57 lze na ty kalkulacce vyrobit.
mohlo vzniknout prvni tlacitkem, pac je lichy, ale ne tim druhym. takze
(57-1)/2=28. a co 28? to mohlo vniknout?
ee, to je blbej zpusob, pouzijeme tabulku, kde si budem zaskrtavat cisla, co
mohly vzniknout a jakmile se dostanem za 57, tak se podivame, jestli sme 57
zaskrtli nebo ne a je to.
-=( vypocet hodnoty na zaklade minule )=-
mame radu kladnych cisel
5 8 1 4 7 12 21 7 3 3 3 52 18 11 49 15 7 2 6
existuje v posloupnosti nejaky usek s dannym souctem?
hloupe reseni je projit secky useky O(n^3). lepsi by bylo projit secky zacatky
useky a scitat, dokud neprekrocime soucet. nebo
5+8+1+7 je moc tak zahodime 5 a zbyde nam soucet 21 a pridavame dalsi cisla zas
dokud neprekrocime ten soucet a odebirame to cislo na zacatku pripadne... tim
docilime slozitosti O(n).
-=( predzpracovani )=-
mame matici rozmeru n*m typu boolean a obsahuje 0 nebo 1. ukolem je najit v
matici nejvetsi souvisly obdelnik obsahujici jen 1. kdyz si udelame este jednu
matici a ke kazdymu policku si napisem, kolik je ve sloupecku pod nim
souvislych jednicek, vcetne jeho. pak projdu secky nenulovy policka a pro kazdy
z nich pudu do strany... a budu si pamatovat nejlepsi reseni. O(n^2*m)
B-STROMY
05-12-2005
==========
-=( motivace )=-
a
/ \
b c
/ \ / \
d e f g
/\ /\ ....
...............
mame binarni vyhledavaci stromecek:
X:TYP
L,P:PPrvek
jak vime z prednasek jirovkyho, tak precist jeden prvek nebo celej jeden sektor
vyjde nastejno. rozdelme si strom na stranky:
+-----------+
| a |
| / \ |
| b c |
+--+-----+-----+--+
| / \ | / \ |
| d e|f g |
| /\ /|\ .... |
: ............... :
nevyplati se nam, abysme meli binarni strom, ale spis nakej sirsi. potrebovali
bychom treba AB-STROMECKY.
-=( B-stromy )=-
B-strom stupne n:
+ kazdy vrchol obsahuje maximalne 2n prvku
+ kazdy vrchol krome korene obsahuje minimalne n prvku
+ vrchol, ktery obsahuje m prvku, ma m+1 synu krome listu
+ vsechny listy jsou na stejne urovni
priklad vrcholu:
+----+----+-----+
| 10 | 20 | 100 |
+----+----+-----+---> vetsi nez 100
| | |
v +-+ v
mensi | 20 az 100
nez |
10 |
v
mezi 10
a 20
-=( pridavani )=-
pridavejme do stromu cisla:
5 7 8 1 49 17 95 103 29 38 6 2
mame v koreni:
1 5 7 8
pridavame 49, musime ten strom rezdelit:
+-+
|7|
+-+
/ \
+-+-+ +-+--+
|1|5| |8|49|
+-+-+ +-+--+
pridame 17 a 95:
+-+
|7|
+-+
/ \
+-+-+ +-+--+--+--+
|1|5| |8|17|49|95|
+-+-+ +-+--+--+--+
pridavame 103, ale ta se tam zase nevejde, takze ho zase musime upravit:
+-----+-----+
| 7 | 49 |
+-----+-----+
/ | \
+-+-+ +-+--+ +--+---+
|1|5| |8|17| |95|103|
+-+-+ +-+--+ +--+---+
dale 29 a 38, 6:
+--------+--------+
| 7 | 49 |
+--------+--------+
/ | \
+-+-+-+ +-+--+--+--+ +--+---+
|1|5|6| |8|17|29|38| |95|103|
+-+-+-+ +-+--+--+--+ +--+---+
atd...
=> b-strom roste tak, ze se koren posouva nahoru
-=( mazani )=-
zacneme mazanim v listech. nektery musem smazat jen tak, bez problemu. muzeme
ale zpusobit, ze nektery vrchol potom nebude naplneny, takze ho musime spojit
s jeho bratrem. kdyby jich pak bylo vic nez 2n, tak je prelijem s otcem.
kdyz budeme mazat prvek, ktery neni v listu:
kdyz jsme v levelu hned nad listy, prvek si muze pujcit od sveho syna.
v ostatnich pridadech postupujeme stejne jako u binarnich stromu.
-=( slozitost )=-
strom ma logaritmickou vysku, takze secky operace mazani, pridavani a hledani
muzeme provadet v O(log n).
-=( 2-3 stromy )=-
specialni pripad b-stromu.
HLEDANI K-TEHO PRVKU
05-12-2005
====================
mame v poli n jakychkoli hodnot, ktere se daji porovnavat. chceme z nich najit
k-tu prvek podle velikosti. jak na to?
-=( 1 - hloupe reseni )=-
muzeme najit prvni nejmensi prvek, zahodim ho a hledame druhy nejmensi... takze
je treba (n-1)+(n-2)+...+(n-k). pro velky k je to ale osklivy => O(n^2)
-=( 2 - trideni )=-
nebo muzeme pole setridit => O(n*log n)
-=( 3 - halda )=-
nebo muzeme sestavit haldu O(n) a (k-1)krat vezmem nejmensi prvek a zahodime ho
a opravime haldu, takze je to zase O(n*log n), ale pro maly k je to lepsi.
-=( 3' - vylepesna halda )=-
dalsi moznost je udelat si haldu zase, ale jen z (n-k+1) prvku
=> O(n-k-1 + (k-1)log(n-k+1))
-=( 4 - a la quicksort )=-
vybereme si pivota a pole rozdelime na prvky mensi a vetsi rovny pivotu.
hledame k-ty prvek, podivame se na velikosti casti mensich a vetsich prvku a
podle toho postupujeme rekurzivne dale ve vybrany casti. od qs se to lisi tak,
ze qs potrebuje setridit obe casti, zatimco my chceme jen jeden prvek. takze
kdyz se nam bude dobre darit delit na poloviny, tak nejdriv prochazime vsechny,
pak jen polovinu atd... pocet prvku se nam zuzi na polovinu, takze vubec
nepotrebujeme rekurzu, lze to delat pekne i cyklem. => O(2n)
ale kdyz se nam to nepovede pekne rozdelit, tak budeme prochazet n prvku, potom
(n-1), pak (n-2) atd... => O(n^2)
takze bysme potrebovali este nak najit toho mediana, coz umime z prednasky
algoritmu.
dukaz:
dokazme si, ze k-ty prvek z n prvku lze najit na 28n kroku. :)
dybych porovnavala kady prvek s kazdym, tak je muzu setridit za n(n-1)/2 casu
=> pro n<=57 to plati (dosadme si 57 do vzorce :)
1/ cisla rozdelime do sedmic. kazdou sedmici usporadame, pri porovnavani kazdy
s kazdym:
7*6/2=21 // na jednu sedmici
n/7*21=3n // krat pocet sedmic
=> potrebujeme na to 3n casu
z kazde sedmice si urcime median, to je ten prvek, co je uprostred, tedy
ctvrty v poradi. to de konstatne ted. median oznacime m.
2/ z tech vsech medianu najdeme prostredni hodnotu. jak to udelame? medianu
mame n/7 cisel, z nich xi prostredni hodnotu. to zvladneme za
n/7 * 28 = 4n
ten median medianu si oznacime M.
3/ vsech n prvku rozdelime do 3 skupin: mensi nez M(skupina A),
rovny M(skupina B) a vetsin nez M(skupina C). ted sme spotrebovali uz 8 n,
este zbyva 20 :)
obrazek(ty sedmice):
+--+--+--+--+--+.........+--+
|# |# |# |# |# | | |
|# |# |# |# |# | | |
|# |# |# |# |# | | |
|m |m |m |m |M | |m |
| | | | | |@ ...... |@ |
| | | | | |@ ... |@ |
| | | | | |@@ ...@|@ |
+--+--+--+--+--+.........+--+
k<=|A| => k-ty prvek je v A
|A|<k<=|A|+|B| => k-ty prvek je M
|A|+|B|k-ty prvek je v C
vime, ze prvky oznaceme jako # jsou urcite mensi rovny M. podobne @ jsou
vetsi rovny M.
takze ted to hledani bude probihat na (n-n/7/2)prvcich. takze:
|A|<=(n-2n/7)=5n/7
vyuzijme predpoklad:
28*5n/7=20n
takze suma sumarum 28n. _
|_|
ZKOUSKOVY PRIKLAD
05-19-2005
=================
-=( zadani - anketa )=-
program ma zpracovavat vysledky studentske ankety:
vstup(soubory):
+ anketni listky
- predmet, ktereho se tykaji (sting[90])
- ucitel (string[50])
- hodnoceni (1..5)
+ udaje o katedrach a ucitelich
- ucitel (string[50])
- katedra (string[50])
vystup:
+ pro kazdy predmet a ucitele
- prumer hodnoceni
- stredni kvadraticka odchylka
- ma byt setrideno podle ucitelu
+ predchozi soubor setrideny podle kateder
-=( jak by to melo vypadat )=-
- na konci by mela byt jedna a4 shrnuti:
0\ upresneni zadani:
pocet predmetu nebude vetsi nez 5000, ucitelu nebude vic nez 5000, kateder
nebude vic jak 500. anketnich listku muze byt neomezene. pamet pocitace
k dispozici: 1kB.
1\ postrehy(zejmena ty, ktere maji vliv na reseni):
napriklad, ze pro urcite pripady se to da resit jednoduse...
2\ seznam algoritmu, co nas napadly
a algoritmus, ktery sem si vybrala a zduvodneni
3\ reprezentace dat
4\ dekompozice(rozklad programu na casti)
5\ diskuze
kdy to najde a kdy to nenajde lespi reseni... co by kdyby(kdyby mel ucitel
vice, nez jeden predmet)...
- odevzdavat mame secky papiry, i ty pracovni, nikdo je nepouzije proti nam .)
-=( POSTREH - stredni kvadraticka odxylka )=-
sum(xi)
X = -------
N
sum(x_i-X)^2 sum(x_i^2*x_i*X+X^2)
stredni kvadraicka odchylka = ------------ = -------------------- =
N N
sum(x_i^2) sum(x_i^2)
= ---------- - 2*X^2 + X^2 = ---------- - X^2
N N
================
-=( jak to nacpat do pameti )=-
takze pro kazdou dvoji ucitel-predmet (je jich max 25000000) potrebujeme spocitat:
sum(x_i), sum(x_i^2) a N. zkusme si tedy odhadnout, ze jeden ucitek neuci vic, jak
10 predmetu, neni to ale jisty. tim sme snizili pozadavky na velikost 25000. to se
nam ale porad do pameti nevejde. tak je zkusime nejak predspracovat.
rekneme, ze vstupni data jsou textove soubory: jeden listek - jeden radek.
takze si data predzpracujeme. ucitele i predmet si nahradime cislem, to mame 5B na
kazdy listek. ale ani to nam nepomuze, aby se to tam veslo.
+--------+
| listky | je jich N
+--------+
|
|
setridim podle bude nas to stat N*logN casu
ucitel-predmet (pouziji vnejsi treideni, neni
| nutno na to psat tu preceduru)
v
+-----------+
| setridene |
| listky +-------> scitani sum(x_i),
+-----------+ sum(x_i^2) a N
|
|
v
+--------------+
| vystup 1 | tolik zaznamu,
+--------------+ kolik je dvojic
| ucitel-predmet
+---------------------------+
|
takze ted to ma tu vyhodu, ze v urcitych usecich mame stejne ucitele a stejne |
predmety. jak to pozname? musime si to pamatovat. mame na to pamet? mameee :) |
druhy vystupni soubor ptrebujeme setridit podle kateder. jak na to? pro |
kazdyho ucitele si to vyhledavat, to je vrazedny. nebo si nacist ten soubor |
do pameti? to ma mega :/ takze ne. soubor vystup 1 mame, setrideny podle |
ucitelu. tedy: (predpokladame, ze ucitel patri jen do jedny katedry, jinak by |
to nemelo reseni - upresneni zadani) setridime katedry podle ucitelu: |
|
+---------+ |
| katedry | je jich M |
+---------+ |
| |
| |
vnejsi zase M*logM |
trideni |
| |
v |
+---------+ |
| ucitele |---------------------->+<---------------+
+---------+ |
pridat pocet dvojic
katedru ucite-predmet
| +|M|
|
|
v
+-----------+
| vystup 1 | |UP|
| + katedra |
+-----------+
|
|
v
trideni |UP|log|UP|
podle kateder
|
|
v
+------------------+
| vystup setrideny |
| podle kateder |
+------------------+
|
|
v
vyhodit |UP|
katedru
|
|
v
+----------+
| vystup 2 |
+----------+
OBJEKTY
05-19-2005
==========
-=( trida - class )=-
- instance (object)
deklarace pomoci klicoveho slova class, vsecky jsou vytvareny na halde.
var TForm // odkaz na objekt
vsecko sou to ukazatele, ale narozdil od TP nepiseme tam ty sipky ^.
deklarace tridy muze obsahovat:
- pole (fields)
- metody
- vlastnosti (property)
urovne ochrany:
- private (viditelny jen v tom objektu, ne v odvozenych)
- protected (viditelne pouze v ty tride nebo v odvozenych - v ramci jednoho
zdrojaku)
- public (uplne verejny)
- published
- kdyz odvozujeme novy objekt, tak zdedi secko i s temi urovnemi ochrany,
nemuzeme utajit neco, co bylo verejne, ale opacne jo.
- je zvykem, ze dyz mame nakou vlastnost (property), tak znacit GetX a SetX
procedury, ktere umoznuji cteni a psani. F-kem zacinaji privatni promenny
k vlastnostem. za klicove slovo default muzu napsat implicitni hodnotu.
to znamena, ze pokud se hodnota rovna ty defaultni, tak se nezapisuje.
- metody:
staticke, virtualni, dynamicke (funguji jako virtualni, ale kazda trida si
patamuje jen metody, co zmenila - je to pomalejsi, ale setri pamet. typicky
se pouzivaji na obsluhu udalosti)
- v delfach neni nasobna dedicnost, takze dedit muzeme jen od jednoho predka
- interface: skupina metod
- muzu sice dedit jen od jedenoho predka, ale muzu mit libovolny pocet
interfacu.
info: www.oreilly.com/delphi/chapter/ch02.html
0 komentářů:
Okomentovat