Alfred V. Aho

[ Pobierz całość w formacie PDF ]
IDZ DO
PRZYK£ADOW
Wyk³ady z informatyki
SPIS TRECI
z przyk³adami w jêzyku C
KATALOG KSI¥¯EK
Autorzy: Alfred V. Aho, Jeffrey D. Ullman
T³umaczenie: Miko³aj Szczepaniak, Bart³omiej Garbacz
ISBN: 83-7361-138-X
Tytu³ orygina³
Format: B5, stron: 846
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
DODAJ DO KOSZYKA
Ksi¹¿ka Alfreda Aho i Jeffreya Ullmana „Jêzyk C” stanowi znacz¹cy postêp w dziedzinie
metodyki nauczania podstaw informatyki. Ten nowatorski podrêcznik w przystêpny
sposób prezentuje zagadnienia dotycz¹ce modeli, pojêæ i technik z zakresu matematyki
dyskretnej i informatyki. Ksi¹¿ka stanowi zarówno wprowadzenie do dziedziny
informatyki, jak i autorytatywne ród³o jej teoretycznych podstaw. Pokazuje, w jaki
sposób „matematyczne abstrakcje” przekszta³ca siê w dzia³aj¹ce programy.
Podrêcznik dostarcza przysz³ym informatykom solidnych podstaw niezbêdnych
w dalszych studiach oraz w przysz³ej pracy zawodowej. Zawiera liczne æwiczenia,
u³atwiaj¹ce przyswojenie przedstawianej w nim wiedzy i sprawdzenie swoich
umiejêtnoci. Autorzy wymagaj¹ od czytelnika znajomoci jêzyka C.
Zakres tematyczny obejmuje miêdzy innymi:
• Iteracjê, indukcjê i rekursjê
• Zagadnienia zwi¹zane z czasem wykonywania programów
• Kombinatorykê i prawdopodobieñstwo
• Modele danych oparte na drzewach, listach i zbiorach
• Relacyjny i grafowy model danych
• Wzorce, automaty i wyra¿enia regularne, rekurencyjny model wzorców
• Logikê zdañ
• Logikê predykatów
Alfred V. Aho jest zastêpc¹ dyrektora ds. informatyki i badañ technologicznych w firmie
Bellcore. Od 1967 do 1991 roku pracowa³ w Computing Science Research Center
w AT&T Bell Laboratories. Wyk³ada³ równie¿ informatykê na Columbia University,
Stanford University oraz Stevens Institute of Technology.
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWOCIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treci
Przedmowa...............................................................................................................9
1.
Informatyka: mechanizacja abstrakcji ...................................................................15
1.1. Zagadnienia omawiane w ksice.............................................................................................................. 17
1.2. Zagadnienia omawiane w tym rozdziale.................................................................................................... 20
1.3. Modele danych........................................................................................................................................... 20
1.4. Model danych j zyka C.............................................................................................................................. 27
1.5. Algorytmy i projektowanie programów..................................................................................................... 35
1.6. Niektóre z wykorzystywanych w tej ksice konwencji j zyka C............................................................. 37
1.7. Podsumowanie rozdziału 1......................................................................................................................... 38
1.8. Bibliografia rozdziału 1.............................................................................................................................. 39
2.
Iteracja, indukcja i rekurencja................................................................................41
2.1. Zagadnienia poruszane w rozdziale 2. ....................................................................................................... 43
2.2. Iteracje........................................................................................................................................................ 43
2.3. Dowody indukcyjne ................................................................................................................................... 51
2.4. Indukcja zupełna ........................................................................................................................................ 61
2.5. Dowodzenie własno2ci programów ........................................................................................................... 69
2.6. Definicje rekurencyjne............................................................................................................................... 77
2.7. Funkcje rekurencyjne................................................................................................................................. 87
2.8. Sortowanie przez scalanie: rekurencyjny algorytm sortujcy.................................................................... 93
2.9. Dowodzenie własno2ci programów rekurencyjnych................................................................................ 102
2.10. Podsumowanie rozdziału 2..................................................................................................................... 105
2.11. Bibliografia rozdziału 2.......................................................................................................................... 106
 4
