Spis treĂci
Przedmowa Wydawcy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Przedmowa Feynmana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1. Wprowadzenie do komputerów . . . . . . . . . . . . . . . . . . . . . . . . . .
17
1.1. Model urzĊdnika archiwisty . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Zbiory instrukcji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Podsumowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21 24 32
2. Organizacja komputerów . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.1. Bramki i ukáad kombinacyjny . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Dekoder binarny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. WiĊcej o bramkach: bramki odwracalne . . . . . . . . . . . . . . . . . . . . 2.4. Funkcjonalnie peáne zbiory operatorów . . . . . . . . . . . . . . . . . . . . 2.5. Przeáączniki i pamiĊü komputerowa . . . . . . . . . . . . . . . . . . . . . . 2.6. Taktowanie i rejestry przesuwne . . . . . . . . . . . . . . . . . . . . . . . .
35 44 47 52 54 58
3. Teoria obliczeñ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
3.1. Efektywne procedury i obliczalnoĞü . . . . . . . . . . . . . . . . . . . . . . 3.2. Automaty skoĔczone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Ograniczenia automatów skoĔczonych . . . . . . . . . . . . . . . . . . . . 3.4. Maszyny Turinga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5. WiĊcej o maszynach Turinga . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6. Uniwersalne maszyny Turinga i problem stopu . . . . . . . . . . . . . . . . 3.7. ObliczalnoĞü . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64 66 70 75 83 88 95
4. Kodowanie i teoria informacji . . . . . . . . . . . . . . . . . . . . . . . . . . .
101
4.1. Informatyka i teoria komunikacji . . . . . . . . . . . . . . . . . . . . . . . 4.2. Wykrywanie báĊdów i kody korygujące . . . . . . . . . . . . . . . . . . . . 4.2.1. Sprawdzanie parzystoĞci . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2. Kody Hamminga . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3. Uwaga o pamiĊci . . . . . . . . . . . . . . . . . . . . . . . . . . . .
102 102 103 105 110