Książka jest przeznaczona dla Czytelników, którzy nie mając specjalnego przygotowania matematycznego i wiadomości wykraczających poza przeciętną szkolną wiedzę, chcą poznać pojęcia i idee stanowiące fundament współczesnej informatyki.
W początkowych rozdziałach przedstawiono najważniejsze właściwości algorytmów, metody algorytmiczne, różnice między obliczeniami analogowymi i cyfrowymi oraz metody cyfrowego przetwarzania sygnałów. W kolejnych rozdziałach Czytelnik jest zaznajamiany z maszyną Turinga, lingwistyką matematyczną i automatami skończonymi.
Autor omawia także budowę i działanie urządzeń cyfrowych, począwszy od operacji na dwójkowych danych poprzez algebrę Boole’a oraz zasady projektowania cyfrowych podzespołów, aż do architektury współczesnych komputerów i współdziałania sprzętu z oprogramowaniem.
Książka jest przeznaczona dla amatorów, którzy chcą być świadomymi użytkownikami sprzętu informatycznego, dla studentów informatyki i kierunków pokrewnych, a także dla informatyków chcących lepiej poznać i zrozumieć korzenie dziedziny, w której się specjalizują.
Spis treści:
1. O czym będzie traktować ta książka Od zadania obliczeniowego do jego wykonania przez komputer 11 O czym opowiemy 16
2. O algorytmach i złożoności obliczeniowej na kilku łatwych przykładach Co to właściwie jest „obliczenie”? 23 Weź, Jasiu, kajecik i notuj 25 Przeszukiwanie listy nieuporządkowanej i uporządkowanej 30 Pojęcie złożoności obliczeniowej (czasowej). Notacja O(.) 35 Problem Collatza i badanie własności stopu 42
3. Trudne problemy, które wybuchają Komiwojażer ma problem 47 Dlaczego NP? 53 Plecak, układanki i różne zabawy z kredkami 56 Pytanie za milion dolarów: czy P = NP? 63
4. O metodach konstruowania algorytmów Skąd się biorą algorytmy? 67 Metoda „dziel i zwyciężaj” 71 Algorytmy zachłanne 73 Algorytmy heurystyczne 75 Algorytmy rekurencyjne 78
5. Algorytmy probabilistyczne i ewolucyjne Metody Monte Carlo 91 Symulacja losowych zjawisk zachodzących w czasie 97 Algorytmy ewolucyjne 103
6. Obliczenia analogowe i cyfrowe Czy obliczenie musi się wykonywać w jakichś krokach? 118 Analogowe i cyfrowe techniki przetwarzania informacji 119 Domowe i szkolne przykłady obliczeń analogowych 123 Analogowe urządzenia w technice 126 Analogowe układy automatycznej regulacji 128 Cybernetyczne wizje: serwomechanizmy czy komputery? 133
7. Cyfrowe przetwarzanie sygnałów Dyskretyzacja ciągłego sygnału 138 Widmo sygnału i przekształcenie (transformata) Fouriera 143 Korzyści ze znajomości widma 152 Matematyka i francuska epopeja 159
8. Maszyna Turinga Zasada działania maszyny Turinga 163 Teza Churcha–Turinga dla obliczeń sekwencyjnych 177 Enigma życia i działalności Alana Turinga 181
9. O lingwistyce matematycznej Czy lingwistyka może być matematyczna? 189 Język jako zbiór 190 Model gramatyki kombinatorycznej Chomsky’ego i notacja BNF 194 Panie gryzą psy ponieważ dzieci lubią koty 196 Języki skończone i nieskończone 202 Poziom leksykalny i składniowy (syntaktyczny) gramatyki 205 Języki bezkontekstowe i kontekstowe 209 A jak się to ma do języków naturalnych? 210 Intelekt i lewicowość 213
10. Automaty skończone Podstawowa definicja automatu skończonego 217 Niezupełność i niedeterminizm automatu 224 Automat skończony a badanie poprawności składniowej 226 Automat skończony jako model zachowania fizycznego urządzenia 231
11. System dwójkowy Dlaczego właśnie dwójkowy? 235 Dwójkowe liczby całkowite i podstawowe arytmetyczne operacje na nich 238 Inne sposoby przedstawiania liczb całkowitych 251 Liczby stałoprzecinkowe i zmiennoprzecinkowe 253 Notacja heksadecymalna (szesnastkowa) 258 Kodowanie znaków alfanumerycznych 259 Projekt Unicode 266
12. Elementarz syntezy logicznej Co oznacza ten tytuł? 273 Od Arystotelesa ze Stagiry do Claude'a Shannona z Gaylord w stanie Michigan 274 Układy przełączające 279 Niezwykła kariera naukowa Claude'a Shannona 286 Algebra Boole’a i pomysł na „automatyzację” obliczeń logicznych 289 Od tabelki prawdy do sieci logicznej 298 Jak zrobić trzydziestodwubitowy sumator? 303 Inne „prefabrykowane” podzespoły logiczne 309
13. Układy sekwencyjne Przerzutniki 313 Rejestry i liczniki 320 Wrzuć monetę. czyli prosty układ sterowania 324
14. Wiek informatyki Praojcowie informatyki 341 Potrzeby obliczeniowe okresu II wojny światowej 347 Bariera niezawodnościowa 350 Bardzo dobry, ale bardzo drogi pomysł 352 Powojenne problemy globalnej polityki 355 Wielki program na przełomowe lata sześćdziesiąte 356 Komputery lat sześćdziesiątych 358 Lata siedemdziesiąte: postęp nie zwalnia 362 Kolejny przełom: komputery prywatne 364 Od internetów do Internetu 367 A co tam, panie, w polityce? 368 Nieoczekiwany koniec zimnej wojny 372
15. Von Neumanna komputer z programem w pamięci Jak to się zaczęło 376 Od prostego kalkulatora do czegoś w rodzaju własnej roboty ENIAC-a 378 Zasada maszyny z programem w pamięci 383 Kilka słów o programowaniu maszyn z pamiętanym programem 392 Inżynieria oprogramowania i inżynieria systemowa 397
16. Organizacja jednoprocesorowego systemu komputerowego O jakim komputerze mowa? 401 Podstawowy schemat blokowy systemu 402 Pan, sługa i arbiter, czyli jak uzyskać dostęp do magistrali 407 Czego pan może wymagać od sługi 409
17. Procesor Schemat blokowy procesora 419 Stos systemowy i operacje na stosie 431
18. System przerwań Zasada przerwań 437 Od zgłoszenia przerwania do reakcji układu sterowania procesora 442 Inicjowanie obsługi przerwania 445 Program obsługi przerwania 448 Programy i procesy 450
19. Co było dalej? Zakończenie 470 Skorowidz nazwisk 471 Skorowidz rzeczowy 473
Wstęp do informatyki nie tylko dla informatyków
|