SPIS TRECI
3
Czas działania programów...................................................................................107
3.1. Zagadnienia poruszane w tym rozdziale.................................................................................................. 107
3.2. Wybór algorytmu ..................................................................................................................................... 108
3.3. Pomiar czasu działania programu ............................................................................................................ 109
3.4. Notacja „duego O” i przybliony czas działania.................................................................................... 114
3.5. Upraszczanie wyrae; „duego O”.......................................................................................................... 120
3.6. Analiza czasu działania programu............................................................................................................ 128
3.7. Reguła rekurencyjna dla szacowania ogranicze; czasów działania......................................................... 136
3.8. Analizowanie programów zawierajcych wywołania funkcji ................................................................. 146
3.9. Analizowanie funkcji rekurencyjnych ..................................................................................................... 151
3.10. Analiza sortowania przez scalanie ......................................................................................................... 155
3.11. Rozwizywanie relacji rekurencyjnych ................................................................................................. 164
3.12. Podsumowanie rozdziału 3..................................................................................................................... 174
3.13. Bibliografia rozdziału 3.......................................................................................................................... 175
4
Kombinatoryka i prawdopodobie'stwo...............................................................177
4.1. Zagadnienia poruszane w tym rozdziale.................................................................................................. 177
4.2. Wariacje z powtórzeniami........................................................................................................................ 178
4.3. Permutacje................................................................................................................................................ 182
4.4. Wariacje bez powtórze;........................................................................................................................... 188
4.5. Kombinacje .............................................................................................................................................. 191
4.6. Permutacje z powtórzeniami.................................................................................................................... 199
4.7. Rozdzielanie obiektów do koszyków....................................................................................................... 202
4.8. Łczenie reguł kombinatorycznych ......................................................................................................... 205
4.9. Wprowadzenie do teorii prawdopodobie;stwa........................................................................................ 209
4.10. Prawdopodobie;stwo warunkowe ......................................................................................................... 215
4.11. Rozumowanie probabilistyczne ............................................................................................................. 225
4.12. Oczekiwane warto2ci oblicze;............................................................................................................... 235
4.13. Niektóre zastosowania prawdopodobie;stwa w programowaniu.......................................................... 238
4.14. Podsumowanie rozdziału 4..................................................................................................................... 244
4.15. Bibliografia rozdziału 4.......................................................................................................................... 245
5
Model danych oparty na drzewach ......................................................................247
5.1. Zagadnienia poruszane w tym rozdziale.................................................................................................. 247
5.2. Podstawowa terminologia ........................................................................................................................ 248
5.3. Struktury danych dla drzew...................................................................................................................... 256
5.4. Rekurencja w drzewach ........................................................................................................................... 263
5.5. Indukcja strukturalna................................................................................................................................ 272
5.6. Drzewa binarne ........................................................................................................................................ 277
5.7. Drzewa przeszukiwania binarnego........................................................................................................... 284
5.8. Efektywno2@ operacji na drzewach przeszukiwania binarnego............................................................... 293
5.9. Kolejki priorytetowe i drzewa cz 2ciowo uporzdkowane...................................................................... 297
5.10. Sortowanie stogowe — sortowanie za pomoc zrównowaonych drzew
cz 2ciowo uporzdkowanych ................................................................................................................ 306
5.11. Podsumowanie rozdziału 5..................................................................................................................... 311
5.12. Bibliografia rozdziału 5.......................................................................................................................... 312
SPIS TRECI
5
6
Model danych oparty na listach ...........................................................................313
6.1. Zagadnienia poruszane w tym rozdziale.................................................................................................. 313
6.2. Podstawowa terminologia ........................................................................................................................ 314
6.3. Operacje na listach ................................................................................................................................... 318
6.4. Struktura danych — lista jednokierunkowa............................................................................................. 320
6.5. Implementacja list oparta na tablicy......................................................................................................... 329
6.6. Stosy......................................................................................................................................................... 335
6.7. Wykorzystanie stosu w implementacji wywoła; funkcji......................................................................... 341
6.8. Kolejki...................................................................................................................................................... 347
6.9. Najdłuszy wspólny podcig.................................................................................................................... 350
6.10. Reprezentowanie cigów znakowych .................................................................................................... 357
6.11. Podsumowanie rozdziału 6..................................................................................................................... 364
6.12. Bibliografia rozdziału 6.......................................................................................................................... 365
7
Model danych oparty na zbiorach........................................................................367
7.1. Zagadnienia poruszane w tym rozdziale.................................................................................................. 367
7.2. Podstawowe definicje............................................................................................................................... 367
7.3. Operacje na zbiorach................................................................................................................................ 372
7.4. Implementacja zbiorów oparta na li2cie................................................................................................... 383
7.5. Implementacja zbiorów oparta na wektorze własnym............................................................................. 389
7.6. Mieszanie ................................................................................................................................................. 392
7.7. Relacje i funkcje....................................................................................................................................... 398
7.8. Implementowanie funkcji w formie danych............................................................................................. 406
7.9. Implementowanie relacji binarnych......................................................................................................... 413
7.10. Specyficzne własno2ci relacji binarnych................................................................................................ 421
7.11. Zbiory niesko;czone .............................................................................................................................. 431
7.12. Podsumowanie rozdziału 7..................................................................................................................... 437
7.13. Bibliografia rozdziału 7.......................................................................................................................... 437
8
Relacyjny model danych......................................................................................439
8.1. Zagadnienia poruszane w tym rozdziale.................................................................................................. 439
8.2. Relacje...................................................................................................................................................... 440
8.3. Klucze ...................................................................................................................................................... 447
8.4. Główne struktury przechowywania danych w relacjach.......................................................................... 451
8.5. Struktury indeksu drugorz dnego ............................................................................................................ 456
8.6. Poruszanie si w2ród wielu relacji ........................................................................................................... 460
8.7. Algebra relacyjna ..................................................................................................................................... 466
8.8. Implementowanie operacji algebry relacyjnej ......................................................................................... 473
8.9. Prawa algebraiczne dla relacji.................................................................................................................. 479
8.10. Podsumowanie rozdziału 8..................................................................................................................... 488
8.11. Bibliografia rozdziału 8.......................................................................................................................... 489
6
SPIS TRECI
9
Grafowy model danych........................................................................................491
9.1. Zagadnienia poruszane w tym rozdziale.................................................................................................. 491
9.2. Podstawowe poj cia................................................................................................................................. 492
9.3. Sposoby implementacji grafów................................................................................................................ 499
9.4. Składowe spójno2ci grafu nieskierowanego ............................................................................................ 506
9.5. Minimalne drzewa rozpinajce ................................................................................................................ 518
9.6. Przeszukiwanie w głb............................................................................................................................. 524
9.7. Zastosowania algorytmu przeszukiwania w głb..................................................................................... 536
9.8. Algorytm Dijkstry znajdowania najkrótszych dróg ................................................................................. 544
9.9. Algorytm Floyda znajdowania najkrótszych dróg ................................................................................... 556
9.10. Wprowadzenie do teorii grafów............................................................................................................. 564
9.11. Podsumowanie rozdziału 9..................................................................................................................... 569
9.12. Bibliografia rozdziału 9.......................................................................................................................... 570
10.
Wzorce, automaty i wyra0enia regularne.............................................................571
10.1. Zagadnienia poruszane w tym rozdziale................................................................................................ 572
10.2. Maszyny stanów i automaty................................................................................................................... 572
10.3. Automaty deterministyczne i niedeterministyczne ................................................................................ 578
10.4. Przechodzenie od niedeterminizmu do determinizmu ........................................................................... 588
10.5. Wyraenia regularne .............................................................................................................................. 597
10.6. Rozszerzenia wyrae; regularnych stosowane w systemie Unix .......................................................... 606
10.7. Prawa algebraiczne wyrae; regularnych.............................................................................................. 610
10.8. Od wyrae; regularnych do automatów................................................................................................. 614
10.9. Od automatów do wyrae; regularnych................................................................................................. 624
10.10. Podsumowanie rozdziału 10................................................................................................................. 631
10.11. Bibliografia rozdziału 10...................................................................................................................... 631
11.
Rekurencyjny opis wzorców................................................................................633
11.1. Zagadnienia poruszane w tym rozdziale................................................................................................ 633
11.2. Gramatyki bezkontekstowe.................................................................................................................... 634
11.3. J zyki gramatyk...................................................................................................................................... 641
11.4. Drzewa rozbioru..................................................................................................................................... 644
11.5. Niejednoznaczno2@ i projektowanie gramatyk....................................................................................... 652
11.6. Konstruowanie drzew rozbioru.............................................................................................................. 659
11.7. Algorytm analizy składniowej oparty na tabeli...................................................................................... 667
11.8. Gramatyki a wyraenia regularne .......................................................................................................... 676
11.9. Podsumowanie rozdziału 11................................................................................................................... 684
11.10. Bibliografia rozdziału 11...................................................................................................................... 684
12.
Logika zda'..........................................................................................................685
12.1. Zagadnienia poruszane w tym rozdziale................................................................................................ 685
12.2. Podstawy logiki zda; ............................................................................................................................. 686
12.3. Wyraenia logiczne................................................................................................................................ 688
[ Pobierz całość w formacie PDF ]