Wstęp do informatyki (Wydawnictwo Naukowe PWN)

Tytuł Wstęp do informatyki Autorzy Jacek Lembas, Rafał Kawa Język polski Wydawnictwo Wydawnictwo Naukowe PWN ISBN 978-83-01-19604-2 Rok wydania 2017 Warszawa Wydanie 1 ilość stron 302 Format mobi, epub Spis treści 1. Wprowadzenie 9
1.1. Informacja 9
1.2. Podstawowe właściwości informacji 11
1.3. Informatyka 13
1.3.1. Istota informatyki 13
1.3.2. Informatyka a komputery 14
1.4. Komputer 15
1.5. Działy informatyki 16

2. Teoria informacji 19
2.1. Miara informacji 19
2.2. Entropia źródła informacji 23
2.3. Kodowanie komunikatów 24
2.4. Algorytmy kodowania optymalnego 29
2.4.1. Algorytmy Shannona-Fano 30
2.4.2. Algorytm Huffmana 32
2.4.3. Uzupełnienia 36

3. Systemy liczbowe 39
3.1. Wprowadzenie 39
3.2. Analogowość, cyfrowość, binarność 42
3.3. Działania na ilośćch naturalnych w systemach pozycyjnych 44
3.3.1. Dodawanie i odejmowanie 44
3.3.2. Mnożenie i dzielenie 45
3.3.3. Zapis liczb rzeczywistych 46
3.4. Konwersje pomiędzy systemami liczbowymi 47
3.4.1. Konwersja do systemu dziesiętnego 48
3.4.2. Konwersja do systemów niedziesiętnych 49
3.4.3. Zależność podstaw systemów liczbowych 53

4. Arytmetyka komputerowa 57
4.1. Kodowania stałopozycyjne 58
4.1.1. Kodowanie znak-moduł prosty 59
4.1.2. Kodowanie odwrotnościowe 63
4.1.3. Kodowanie uzupełnieniowe 70
4.1.4. Kodowanie nadmiarowe 77
4.2. Kodowania zmiennopozycyjne 87
4.2.1. Wprowadzenie 87
4.2.2. Normalizacja i jednoznaczność 88
4.2.3. Algorytmy kodowania i dekodowania 89
4.2.4. Reprezentatywność 97
4.2.5. Efektywność i optymalizacja 101
4.2.6. Działania na kodach zmiennopozycyjnych 103
4.2.7. Praktyczne implementacje 108

5. Maszyna Turinga 109
5.1. Wprowadzenie 109
5.2. Definicja 110
5.3. Przykłady 113
5.3.1. Pracowity bóbr stopnia trzeciego 113
5.3.2. Inkrementacja liczby binarnej 115
5.3.3. Inkrementacja liczby dziesiętnej 118
5.3.4. Dekrementacja liczby binarnej 120
5.3.5. Sumowanie przez inkrementację i dekrementację 122
5.3.6. Dodawanie pisemne liczb binarnych 124

6. Przykładowa Maszyna Cyfrowa (PMC) 129
6.1. Architektura von Neumanna 129
6.2. Budowa PMC 131
6.3. Działanie PMC 132
6.3.1. Interpretacja słowa maszynowego 132
6.3.2. Rozkazy 133
6.3.3. Tryby adresowania 135
6.3.4. Proces pracy 136
6.4. Realizacja przykładowych algorytmów 136

7. Podstawy algorytmiki 147
7.1. Wprowadzenie 147
7.2. Podstawowe pojęcia 148
7.2.1. Pojęcie algorytmu 148
7.2.2. Wstępne przykłady 149
7.2.3. Zmienna 151
7.2.4. Podstawienie 152
7.2.5. Tablica 154
7.3. Zapis algorytmów 156
7.3.1. Zapis krokowy 156
7.3.2. Schemat blokowy 156
7.3.3. Strukturalne schematy blokowe 165
7.3.4. Zapis liniowy, pseudokod 177
7.4. Strukturalność 186
7.4.1. Generalia 186
7.4.2. Strukturalny zapis niestrukturalności 188
7.5. Tworzenie algorytmów 194
7.6. Złożoność algorytmów 205
7.7. Poprawność algorytmów 215
7.7.1. Wprowadzenie 215
7.7.2. Podstawy 216
7.7.3. Częściowa poprawność, niezmienniki pętli 218
7.7.4. Częściowa poprawność wybranych algorytmów 226

8. Notacje wyrażeń algebraicznych 237
8.1. Generalia 237
8.1.1. Podstawowe pojęcia 237
8.1.2. Typy notacji algebraicznych 239
8.2. Notacje algebraiczne w informatyce 242
8.3. Konwersje notacji 243
8.3.1. Stos 243
8.3.2. Sprowadzenie do zapisu liniowego 243
8.3.3. Zamiana na odwrotną notację polską 245
8.3.4. Wartościowanie wyrażeń w ONP 248
8.4. Zapis algorytmów w ONP 250
8.4.1. Konwersja zapisu algorytmów do ONP 250
8.4.2. Odtworzenie algorytmów z zapisu w ONP 258

9. Języki formalne 263
9.1. Podstawowe pojęcia i oznaczenia 265
9.1.1. Przykładowe alfabety 267
9.1.2. Przykładowe języki 269
9.2. Gramatyka formalna 275
9.2.1. Intuicja 275
9.2.2. Formalne definicje 278
9.2.3. Hierarchia Chomsky’ego 282
9.2.4. Jeszcze o gramatykach 286
9.2.5. Gramatyki języków programowania 294
9.3. Gramatyki regularne a maszyna Turinga 296
9.3.1. Akceptacja słów języka regularnego 296
9.3.2. Rozpoznawanie palindromów 298

Indeks 301