Robert Sedgewick, Kevin Wayne algorytmy. wydanie iv helion.pdf

Ty t uł oryginału: Algorithms (4th Edition)

Tłumaczenie: Tomasz Walczak

ISBN: 978-83-246-3536-8

Authorized translation from the English language edition, entitled: Algorithms, 4th Edition

ISBN 032157351X, by Robert Sedgewick and Kevin Wayne, published by Pearson Education, Inc,

means, electronic or mechanical, including photocopying, recording or by any information storage

retrieval system, without permission from Pearson Education Inc.

Polish language edition published by Helion S.A.

means, electronic or mechanical, including photocopying, recording or by any information storage

retrieval system, without permission from the Publisher.

Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej

publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną,

fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje

naruszenie praw autorskich niniejszej publikacji.

Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich

właścicieli.

Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje

były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za

związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz Wydawnictwo

HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z

wykorzystania informacji zawartych w książce.

Wydawnictwo HELION

ul. Kościuszki 1c, 44-100 GLIWICE

tel. 32 231 22 19, 32 230 98 63

e-mail: helion@helion.pl

WWW: http://helion.pl (księgarnia internetowa, katalog książek)

Pliki z przykładami omawianymi w książce można znaleźć pod adresem:

ftp://ftp.helion.pl/przyklady/algor4.zip

Drogi Czytelniku!

Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres

http://helion.pl/user/opinie/algor4

Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.

Printed in Poland.

• Kup książkę

• Poleć książkę

• Oceń książkę

• Księgarnia internetowa

• Lubię to! » Nasza społeczność

SPIS TRE CI

Przedmowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1 Podstawy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.1

Podstawowy model programowania

1.2

Abstrakcja danych

1.3

Wielozbiory, kolejki i stosy

132

1.4

Analizy algorytmów

184

1.5

Studium przypadku — problem Union-Find

228

2 Sortowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

2.1

Podstawowe metody sortowania

256

2.2

Sortowanie przez scalanie

282

2.3

Sortowanie szybkie

300

2.4

Kolejki priorytetowe

320

2.5

Zastosowania

348

3 Wyszukiwanie . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

3.1

Tablice symboli

374

3.2

Drzewa wyszukiwa binarnych

408

3.3

Zbalansowane drzewa wyszukiwa

436

3.4

Tablice z haszowaniem

470

3.5

Zastosowania

498

Poleć książkę

Kup książkę

4 Grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526

4.1

Grafy nieskierowane

530

4.2

Grafy skierowane

578

4.3

Minimalne drzewa rozpinajce

616

4.4

Najkrótsze cieki

650

5 Łacuchy znaków . . . . . . . . . . . . . . . . . . . . . . . . . 706

5.1

Sortowanie łacuchów znaków

714

5.2

Drzewa trie

742

5.3

Wyszukiwanie podłacuchów

770

5.4

Wyraenia regularne

800

5.5

Kompresja danych

822

6 Kontekst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864

Algorytmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944

Klienty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945

Skorowidz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 946

Poleć książkę

Kup książkę

S ortowanie to proces porz dkowania obiektów w logiczny sposób. Przykładowo,

na wydruku dla u ytkownika karty kredytowej transakcje s uporz dkowane

chronologicznie. Kolejno ta została prawdopodobnie wyznaczona przez algo-

rytm sortowania. W pocz tkowym okresie rozwoju informatyki szacowano, e do 30%

wszystkich cykli procesora po wi canych jest na sortowanie. To, e obecnie odsetek

ten jest ni szy, wynika z tego, i algorytmy sortowania s stosunkowo wydajne, a nie ze

zmniejszenia znaczenia tej operacji. Wszechobecno komputerów sprawia, e dost p-

nych jest mnóstwo danych, a pierwszym krokiem przy ich organizowaniu jest cz sto

sortowanie. We wszystkich systemach komputerowych istniej implementacje algoryt-

mów sortowania dost pne dla systemu i u ytkowników.

S trzy praktyczne powody, dla których warto pozna algorytmy sortowania

(mimo e mo na zastosowa sortowanie systemowe).

Analiza algorytmów sortowania jest solidnym wprowadzeniem do podej cia

u ywanego przy porównywaniu wydajno ci algorytmów w tej ksi ce.

Podobne techniki s skuteczne w rozwi zywaniu innych problemów.

Algorytmy sortowania cz sto słu za punkt wyj cia przy rozwi zywaniu in-

nych problemów.

Wa niejsze od tych praktycznych powodów jest to, e algorytmy sortowania s ele-

ganckie, klasyczne i skuteczne.

Sortowanie odgrywa kluczow rol w komercyjnym przetwarzaniu danych

i współczesnych obliczeniach naukowych. Istnieje wiele zastosowa takich algoryt-

mów w obszarze przetwarzania transakcji, optymalizacji kombinatorycznej, astro-

zyki, dynamiki molekularnej, lingwistyki, bada nad genomem, prognozowania

pogody itd. Jeden z algorytmów sortowania (sortowanie szybkie, opisane w -

. ) został uznany za jeden z 10 najwa niejszych algorytmów XX wieku

w dziedzinie nauki i in ynierii.

W tym rozdziale omówiono kilka klasycznych metod sortowania i wydajn imple-

mentacj wa nego typu danych — kolejki priorytetowej. Opisano teoretyczne pod-

stawy porównywania algorytmów sortowania, a rozdział zako czono analiz zasto-

sowa sortowania i kolejek priorytetowych.



255

Poleć książkę

Kup książkę

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: