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 07 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

30Kombinatoryka

128

3º1ºPermutσcjewkolejnościσntyleksykogrσﬁcznejºººººººººººººººº128

3º2ºPermutσcjeTminimσlnσliczbσtrσnspozycjiºººººººººººººººº130

3º3ºPermutσcjeTminimσlnσliczbσtrσnspozycjisąsiednichºººººººººº132

3º4ºWszystkiepodzbioryzbioruºººººººººººººººººººººººººº135

3º5ºPodzbioryk-elementowewkolejnościleksykogrσﬁcznejººººººººººº137

3º6ºPodziσłyzbioruzużyciemminimσlnejliczbyzmiσnººººººººººººº138

3º7ºPodziσłyliczbywkolejnościσntyleksykogrσﬁcznejºººººººººººººº140

40Teorialiczb

142

4º1ºWspółczynnikdwumiσnowyºººººººººººººººººººººººººº142

4º2ºNσjwiększywspólnydzielnikºººººººººººººººººººººººººº144

4º3ºOdwrotnośćmodulσrnσºººººººººººººººººººººººººººº147

4º4ºKongruencjeººººººººººººººººººººººººººººººººººº149

4º5ºSzybkiepotęgowσniemodulσrneºººººººººººººººººººººººº152

4º6ºSitoErσtostenesσºººººººººººººººººººººººººººººººº154

4º7ºListσliczbpierwszychººººººººººººººººººººººººººººº155

4º8ºTestpierwszościººººººººººººººººººººººººººººººººº157

4º9ºArytmetykσwielkichliczbººººººººººººººººººººººººººº160

50Strukturydanych

178

5º1ºStrukturσdσnychdoreprezentσcjizbiorówrozłącznychººººººººººº178

5º2ºDrzewσwyszukiwσńbinσrnychºººººººººººººººººººººººº182

5º2º1ºDrzewσmσksimówººººººººººººººººººººººººººº185

5º2º2ºDrzewσlicznikoweººººººººººººººººººººººººººº187

5º2º3ºDrzewσpozycyjneººººººººººººººººººººººººººº189

5º2º4ºDrzewσpokrycioweººººººººººººººººººººººººººº192

5º3ºBinσrnedrzewσstσtycznedynσmicznieσlokowσneºººººººººººººº195

5º4ºWzbogσcσnedrzewσbinσrneºººººººººººººººººººººººººº200

60Algorytmytekstowe

212

6º1ºAlgorytmKMPººººººººººººººººººººººººººººººººº212

6º2ºMinimσlnyokressłowσººººººººººººººººººººººººººººº216

6º3ºKMPdlσwieluwzorców(σlgorytmAho-Corσsick)ººººººººººººº217

6º4ºPromieniepσlindromówwsłowieººººººººººººººººººººººº223

6º5ºDrzewσsuﬁksoweºººººººººººººººººººººººººººººººº226

6º5º1ºLiczbσwystąpieńwzorcσwtekścieºººººººººººººººººº230

6º5º2ºLiczbσróżnychpodsłówsłowσººººººººººººººººººººº232

6º5º3ºNσjdłuższepodsłowowystępującenrσzyºººººººººººººº233

6º6ºMσksymσlnyleksykogrσﬁczniesuﬁksººººººººººººººººººººº234

6º7ºRównowσżnośćcyklicznσºººººººººººººººººººººººººººº235

6º8ºMinimσlnσleksykogrσﬁczniecyklicznośćsłowσºººººººººººººººº237

Brak wyników

Algorytmika praktyczna

Treść książki

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