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: 22 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

Przedmowσ

PredItorswrσzzkomentσrzσmiopisującymiichwykorzystσniejestzσmieszczonywdo-

dσtkuAnσlistinguAº1ºSσmenσgłówki,pousunięciuznichkomentσrzy,sąprzedstσ-

wionenσlistinguAº2º

Oprócznσgłówkówpodstσwowychistniejerównieżwieleinnychskrótów,któreokσzu-

jąsiępomocnepodczσsrozwiązywσniσzσdσńºOmσwiσnσwtejksiążcebiblioteczkσ,pozσ

nσgłówkσmipodstσwowymi,zσwierσtσkżedodσtkowemσkrσumieszczσnetylkowtych

progrσmσch,któreznichkorzystσjąºIchlistσjestpodσnσnσlistinguAº3ºWprezento-

wσnychprogrσmσchbędąodwołσniσzσrównodotychpodstσwowych,jσkidodσtkowych

nσgłówków,σleichdeﬁnicjeniebędąumieszczonewimplementowσnychprogrσmσchT

czytelnikpowiniensσmpσmiętσćokσżdorσzowymichdopisσniuºDziękitσkiemupodej-

ściukodyźródłoweprzedstσwiσnychwksiążceσlgorytmówsąkrótsze,σczytelniknie

musizσkσżdymrσzemσnσlizowσćpowtσrzσjącychsięfrσgmentówkoduº

Znσnesąsytuσcje,gdyniektórzyzσwodnicytworzyliprzyużyciumσkrwłσsne,specy-

ﬁcznejęzykiprogrσmowσniσumożliwiσjąceszybkiepisσnieprogrσmówºTσkiepodejście

wymσgσ,niestety,przepisσniσznσcznejilościkodu,zσnimprzystąpisiędowłσściwego

rozwiązywσniσproblemuºWprzypσdkukonkursóworgσnizowσnychprzezInternetzσsto-

sowσnietσkiejmetodyokσzujesięjednσkbσrdzowygodneºWdodσtkuBznσjdujesię

przykłσdowenśrodowiskoπprogrσmistycznewykorzystywσnewkonkursieTopCoderprzez

ErykσKopczyńskiegoºJestonodośćrozbudowσne,dlσtegoteżwinnychkonkursσch(tσ-

kichjσkACMICPC)jestpoprostunieprzydσtneº

Podziękowania

Opisywσnσwtejksiążcebiblioteczkσσlgorytmicznσzostσłσstworzonσprzywspółprσcy

zmoimikolegσmizzespołuWIrsIwPredItorsTMσrkiemCygσnemiMσrcinemPilip-

czukiemºSerdecznieimdziękujęzσtenwspólnytrudºChciσłbymrównieżpodziękowσć

TomσszowiIdziσszkowi,któregokilkσnchwytówprogrσmistycznychπznσlσzłosięwnσ-

szejbiblioteczce,orσzErykowiKopczyńskiemu,któryzgodziłsięnσopublikowσniezbioru

swoichmσkrużywσnychwkonkursieTopCoderº

JestemniezmierniewdzięcznyTomσszowiCzσjce,AndrzejowiGąsienicy-Sσmkowi,

TomσszowiMσlesińskiemu,KrzysztofowiOnσkowiiMσrcinowiStefσniσkowizσwyrσże-

niezgodynσpublikσcjęichndobrychrσdπ,którychudzieliliswoimmłodszymkolegom

zUniwersytetuWσrszσwskiego,biorącymudziσłwkonkursieACMICPCºZostσłyone

zebrσnewdodσtkuCtejksiążkiº

Wσżnymwyzwσniempodczσsgromσdzeniσmσteriσłówdoksiążkibyłowybierσnie

odpowiednichzσdσńzróżnychserwisówinternetowychºLiczbσdostępnychzσdσńjest

ogromnσ(wmomenciepisσniσtegotekstuserwisVσllσdolidProgrσmmingContestSite

zσwierσłponσddwσtysiącezσdσń)ºChciσłbympodziękowσćJσkubowiRσdoszewskiemu

zσudzieleniecennychwskσzówekdotyczącychwyboruzσdσńº

SzczególnepodziękowσniσnσleżąsięprofesorowiKrzysztofowiDiksowiTnσszemu

wykłσdowcyiwielkiemuprzyjσcielowi,którywytrwσleopiekowσłsięnσmiistwσrzσł

wσrunkipozwσlσjącenσefektywneprzygotowσniσnσszychdrużyndozσwodówºNiniejszσ

książkσpowstσłσpodjegożyczliwymnσdzoremº

Brak wyników

Algorytmika praktyczna

Treść książki

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