Autor: Alfred V. Aho, Jeffrey D. Ullman

ISBN 83-7361-138-X

Ilość stron: 846

Twarda oprawa

Data wydania: 08/2003

Książka Alfreda Aho i Jeffreya Ullmana "Wykłady z informatyki z przykładami w języku 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 "Wykłady z informatyki z przykładami w języku C" 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ętności. Autorzy wymagają od czytelnika znajomości języka C.

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.

Rozdziały:

1. Informatyka: mechanizacja abstrakcji (15)

• 1.1. Zagadnienia omawiane w książce (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 książce 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łasności programów (69)
  
• 2.6. Definicje rekurencyjne (77)
  
• 2.7. Funkcje rekurencyjne (87)
  
• 2.8. Sortowanie przez scalanie: rekurencyjny algorytm sortujący (93)
  
• 2.9. Dowodzenie własności programów rekurencyjnych (102)
  
• 2.10. Podsumowanie rozdziału 2. (105)
  
• 2.11. Bibliografia rozdziału 2. (106)

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 "dużego O" i przybliżony czas działania (114)
  
• 3.5. Upraszczanie wyrażeń "dużego 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 zawierających wywołania funkcji (146)
  
• 3.9. Analizowanie funkcji rekurencyjnych (151)
  
• 3.10. Analiza sortowania przez scalanie (155)
  
• 3.11. Rozwiązywanie 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 wartości 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. Efektywność operacji na drzewach przeszukiwania binarnego (293)
  
• 5.9. Kolejki priorytetowe i drzewa częściowo uporządkowane (297)
  
• 5.10. Sortowanie stogowe - sortowanie za pomocą zrównoważonych drzew częściowo uporządkowanych (306)
  
• 5.11. Podsumowanie rozdziału 5. (311)
  
• 5.12. Bibliografia rozdziału 5. (312)

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łuższy wspólny podciąg (350)
  
• 6.10. Reprezentowanie ciągó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 liście (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łasności 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ę wśró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)

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ójności grafu nieskierowanego (506)
  
• 9.5. Minimalne drzewa rozpinające (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 wyrażenia 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. Wyrażenia regularne (597)
  
• 10.6. Rozszerzenia wyrażeń regularnych stosowane w systemie Unix (606)
  
• 10.7. Prawa algebraiczne wyrażeń regularnych (610)
  
• 10.8. Od wyrażeń regularnych do automatów (614)
  
• 10.9. Od automatów do wyrażeń 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. Niejednoznaczność i projektowanie gramatyk (652)
  
• 11.6. Konstruowanie drzew rozbioru (659)
  
• 11.7. Algorytm analizy składniowej oparty na tabeli (667)
  
• 11.8. Gramatyki a wyrażenia 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. Wyrażenia logiczne (688)
  
• 12.4. Tabele prawdy (692)
  
• 12.5. Od funkcji boolowskich do wyrażeń logicznych (699)
  
• 12.6. Określanie wyrażeń logicznych za pomocą tablic Karnaugha (704)
  
• 12.7. Tautologie (712)
  
• 12.8. Niektóre prawa algebraiczne dla wyrażeń logicznych (717)
  
• 12.9. Tautologie i metody dowodzenia (726)
  
• 12.10. Dedukcja (731)
  
• 12.11. Dowodzenie przez rezolucję (737)
  
• 12.12. Podsumowanie rozdziału 12. (742)
  
• 12.13. Bibliografia rozdziału 12. (743)

13. Wykorzystanie logiki do projektowania komponentów komputerów (745)

• 13.1. Zagadnienia poruszane w tym rozdziale (745)
  
• 13.2. Bramki (746)
  
• 13.3. Układy (747)
  
• 13.4. Wyrażenia logiczne i układy (750)
  
• 13.5. Ograniczenia fizyczne związane z układami (756)
  
• 13.6. Projekt układu dodawania z zastosowaniem zasady dziel i zwyciężaj (761)
  
• 13.7. Projekt multipleksera (769)
  
• 13.8. Elementy pamięciowe (776)
  
• 13.9. Podsumowanie rozdziału 13. (778)
  
• 13.10. Bibliografia rozdziału 13. (778)

14. Logika predykatów (779)

• 14.1. Zagadnienia poruszane w tym rozdziale (779)
  
• 14.2. Predykaty (780)
  
• 14.3. Wyrażenia logiczne (782)
  
• 14.4. Kwantyfikatory (785)
  
• 14.5. Interpretacje (791)
  
• 14.6. Tautologie (797)
  
• 14.7. Tautologie zawierające kwantyfikatory (799)
  
• 14.8. Dowody w logice predykatów (806)
  
• 14.9. Dowody na podstawie reguł i faktów (810)
  
• 14.10. Prawdziwość i możność dowodzenia (816)
  
• 14.11. Podsumowanie rozdziału 14. (822)
  
• 14.12. Bibliografia rozdziału 14. (823)