Algoritmi
Miodrag ivkovi
Matematiqki fakultet, Beograd
E-mail address
:
[email protected].
iv
PREDGOVOR
rexea. Ova kiga trebalo bi da prui argumente da su algoritmi elegantna
i vana disciplina.
U prvom delu kige, u poglav ima 1-4, dat je uvodni materijal o matema-
tiqkoj indukciji, analizi algoritama, strukturama podataka, kao i primeri
konstrukcije algoritama pomou matematiqke indukcije. Narednih qetiri
poglav a 5-8 bave se algoritmima za rexavae problema u pojedinim oblas-
tima: u vezi sa nizovima i skupovima, grafovima, iz algebre i geometrije.
Poglav e 9 daje osnovne pojmove iz kriptografije, oblasti veoma znaqajne
kroz celu udsku istoriju, u kojoj algoritmi imaju veliku primenu. Reduk-
cijama, odnosno meusobnim svoeima algoritama, posveeno je poglav e 10,
a
NP
-kompletni problemi analizirani su u poglav u 11. Poslede poglav e
sadri uvod u paralelne algoritme.
Preliminarna verzija kige je isprav ena i dopuena zadacima sa rexe-
ima. Veliki broj grexaka otkrili su studenti, na qemu im se autor zahva u-
je. Autor je unapred zahvalan i za sve budue primedbe i sugestije na sadraj
kige. Poruke se mogu slati na adresu
[email protected].
. Tei zadaci
oznaqeni su zvezdicom. U rexavau zadataka uqestvovali su i studenti, xto je
nastavu qinilo interesantnijom. Autor je zahvalan naroqito postdiplomcima
A. Samariu i M. Vugdeliji, koji su rexili vei broj zadataka.
Za korisne primedbe i sugestije autor posebnu zahvalnost duguje recen-
zentima.
Miodrag ivkovi
Sadraj
Predgovor
iii
Poglav e
1. Matematiqka indukcija
1
1.1. Uvod
1
1.2. Dva jednostavna primera
2
1.3. Brojae oblasti na koje je pode ena ravan
2
1.4. Problem sa bojeem ravni
3
1.5. Primer sa sumiraem
4
1.6. Ojlerova formula
4
1.7. Grejovi kodovi
5
1.8. Nalaee disjunktnih puteva u grafu
7
1.9. Nejednakost izmeu aritmetiqke i geometrijske sredine
9
1.10. Invarijanta pet e | dokaz ispravnosti algoritma
10
1.11. Najqexe grexke
11
1.12. Rezime
12
Zadaci
12
Glava 2. Analiza algoritama
15
2.1. Uvod
15
2.2. Asimptotska oznaka
O
16
2.3. Vremenska i prostorna sloenost
18
2.4. Sumirae
18
2.5. Diferencne jednaqine
20
2.6. Rezime
27
Zadaci
27
Glava 3. Strukture podataka
31
3.1. Elementarne strukture podataka
32
3.2. Stabla
34
3.3. Hip
36
3.4. Binarno stablo pretrage
38
3.5. AVL stabla
44
3.6. Hex tabele
47
3.7. Problem formiraa unija
50
3.8. Grafovi
52
3.9. Rezime
53
v
SADRAJ
vii
7.1. Uvod
181
7.2. Utvrivae da li zadata taqka pripada mnogouglu
182
7.3. Konstrukcija prostog mnogougla
185
7.4. Konveksni omotaq
186
7.5. Najblii par taqaka
192
7.6. Preseci horizontalnih i vertikalnih dui
196
7.7. Rezime
200
Zadaci
201
Glava 8. Algebarski algoritmi
205
8.1. Uvod
205
8.2. Stepenovae
206
8.3. Euklidov algoritam
207
8.4. Mnoee polinoma
210
8.5. Mnoee matrica
211
8.6. Brza Furijeova transformacija
214
8.7. Rezime
219
Zadaci
220
Glava 9. Primene u kriptografiji
223
9.1. Uvod
223
9.2. Klasiqna kriptografija
227
9.3. Sluqajna xifra
229
9.4.
DES
230
9.5.
RSA
240
9.6. Rezime
243
Zadaci
243
Glava 10. Redukcije
245
10.1. Uvod
245
10.2. Primeri redukcija
246
10.3. Redukcije na problem linearnog programiraa
249
10.4. Primena redukcija na nalaee doih granica
253
10.5. Uobiqajene grexke
256
10.6. Rezime
258
Zadaci
258
Glava 11.
NP
-kompletnost
261
11.1. Uvod
261
11.2. Redukcije polinomijalne vremenske sloenosti
262
11.3. Nedeterminizam i Kukova teorema
264
11.4. Primeri dokaza
NP
-kompletnosti
272
11.5. Tehnike za rad sa
NP
-kompletnim problemima
282
11.6. Rezime
293
Zadaci
293
