Algorytmika praktyczna - nie tylko ...

[ Pobierz całość w formacie PDF ]
Uniwersytet Warszawski
Wydział Matematyki,InformatykiiMechaniki
Piotr Sta«czyk
Nr albumu: 209291
Algorytmika praktyczna w
konkursach Informatycznych
Praca magisterska
na kierunku INFORMATYKA
w zakresie ALGORYTMIKA
Praca wykonana pod kierunkiem
dra hab. Krzysztofa Diksa
Instytut Informatyki
Czerwiec 2006
O±wiadczenie kieruj
a
cego prac
a
O±wiadczam,»eniniejszapracazostałaprzygotowanapodmoimkierunkiemistwier-
dzam, »e spełnia ona warunki do przedstawienia jej w postepowaniu o nadanie tytułu
zawodowego.
Data
Podpis kieruj acego prac a
O±wiadczenie autora (autorów) pracy
‘wiadom odpowiedzialno±ci prawnej o±wiadczam, »e niniejsza praca dyplomowa
została napisana przeze mnie samodzielnie i nie zawiera tre±ci uzyskanych w sposób
niezgodny z obowi azuj acymi przepisami.
O±wiadczam równie», »e przedstawiona praca nie była wcze±niej przedmiotem pro-
cedur zwi azanych z uzyskaniem tytułu zawodowego w wy»szej uczelni.
O±wiadczam ponadto, »e niniejsza wersja pracy jest identyczna z zał aczon a wersj a
elektroniczn a.
Data
Podpis autora (autorów) pracy
Streszczenie
Brak
Słowa kluczowe
Brak
Dziedzina pracy (kody wg programu Socrates-Erasmus)
11.3 Informatyka
Klasyfikacja tematyczna
Brak
Spis tre±ci
1. Przedmowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1. Struktura ksi¸a»ki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2. Wymagania wst¦pne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3. Podzi¦kowania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4. Nagłówki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2. Algorytmy Grafowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1. Struktura grafu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2. Przeszukiwanie grafu wszerz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3. Przeszukiwanie grafu w gł¸ab. . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4. Silnie spójne składowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5. Sortowanie topologiczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.6. Acykliczno±¢ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.7. Dwuspójne składowe, mosty i punkty artykulacji . . . . . . . . . . . . . . . . 42
2.8. ‘cie»ka i cykl Eulera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.9. Minimalne drzewo rozpinaj¸ace . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.10.Algorytm Dijkstry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.11.Algorytm Bellmana - Forda . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.12.Maksymalny przepływ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.12.1. Maksymalny przepływ metod¸a Dinica . . . . . . . . . . . . . . . . . . 64
2.12.2. Maksymalny przepływ dla kraw¦dzi jednostkowych . . . . . . . . . . . 68
2.12.3. Najta«szy, maksymalny przepływ dla kraw¦dzi jednostkowych. . . . . 70
2.13.Maksymalne skojarzenie w grafie dwudzielnym . . . . . . . . . . . . . . . . . 73
2.13.1. Dwudzielno±¢ grafu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.13.2. Maksymalne skojarzenie w grafie dwudzielnym w czasie O(n
(n+m)) 76
2.13.3. Maksymalne skojarzenie wgrafie dwudzielnymwczasie O((n+m)
p
3. Geometria obliczeniowa na płaszczy¹nie . . . . . . . . . . . . . . . . . . . . . 87
3.1. Odległo±¢ punktu od prostej . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.2. Powierzchnia wielok¸ata. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.3. Przynale»no±¢ punktu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.4. Punkty przeci¦cia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.5. Trzy punkty — okr¸ag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.6. Wypukła otoczka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.7. Sortowanie k¸atowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.8. Para najbli»szych punktów . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3
n) 78
2.13.4. Najdro»sze skojarzenie w grafie dwudzielnym . . . . . . . . . . . . . . 82
[ Pobierz całość w formacie PDF ]