Dane szczegółowe książki
Wstęp do informatyki / Fulmański, Piotr; Sobieski, Ścibór
Autorzy
Tytuł
Wstęp do informatyki
Wydawnictwo
Łódź: Wydawnictwo Uniwersytetu Łódzkiego, 2005
ISBN
8371718446
Hasła przedmiotowe
Spis treści
pokaż spis treści
Spis treści 3
Spis rysunków 9
1 Wstęp 15
1.1 Czym jest informatyka? IV. 15
1.2 Historia informatyki V^^*L_J ->y^**^ • 17
1.2.1 Bardzo dawno temu /. L . . T^^_ . .^>r O^y . 17
1.2.2 Ostatnie tysiąclecie 19
1.2.3 Wiek XX ^^N^. . J\ Jl . 22
1.3 Zastosowanie i przyszłość . ■0t0—**0^^0t**t0;0^/£^: -O . . 27
1.4 Kierunki współczesnej informatyki 29
1.4.1 Algorytmika ^^«<: > fi\ ft • • • 29
1.4.2 Bazy danych . . .^-*-^T^S^V > ^M .... 30
1.4.3 Grafika komputerowa ~?*>«<^^\ • •« 30
1.4.4 Kryptografia ■//■ ■ ■ ■ ■ -\-\ • • • V 31
1.4.5 Programowanie 31
1.4.6 Sieci komputerowe '/. -XShS 32
1.4.7 Systemy operacyjne •^^!s^/'^53c ^3
1.4.8 Sztuczna inteligencja . . />^/ •^»»s_^ 35
1.4.9 Teoria informacji ./. ^N^ 36
1.5 Zadania ■ ■ ■ Jf -^N- yOS?' 37
2 Podstawowe pojęcia i definicje 39
2.1 Algebra Boole'a .^S>^!*^>^ -J^s* 39
2.1.1 Definicja ogólna . . .ft. >>|j 39
2.1.2 Dwuelementowa algebra Boole'a 44
2.2 Pozycyjne systemy liczbowe 45
2.2.1 System dwójkowy 47
c 2001-2003 by P. Fulmański & Ś. Sobieski, Uniwersytet Łódzki. Wersja RC1 z dnia: 4 stycznia 2004
SPIS TREŚCI
2.2.2 Zapis liczby rzeczywistej w systemie dwójkowym ... 52
2.2.3 Kod szesnastkowy ... . . . . . . . 56
2.2.4 Inne pozycyjne systemy liczbowe . ... . ...... . 57
2.3 BCD .......... 62
2.4 Zadania .. . .... . . ... 67
3 Architektura i działanie komputera 69
3.1 Maszyna Turinga .... ..... . . . ^
3.1.1 Definicja Maszyny Turinga . ... . . . . ... . • • 70
3.2 Bramki logiczne . . 75
3.3 Architektura współczesnego komputera . ... 78
3.4 Procesor — serce komputera . . . .... ..... 83
3.4.1 Cykl pracy procesora . ... ...... ... ^
3.4.2 Rejestry procesora Intel 8086 . . ... .. 86
3.4.3 Budowa rozkazu . .. ... . 89
3.4.4 Adresowanie . . . .. .. 90
3.4.5 Asembler ... ..... 96
3.5 Reprezentacja informacji . . .. ........ .........100
3.5.1 Znaki alfanumeryczne . ... .. .. ... . 100
3.5.2 Liczby naturalne . ... .... 103
3.5.3 Liczby całkowite >-^--^^^. . O. Y 103
3.5.4 Reprezentacja uzupełnień do dwu 105
3.5.5 Liczby rzeczywiste .. ... 109
3.6 Zadania •>^^>^-\\j^ 113
4 Teoria informacji 117
4.1 Informacja vs. wiadomość 117
4.2 Geneza i zakres teorii informacji 118
4.3 Metody kontroli poprawności danych 120
4.3.1 Bit parzystości 121
4.3.2 Suma kontrolna . ..... ................122
4.3.3 Kod CRC . . . (?^? 125
4.4 Zadania .. ...... .................128
5 Algorytmy i struktury danych 129
5.1 Pojęcie algorytmu 129
5.2 Struktury danych 132
5.2.1 Typ danych 132
5.2.2 Tablica . ..... 133
5.2.3 Rekord . /^/ 134
c2001-2003 by P. Fulmański & Ś. Sobieski, Uniwersytet Łódzki. Wersja RC1 z dnia: 4 stycznia 2004
SPIS TREŚCI
5.2.4 Zbiór 136
5.2.5 Plik .......
5.3 Metody opisu algorytmów .. . . . 137
5.3.1 Schemat blokowy ^""^ 137
5.3.2 Schemat zapisu algorytmu za pomocą pseudo-języka . 139
5.4 Podstawowe algorytmy . .. ... . 143
5.4.1 Algorytmy obliczeniowe .. ...... 143
5.4.2 Algorytmy sortowania ...... . . . 144
5.4.3 Algorytmy wyszukujące .... .. . . . 146
5.5 Rekurencja vs. iteracja .... . ... . .
5.6 Analiza złożoności ........ . .
5.7 Zadania ....... 155
6 Języki programowania 157
6.1 Czym jest język programowania? ... . . . 157
6.1.1 Składnia i semantyka .. 159
6.2 Ewolucja języków programowania ..... . 159
6.3 Klasyfikacja języków programowania . . ... . . .. 173
6.3.1 Podział według metodologii programowania 173
6.3.2 Generacje języków programowania . .. . 176
6.4 Kompilacja vs. interpretacja. . . . . . . .. • • 177
6.5 Elementy teorii języków formalnych 183
6.5.1 Gramatyka . . . . rT —*^^Sw • • • (F^L\c- • • • 1^3
6.5.2 Notacja BNF . . . .. ... ... ... \y • ... 184
6.5.3 Notacja przy użyciu diagramów składni 185
7 System operacyjny 187
7.1 Zadania realizowane przez system operacyjny 188
7.2 System operacyjny a architektura komputera 189
7.3 Klasyfikacja systemów operacyjnych ..... 190
7.4 Realizacja zadań . . . ....... 193
7.5 W kierunku systemów wielozadaniowych 196
7.6 Procesy, wątki, .. ... . ............197
7.7 Zarządzanie pamięcią .... .... . . . 198
7.8 System plików .... ...... .... 198
7.9 Czy każdy komputer musi posiadać system operacyjny? . . . 199
7.10 Przykładowe systemy operacyjne 201
7.10.1 Amoeba i Ur^T^f . £^[ 201
7.10.2 Mac OS . ...... .... 202
c2001-2003 by P. Fulmański & Ś. Sobieski, Uniwersytet Łódzki. Wersja RC1 z dnia: 4 stycznia 2004
SPIS TREŚCI
7.10.3 MS-DOS i Windows 204
7.10.4 NetWare //^ ;>-*< • 207
7.10.5 OS/390 rr y^^l • 208
7.10.6 OS/400 ......... . 210
7.10.7 Unix i rodzina . .... . 211
7.11 Zadania .... . . ^^. . 213
8 Sieci komputerowe 215
8.1 Po co mi ona? .. . 215
8.2 Struktura fizyczna sieci . . 216
8.2.1 Zasięg sieci ....... 216
8.2.2 Topologia sieci ........ .......217
8.3 Architektura sieci ....... . ... 218
8.3.1 Architektura równorzędna . . ..... . . 222
8.3.2 Architektura klient-serwer 223
8.4 Kilka przydatnych pojęć . .. .. 224
8.4.1 Pakiety i ramki . . . ...... . ...... 224
8.4.2 Protokół .... .. ............. .......225
8.4.3 TCP/IP . . . .^r^^^. fy/P^• 227
8.4.4 Usługa DNS ^^^s^ ■ ^^d 228
8.5 Urządzenia sieci komputerowych ...... . . 229
8.5.1 Urządzenia transmisji .. ... 229
8.5.2 Urządzenia dostępowe 230
8.6 Zadania ..... ... .............233
A Podstawowe jednostki i pojęcia w informatyce 235
h
B Kody ASCII 237
C Kodowanie polskich znaków 241
D Organizacje standaryzujące 243
E Rozwiązania zadań 245
E.1 Rozwiązania do rozdziału 2 245
E.2 Rozwiązania do rozdziału 3 248
E.3 Rozwiązania do rozdziału 4 251
E.4 Rozwiązania do rozdziału 5 252
Bibliografia 257
Indeks 260
Spis rysunków 9
1 Wstęp 15
1.1 Czym jest informatyka? IV. 15
1.2 Historia informatyki V^^*L_J ->y^**^ • 17
1.2.1 Bardzo dawno temu /. L . . T^^_ . .^>r O^y . 17
1.2.2 Ostatnie tysiąclecie 19
1.2.3 Wiek XX ^^N^. . J\ Jl . 22
1.3 Zastosowanie i przyszłość . ■0t0—**0^^0t**t0;0^/£^: -O . . 27
1.4 Kierunki współczesnej informatyki 29
1.4.1 Algorytmika ^^«<: > fi\ ft • • • 29
1.4.2 Bazy danych . . .^-*-^T^S^V > ^M .... 30
1.4.3 Grafika komputerowa ~?*>«<^^\ • •« 30
1.4.4 Kryptografia ■//■ ■ ■ ■ ■ -\-\ • • • V 31
1.4.5 Programowanie 31
1.4.6 Sieci komputerowe '/. -XShS 32
1.4.7 Systemy operacyjne •^^!s^/'^53c ^3
1.4.8 Sztuczna inteligencja . . />^/ •^»»s_^ 35
1.4.9 Teoria informacji ./. ^N^ 36
1.5 Zadania ■ ■ ■ Jf -^N- yOS?' 37
2 Podstawowe pojęcia i definicje 39
2.1 Algebra Boole'a .^S>^!*^>^ -J^s* 39
2.1.1 Definicja ogólna . . .ft. >>|j 39
2.1.2 Dwuelementowa algebra Boole'a 44
2.2 Pozycyjne systemy liczbowe 45
2.2.1 System dwójkowy 47
c 2001-2003 by P. Fulmański & Ś. Sobieski, Uniwersytet Łódzki. Wersja RC1 z dnia: 4 stycznia 2004
SPIS TREŚCI
2.2.2 Zapis liczby rzeczywistej w systemie dwójkowym ... 52
2.2.3 Kod szesnastkowy ... . . . . . . . 56
2.2.4 Inne pozycyjne systemy liczbowe . ... . ...... . 57
2.3 BCD .......... 62
2.4 Zadania .. . .... . . ... 67
3 Architektura i działanie komputera 69
3.1 Maszyna Turinga .... ..... . . . ^
3.1.1 Definicja Maszyny Turinga . ... . . . . ... . • • 70
3.2 Bramki logiczne . . 75
3.3 Architektura współczesnego komputera . ... 78
3.4 Procesor — serce komputera . . . .... ..... 83
3.4.1 Cykl pracy procesora . ... ...... ... ^
3.4.2 Rejestry procesora Intel 8086 . . ... .. 86
3.4.3 Budowa rozkazu . .. ... . 89
3.4.4 Adresowanie . . . .. .. 90
3.4.5 Asembler ... ..... 96
3.5 Reprezentacja informacji . . .. ........ .........100
3.5.1 Znaki alfanumeryczne . ... .. .. ... . 100
3.5.2 Liczby naturalne . ... .... 103
3.5.3 Liczby całkowite >-^--^^^. . O. Y 103
3.5.4 Reprezentacja uzupełnień do dwu 105
3.5.5 Liczby rzeczywiste .. ... 109
3.6 Zadania •>^^>^-\\j^ 113
4 Teoria informacji 117
4.1 Informacja vs. wiadomość 117
4.2 Geneza i zakres teorii informacji 118
4.3 Metody kontroli poprawności danych 120
4.3.1 Bit parzystości 121
4.3.2 Suma kontrolna . ..... ................122
4.3.3 Kod CRC . . . (?^? 125
4.4 Zadania .. ...... .................128
5 Algorytmy i struktury danych 129
5.1 Pojęcie algorytmu 129
5.2 Struktury danych 132
5.2.1 Typ danych 132
5.2.2 Tablica . ..... 133
5.2.3 Rekord . /^/ 134
c2001-2003 by P. Fulmański & Ś. Sobieski, Uniwersytet Łódzki. Wersja RC1 z dnia: 4 stycznia 2004
SPIS TREŚCI
5.2.4 Zbiór 136
5.2.5 Plik .......
5.3 Metody opisu algorytmów .. . . . 137
5.3.1 Schemat blokowy ^""^ 137
5.3.2 Schemat zapisu algorytmu za pomocą pseudo-języka . 139
5.4 Podstawowe algorytmy . .. ... . 143
5.4.1 Algorytmy obliczeniowe .. ...... 143
5.4.2 Algorytmy sortowania ...... . . . 144
5.4.3 Algorytmy wyszukujące .... .. . . . 146
5.5 Rekurencja vs. iteracja .... . ... . .
5.6 Analiza złożoności ........ . .
5.7 Zadania ....... 155
6 Języki programowania 157
6.1 Czym jest język programowania? ... . . . 157
6.1.1 Składnia i semantyka .. 159
6.2 Ewolucja języków programowania ..... . 159
6.3 Klasyfikacja języków programowania . . ... . . .. 173
6.3.1 Podział według metodologii programowania 173
6.3.2 Generacje języków programowania . .. . 176
6.4 Kompilacja vs. interpretacja. . . . . . . .. • • 177
6.5 Elementy teorii języków formalnych 183
6.5.1 Gramatyka . . . . rT —*^^Sw • • • (F^L\c- • • • 1^3
6.5.2 Notacja BNF . . . .. ... ... ... \y • ... 184
6.5.3 Notacja przy użyciu diagramów składni 185
7 System operacyjny 187
7.1 Zadania realizowane przez system operacyjny 188
7.2 System operacyjny a architektura komputera 189
7.3 Klasyfikacja systemów operacyjnych ..... 190
7.4 Realizacja zadań . . . ....... 193
7.5 W kierunku systemów wielozadaniowych 196
7.6 Procesy, wątki, .. ... . ............197
7.7 Zarządzanie pamięcią .... .... . . . 198
7.8 System plików .... ...... .... 198
7.9 Czy każdy komputer musi posiadać system operacyjny? . . . 199
7.10 Przykładowe systemy operacyjne 201
7.10.1 Amoeba i Ur^T^f . £^[ 201
7.10.2 Mac OS . ...... .... 202
c2001-2003 by P. Fulmański & Ś. Sobieski, Uniwersytet Łódzki. Wersja RC1 z dnia: 4 stycznia 2004
SPIS TREŚCI
7.10.3 MS-DOS i Windows 204
7.10.4 NetWare //^ ;>-*< • 207
7.10.5 OS/390 rr y^^l • 208
7.10.6 OS/400 ......... . 210
7.10.7 Unix i rodzina . .... . 211
7.11 Zadania .... . . ^^. . 213
8 Sieci komputerowe 215
8.1 Po co mi ona? .. . 215
8.2 Struktura fizyczna sieci . . 216
8.2.1 Zasięg sieci ....... 216
8.2.2 Topologia sieci ........ .......217
8.3 Architektura sieci ....... . ... 218
8.3.1 Architektura równorzędna . . ..... . . 222
8.3.2 Architektura klient-serwer 223
8.4 Kilka przydatnych pojęć . .. .. 224
8.4.1 Pakiety i ramki . . . ...... . ...... 224
8.4.2 Protokół .... .. ............. .......225
8.4.3 TCP/IP . . . .^r^^^. fy/P^• 227
8.4.4 Usługa DNS ^^^s^ ■ ^^d 228
8.5 Urządzenia sieci komputerowych ...... . . 229
8.5.1 Urządzenia transmisji .. ... 229
8.5.2 Urządzenia dostępowe 230
8.6 Zadania ..... ... .............233
A Podstawowe jednostki i pojęcia w informatyce 235
h
B Kody ASCII 237
C Kodowanie polskich znaków 241
D Organizacje standaryzujące 243
E Rozwiązania zadań 245
E.1 Rozwiązania do rozdziału 2 245
E.2 Rozwiązania do rozdziału 3 248
E.3 Rozwiązania do rozdziału 4 251
E.4 Rozwiązania do rozdziału 5 252
Bibliografia 257
Indeks 260