Algorytmy Wydanie IV algor4

[ Pobierz całość w formacie 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,
publishing as Addison Wesley, Copyright © 2011 by Pearson Education, Inc.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any
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.
Copyright © 2012
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any
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
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
Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.
Printed in Poland.
•
Kup książkę
•
Poleć książkę
•
Oceń książkę
•
Księgarnia internetowa
SPIS TRE
CI
Przedmowa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1
Podstawy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1
Podstawowy model programowania
20
1.2
Abstrakcja danych
76
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
6
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
7
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ę
[ Pobierz całość w formacie PDF ]