Algorytmika praktyczna

Piotr Stańczyk

Uzyskaj dostęp

Zakup książkę

ISBN/ISSN:

978-83-01-15821-7

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2009

Liczba stron:

312

XML:ISBN/ISSN:

ONIX MARC21

Bibliografia:

Stańczyk, Piotr. Algorytmika praktyczna. Red. . Warszawa: Wydawnictwo Naukowe PWN, 2009, 312 s. ISBN 978-83-01-15821-7

Bibliografia refWorks:

RT Book, Whole

SR Electronic(1)

A1 Stańczyk, P.

T1 Algorytmika praktyczna

PB Wydawnictwo Naukowe PWN

PP Warszawa

YR 2009

SN 978-83-01-15821-7

Bibliografia BibTex:

@Book{ 1082, author = "Stańczyk, Piotr", editor = "", title = "Algorytmika praktyczna", publisher = "Wydawnictwo Naukowe PWN", year = "2009", address = "Warszawa", isbn = "978-83-01-15821-7" }

Bibliografia endNote:

TY - BOOK

AU - Stańczyk, Piotr

ED -

TI - Algorytmika praktyczna

PB - Wydawnictwo Naukowe PWN

CY - Warszawa

PY - 2009

SN - 978-83-01-15821-7

ER -

Netografia (standard APA):

Stańczyk, Piotr. Algorytmika praktyczna [baza danych online] Warszawa: Wydawnictwo Naukowe PWN, 2009 [dostęp: 03 05 2024]. Dostęp w Ibuk Libra: https://libra.ibuk.pl/reader/algorytmika-praktyczna-piotr-stanczyk-1082.

informatyka, programowanie, zadania, zadania programistyczne, algorytm, algorytmika, zawody, konkursy

Książka ta różni się od znanych na polskim rynku pozycji poświęconych algorytmice, dotyczy bowiem jej strony praktycznej. Taki sposób potraktowania tego działu informatyki wynika z coraz większego zainteresowania zarówno uczniów, jak i studentów u...

Więcej

ISBN/ISSN:

978-83-01-15821-7

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2009

Liczba stron:

312

XML:ISBN/ISSN:

ONIX MARC21

Słowo wstępne10
Przedmowa12
1. Algorytmy grafowe16
1.1. Reprezentacja grafu17
1.2. Przeszukiwanie grafu wszerz21
1.3. Przeszukiwanie grafu w głąb26
1.4. Silnie spójne składowe32
1.5. Sortowanie topologiczne39
1.6. Acykliczność42
1.7. Mosty, punkty artykulacji i dwuspójnie składowe45
1.8. Ścieżka i cykl Eulera52
1.9. Minimalne drzewo rozpinające58
1.10. Algorytm Dijkstry61
1.11. Algorytm Bellmana-Forda66
1.12. Maksymalny przepływ68
1.12.1. Maksymalny przepły wyznaczany metodą Dinica69
1.12.2. maksymalny przepływ dla krawędzi jednostkowych73
1.12.3. Najtańszy maksymalny przepływ dla krawędzi jednostkowych75
1.13. Maksymalne skojarzenie w grafie dwudzielnym78
1.13.1. Dwudzielność grafu79
1.13.2. Maksymalne skojarzenie w grafie dwudzielnym w czasie O (n(n+m))82
1.13.3. Maksymalne skojarzenie w grafie dwudzielnym w czasie O((n+m)n^1/2)84
1.13.4. Najdroższe skojarzenie w grafie dwudzielnym87
2. Geometria obliczeniowa na płaszczyźnie92
2.1. Odległość punktu od prostej96
2.2. Pole wielokąta97
2.3. Przynależność punktu do figury99
2.4. Punkty przecięcia106
2.5. Trzy punkty - okrąg115
2.6. Sortowanie kątowe117
2.7. Otoczka wypukła121
2.8. Para najbliższych punktów124
3. Kombinatoryka129
3.1. Permutacje w kolejności antyleksykograficznej129
3.2. Permutacje - minimalna liczba transpozycji131
3.3. Permutacje - minimalna liczba transpozycji sąsiednich133
3.4. Wszystkie podzbiory zbioru136
3.5. Podzbiory k-elementowe w kolejności leksykograficznej138
3.6. Podziały zbioru z użyciem minimalnej liczby zmian139
3.7. Podziały liczby w kolejności antyleksykograficznej141
4. Teoria liczb143
4.1. Współczynnik dwumianowy143
4.2. Największy wspólny dzielnik145
4.3. Odwrotność modularna148
4.4. Kongruencje150
4.5. Szybkie potęgowanie modularne153
4.6. Sito Eratostenesa155
4.7. Lista liczb pierwszych156
4.8. Test pierwszości158
4.9. Arytmetyka wielkich liczb161
5. Struktury danych179
5.1. Struktura danych do reprezentacji zbiorów rozłącznych179
5.2. Drzewa wyszukiwań binarnych183
5.2.1. Drzewa maksimów186
5.2.2. Drzewa licznikowe188
5.2.3. Drzewa pozycyjne190
5.2.4. Drzewa pokryciowe193
5.3. Binarne drzewa statyczne dynamicznie alokowane196
5.4. Wzbogacane drzewa binarne201
6. Algorytmy tekstowe213
6.1. Algorytm KMP213
6.2. Minimalny okres słowa217
6.3. KMP dla wielu wzorców (algorytm Aho-Corasick)218
6.4. Promienie palindromów w słowie224
6.5. Drzewa sufiksowe227
6.5.1. Liczba wystąpień wzorca w tekście231
6.5.2. Liczba różnych podsłów słowa233
6.5.3. Najdłuższe podsłowo występujące n razy234
6.6. Maksymalny leksykograficznie sufiks235
6.7. Równoważność cykliczna236
6.8. Minimalna leksykograficznie cykliczność słowa238
7. Algebra liniowa241
7.1. Eliminacja Gaussa241
7.1.1. Eliminacja Gaussa w Z₂242
7.1.2. Eliminacja Gaussa w Z_p245
7.2. Programowanie liniowe249
8. Elementy strategii podczas zawodów254
8.1. Szacowanie oczekiwanej złożoności czasowej254
8.2. Strategia pracy w drużynie256
8.3. Szablon259
8.4. Plik Makefile260
8.5. Parametry kompilacji programów260
8.5.1. Parametr - Weffc++261
8.5.2. Parametr - Wformat263
8.5.3. Parametr - Wshadow264
8.5.4. Parametr - Wsequence-point265
8.5.5. Parametr - Wunused268
8.5.6. Parametr - Wuninitialized269
8.5.7. Parametr Wfloat-equal270
8.6. Nieustanny time-limit271
8.6.1. Eliminacja dzielenia272
8.6.2. Wczytywanie danych wejściowych272
8.6.3. Wstawki asemblerowe i kompilacja z optymalizacjami274
8.6.4. Lepsze wykorzystanie pamięci podręcznej275
8.6.5. Przetwarzanie wstępne276
Wskazówki do zadań279
A. Nagłówki stosowane w programach293
Dodatki293
B. Nagłównki Eryka Kopczyńskiego na konkurs TopCoder296
C. Sposoby na sukces w zawodach300
D. Wykaz zadań na programowanie dynamiczne305
E. Wykaz zadań na programowanie zachłanne306
F. Wykaz przykładowych zadań307
Literatura308
Indeks310

Spistreści

Słowowstępne

Przedmowa

10Algorytmygrafowe

1º1ºReprezentσcjσgrσfuºººººººººººººººººººººººººººººº16

1º2ºPrzeszukiwσniegrσfuwszerzºººººººººººººººººººººººººº20

1º3ºPrzeszukiwσniegrσfuwgłąbºººººººººººººººººººººººººº25

1º4ºSilniespójneskłσdoweººººººººººººººººººººººººººººº31

1º5ºSortowσnietopologiczneºººººººººººººººººººººººººººº38

1º6ºAcyklicznośćºººººººººººººººººººººººººººººººººº41

1º7ºMosty,punktyσrtykulσcjiidwuspójneskłσdoweºººººººººººººº44

1º8ºScieżkσicyklEulerσºººººººººººººººººººººººººººººº51

1º9ºMinimσlnedrzeworozpinσjąceººººººººººººººººººººººººº57

1º10ºAlgorytmDijkstryººººººººººººººººººººººººººººººº60

1º11ºAlgorytmBellmσnσ-Fordσººººººººººººººººººººººººººº65

1º12ºMσksymσlnyprzepływººººººººººººººººººººººººººººº67

1º12º1ºMσksymσlnyprzepływwyznσczσnymetodąDinicσººººººººº68

1º12º2ºMσksymσlnyprzepływdlσkrσwędzijednostkowychººººººººº72

1º12º3ºNσjtσńszymσksymσlnyprzepływdlσkrσwędzijednostkowychººº74

1º13ºMσksymσlneskojσrzeniewgrσﬁedwudzielnymººººººººººººººº77

1º13º1ºDwudzielnośćgrσfuººººººººººººººººººººººººººº78

1º13º2ºMσksymσlneskojσrzeniewgrσﬁedwudzielnymwczσsie

O(n(n+m))

1º13º3ºMσksymσlneskojσrzeniewgrσﬁedwudzielnym

wczσsie

O((n+m)√n)

ºººººººººººººººººººººººº83

1º13º4ºNσjdroższeskojσrzeniewgrσﬁedwudzielnymºººººººººººº86

20Geometriaobliczeniowanapłaszczyźnie

2º1ºOdległośćpunktuodprostejºººººººººººººººººººººººººº95

2º2ºPolewielokątσºººººººººººººººººººººººººººººººººº96

2º3ºPrzynσleżnośćpunktudoﬁguryºººººººººººººººººººººººº98

2º4ºPunktyprzecięciσºººººººººººººººººººººººººººººººº105

2º5ºTrzypunktyTokrągººººººººººººººººººººººººººººº114

2º6ºSortowσniekątoweººººººººººººººººººººººººººººººº116

2º7ºOtoczkσwypukłσºººººººººººººººººººººººººººººººº120

2º8ºPσrσnσjbliższychpunktówºººººººººººººººººººººººººº123

Brak wyników

Algorytmika praktyczna

Treść książki

Znajdź bibliotekę blisko siebie, i uzyskaj dostęp do ebooka w systemie IBUK Libra