.:$$:.

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 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.

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

• 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.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.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.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.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.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.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.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.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.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.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.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.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.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)