algorytmy_techniki_programowania.pdf

ł>*

I •*_

-_!__ J

UKtury danych i te<hniki program

-fli^i*

•f

„Algorytmy, struktury danych i techniki pro gramów an i u" lu w

podręcznik dla wszystkich osób, które w codzienny pracy programistycz-

nej odczuwająpotrzebę szybkiego odszukania pewnych informacji z dzie-

dzin} algor>'tmiki w celu zastosowania ich w Swoich programach.

]i[|żka niniejsza zoslaJa stworzona według zasady:

li J ^ a

minimum teorii- maksimum praktyki

lic/ba zadań i programy znajdujące się na dyskietce powinny mim-

żliuic- syybkic zaslosowanie w praktyce omawianego materiału.

BASIC

Techniki rtrkurencyjne: co to jesŁ rckur^ncja i jak ją stosować w praktyce?

Analiza sprawności a1uor\"^ńw: kilka prostych metod powalających

porównywać efeLlywność algoryttnuw.

Sortowanie danych; najpopularniej,s/e procedury sortujące,

Slruktury dairyeb: Hsty, kolejki, zbiory i drzewa w ujęciu praktycznym.

«^ Derętnr?yu^cja: jak 7amieTiić program reklirencyjny (czasami bardzo

a5l czasochŁonny) na jego wersję iteraoyjną?

Aliior>tm\ przeszukiwania: przeszukiwanie liniowe, binarne

i transformacja kino/owa (^ng. hashing).

I Przeszukiwanie icksińw: opis najbardziej zujn\di melod pr7.e57.Liki\*aniJ

Hellon

lekstów (brute-force. K-M.-ł 1 , Boy era 1 Mnorea, Rabina i Karpa).

Zaiiv^j.nso\\ane techniki programem ania: dzicl-i-r^ąd^, program o wanie

dynainiczn^ algorytmy żarłoczne iang r greedy).

Algo rytmika grafów: opis jednej 7, najciekawszych slruklur

jqvych w informatyce.

Algorytmy numerycznej jak zasln^ować komputery w matematyce do

wykonywaniu obliczeń "''

Sztuczna inteligencja: czy komputery moĘą myśleć?

Kuikiwajiie \ konipiesja danych: opis najbardziej znanych popularnych

metod kodowania i kompresji danych: systemu kiypiotrafiv/nego

/ kluczem publicznym i mdod> Huttmana,

Zadania: z,rub ti> sam!

vtv.;---

1VH

ISBN 83-86718-64-1

788386 718641

Wydawnictwo Helion

ul. Pszczyńska 89, 44-100 Gliwice, POLAND

44-100 Gliwice, skr. poc^t. 462, POLAND

iel./fax (32) 38-81 -54, GSM 0(602) 38-81 -54

fax (32) 38-81-01, e-mail: helion@helion.com.pl

http://www.helron.com.pl

Piotr Wróblewski

struktury danych

i techniki programowania

Wydanie drugie poprawione i uzupełnione

Spis treści

Przedmowa 9

Rozdziali Zanim wystartujemy 1 7

I. I, Jak to wcześniej bywało, czyli wyjątki z historii maszyn algorytmicznych , , 19

1.2. Jak to się niedawno odbyto, c zyli o tym k t o „wymyślił " metodologi ę programow a nia 2 1

1.3. Proces koncepcji programów

2 2

1.4. Poziomy abstrakcji opisu i wybór języka

1.5. Poprawność algorytmów

Rozdział 2 Rakurencja

2.1. Definicja

rekurencji

2 9

2.2. Ilustracja pojęcia rekurencji

2.3. Jak wykonująsię programy rekurencyjne?

2.4. Niebezpieczeństwa

rekurencji

2.4.1. CiągFibonaccie go.. .

3 5

2.4.2. Stack overfl ow!

3 6

2.5. Pułapek ciąg dalszy

3 7

2.5.1. Stąd do wieczności

3 8

2.5.2. Definicja poprawna, ale

3 8

2.6. Typy programów rcku rcncyjny c h

4 0

2.7. Myślenie rekure ncyjn e

4 2

2.7.1. Spirala

4 2

2.7.2. Kwadraty „parzyste"

4 4

2.8. Uwagi p rak t yczne na t emat t echnik rekurency j ny c h

2.9. Zadania

4 7

2.10. Rozwiązania) wskazówki dn zadań

Rozdział 3 Analiza sprawności algorytmów

5 3

3.1. Dobre samopoczucie użytkownika programu

Spis treści

!. Przykład I: Jeszcye raz fiinkcja silnia

5 7

5, Przykład 2: Zerowanie fragmentu tab li cy

6 1

i. Przykład 3: Wpadamy w pułapkę

i. Przykład 4: Różne typy złożoności obliczeniowej...

,...65

Nowe zadanie: uprościć obliczenia!

, .. ,

. ..6 8

Analiza programówre kurency j ny c h. .. .,

6 8

3.7.1. Terminologia

6 9

3.7.2. Ilustracja melody na przy kładz i e

3.7. 3. Rozk ł ad „logarytm i czny"

,...72

3.7.3

7 2

3.7.4. Damiana dziedziny równania rekurencyjnego

7 4

3.7.5. Funkcja Ackermanna, czyli coś dla sm a ko s zy

7 5

3.8. Zadania

7 6

3.9. Rozwiązania i wskazówki do zadań

4.1. Sortowanie przez wstawianie, algorytm klasy O(N 2 )

4.2. Sortowanie bąbelkowe, algorytm klasy O(N-)

4.3. Quicksort, algoryt m kla s y 0{N l og j N)

, .. ,

8 7

4.4. Uwagi praktyczne

Rozdział 5 Struktury danych

9 3

5.1. Listy jednokierunkowe

9 4

5.1.1. Realizacja struktur danych listy jednokierunkowej

5.1.2. Tworzenie listy jednokierunkowej

5.1.3. Listy jednokierunkowe-teoria i rzeczywistość

5.2. Tablicowa implementacja list

5.2.1. Klasyczna reprezentacja tabl icowa

5.2.2. Metoda tablic rów noległych

5. 2.3. Lis l y innych t ypów

1 27

5.3. Stos

128

5.3.1. Zasad a dz i ałania stosu

5.4. Kolejki FIFO

5.5. Sterty i kolejki priorytetnwe

5.6. Dizewa i ich reprezentacje ,

5.6.1. Drzewa binarne i wyrażenia arytmetyczne

5.7. Uniwe rsa l na struktura słown i kowa

5.8. Zbiory

1 59

5.9. Zadania

161

5.10. Rozwiązania zadań

Rozdział 6 Derekursywacja

6.1. Jak pracuje kompilator?

6.2. Odrobina formalizmu... nie zaszkodzi!.,

6.3 Kilka przykładów derekursywacji algorytmów

6.4. Derekursywacja z wykorzystaniem stosu

6.4.1. Eliminacja zmienny ch lokalnych

6.5. Metoda funkcji przeciwnych

6.6. Klasyczne schematy derekursywacj i

180

RozdziaM Algorytmy sortowania

8 2

Spis treści

6.6.1. Schemat typu wfiile

6.6.2. Schemat typu i/... else

6.6.3. Schem a t z podw ó jn y m wywo ł aniem

6.7. Podsumowanie

Rozdział 7 Algorytmy przes zuk i wan i a

7.1. Przeszukiwanie liniowe

7.2. Przeszukiwanie binarne

7.3. Transformacja kluczowa

7.3.1. W pohukiwaniu funkcji W

7.3.2. Najbardziej znane funkcje W

7.3.3. Obsługa konfliktów dostępu ,

7.3.4. Zastosowania iransformacji kluczowej

7.3.5. Podsumowanie metod transformacji kluczowej

204

RozdziałS Przeszukiwanie tek s t ó w

2 07

8.1. Algorytm typu brute-forcc

2 07

8.2. Nowe algorytmy poszuki w a ń.,

2 10

8.2.1. Algorytm K-M-P

211

RJ 7. Algorytm Boyera i Moore'a

2 16

8.2,3. Algoryim Rabina i Karpa.....

218

Rozdział 9 Zaawansowane techniki pro gramowania

2 23

9.1. Programowanie typu „dziel-i-rządż"

2 24

9.1.1. Odszukiwanie minimum i maksimum w t ab li cy liczb

2 25

9.1.2. Mnożenie macierzy o rozmi a r ze N*N

2 29

9.1.3. Mnożenie liczb całkowitych

2 32

9.1.4. Inne znane algorytmy „dzic!-i-rządź"..

2 33

9.2. Algorytmy „żarłoczne", czyli przekąsić coś nadszedł już czas

2 34

9.2.1. Problem plecakowy, cz y li nieł a tw e je s t ż y cie Hiryst y -pi e chura

2 35

9.3. Programowanie dynam iczne

2 38

9.4. Uwagi bibliograficzne

343

Rozdział 10 Elementy algoryimiki g rafów

2 45

10.1. Definicje i pojęcia podstawow e

246

10.2. Sposoby reprezentacji grafów

2 48

10.3. Podstawowe operacje na g ra f a c h

2 49

10.4. Algorytm Roy-W a r shalia

2 51

10.5. Algorytm Floyda

2 54

10.6. Przeszukiwanie grafów

2 57

10.6.1. Strategia „w głąb"

257

10.6.2. Strategia „wszerz"

2 59

10.7. Problem właści wego dob o ru

2 61

10.8. Podsumowanie

266

Rozdziału Algorytmy numeryczne

2 67

11.1. Poszukiwanie miejsc zerowych funkc ji

. 2 68

11.2. Iteracyjne obliczanie wartości funkcji

2 G9

11.3. Interpolacja fijnkcji met o d ą L ag r an g e'a... .

270

11.4. Różniczkowanie funkcji

272

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: