Fulmański.P‘, Informatyka
[ Pobierz całość w formacie PDF ]
Wst¦pdoinformatyki
(Podr¦cznik. WersjaRC1)
1
PiotrFulma«ski
2
cibórSobieski
3
4stycznia2004
1
RC1|ReleaseCondidate1,oznacza,»enieb¦dzie»adnychistotnychmody-
kacji,raczejb¦d¡usuwanewyª¡czniebª¦dy.
2
E-mail: fulmanp@math.uni.lodz.pl
3
E-mail: scibor@math.uni.lodz.pl
2
c
2001-2003 by P. Fulma«ski & . Sobieski, Uniwersytet ódzki. Wersja RC1 z dnia: 4 stycznia 2004
Spistre±ci
Spis tre±ci
3
Spis rysunków
9
1 Wst¦p 15
1.1 Czymjestinformatyka? . . . . . . . . . . . . . . . . . . . . . 15
1.2 Historiainformatyki . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.1 Bardzodawnotemu... . . . . . . . . . . . . . . . . . . 17
1.2.2 Ostatnietysi¡clecie . . . . . . . . . . . . . . . . . . . . 19
1.2.3 WiekXX . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3 Zastosowanieiprzyszªo±¢ . . . . . . . . . . . . . . . . . . . . 27
1.4 Kierunkiwspóªczesnejinformatyki . . . . . . . . . . . . . . . 29
1.4.1 Algorytmika. . . . . . . . . . . . . . . . . . . . . . . . 29
1.4.2 Bazydanych . . . . . . . . . . . . . . . . . . . . . . . 30
1.4.3 Grakakomputerowa . . . . . . . . . . . . . . . . . . 30
1.4.4 Kryptograa . . . . . . . . . . . . . . . . . . . . . . . 31
1.4.5 Programowanie . . . . . . . . . . . . . . . . . . . . . . 31
1.4.6 Siecikomputerowe . . . . . . . . . . . . . . . . . . . . 32
1.4.7 Systemyoperacyjne . . . . . . . . . . . . . . . . . . . 33
1.4.8 Sztucznainteligencja . . . . . . . . . . . . . . . . . . . 35
1.4.9 Teoriainformacji . . . . . . . . . . . . . . . . . . . . . 36
1.5 Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2 Podstawowe poj¦cia i denicje 39
2.1 AlgebraBoole'a. . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.1.1 Denicjaogólna . . . . . . . . . . . . . . . . . . . . . 39
2.1.2 DwuelementowaalgebraBoole'a . . . . . . . . . . . . 44
2.2 Pozycyjnesystemyliczbowe . . . . . . . . . . . . . . . . . . . 45
2.2.1 Systemdwójkowy . . . . . . . . . . . . . . . . . . . . 47
c
2001-2003 by P. Fulma«ski & . Sobieski, Uniwersytet ódzki. Wersja RC1 z dnia: 4 stycznia 2004
4
SPIS TRECI
2.2.2 Zapisliczbyrzeczywistejwsystemiedwójkowym . . . 52
2.2.3 Kodszesnastkowy . . . . . . . . . . . . . . . . . . . . 56
2.2.4 Innepozycyjnesystemyliczbowe . . . . . . . . . . . . 57
2.3 BCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.4 Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3 Architektura idziaªanie komputera 69
3.1 MaszynaTuringa . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.1.1 DenicjaMaszynyTuringa . . . . . . . . . . . . . . . 70
3.2 Bramkilogiczne. . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.3 Architekturawspóªczesnegokomputera. . . . . . . . . . . . . 78
3.4 Procesor|sercekomputera . . . . . . . . . . . . . . . . . . 83
3.4.1 Cyklpracyprocesora. . . . . . . . . . . . . . . . . . . 84
3.4.2 RejestryprocesoraIntel8086 . . . . . . . . . . . . . . 86
3.4.3 Budowarozkazu . . . . . . . . . . . . . . . . . . . . . 89
3.4.4 Adresowanie . . . . . . . . . . . . . . . . . . . . . . . 90
3.4.5 Asembler . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.5 Reprezentacjainformacji. . . . . . . . . . . . . . . . . . . . . 100
3.5.1 Znakialfanumeryczne . . . . . . . . . . . . . . . . . . 100
3.5.2 Liczbynaturalne . . . . . . . . . . . . . . . . . . . . . 103
3.5.3 Liczbycaªkowite . . . . . . . . . . . . . . . . . . . . . 103
3.5.4 Reprezentacjauzupeªnie«dodwu. . . . . . . . . . . . 105
3.5.5 Liczbyrzeczywiste . . . . . . . . . . . . . . . . . . . . 109
3.6 Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4 Teoriainformacji 117
4.1 Informacjavs. wiadomo±¢ . . . . . . . . . . . . . . . . . . . . 117
4.2 Genezaizakresteoriiinformacji . . . . . . . . . . . . . . . . 118
4.3 Metodykontrolipoprawno±cidanych . . . . . . . . . . . . . . 120
4.3.1 Bitparzysto±ci . . . . . . . . . . . . . . . . . . . . . . 121
4.3.2 Sumakontrolna. . . . . . . . . . . . . . . . . . . . . . 122
4.3.3 KodCRC . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.4 Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5 Algorytmy i struktury danych 129
5.1 Poj¦ciealgorytmu . . . . . . . . . . . . . . . . . . . . . . . . 129
5.2 Strukturydanych . . . . . . . . . . . . . . . . . . . . . . . . . 132
5.2.1 Typdanych . . . . . . . . . . . . . . . . . . . . . . . . 132
5.2.2 Tablica . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.2.3 Rekord . . . . . . . . . . . . . . . . . . . . . . . . . . 134
c
2001-2003 by P. Fulma«ski & . Sobieski, Uniwersytet ódzki. Wersja RC1 z dnia: 4 stycznia 2004
SPIS TRECI
5
5.2.4 Zbiór . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.2.5 Plik . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.3 Metodyopisualgorytmów . . . . . . . . . . . . . . . . . . . . 137
5.3.1 Schematblokowy . . . . . . . . . . . . . . . . . . . . . 137
5.3.2 Schematzapisualgorytmuzapomoc¡pseudo-j¦zyka . 139
5.4 Podstawowealgorytmy . . . . . . . . . . . . . . . . . . . . . . 143
5.4.1 Algorytmyobliczeniowe . . . . . . . . . . . . . . . . . 143
5.4.2 Algorytmysortowania . . . . . . . . . . . . . . . . . . 144
5.4.3 Algorytmywyszukuj¡ce . . . . . . . . . . . . . . . . . 146
5.5 Rekurencjavs. iteracja. . . . . . . . . . . . . . . . . . . . . . 148
5.6 Analizazªo»ono±ci . . . . . . . . . . . . . . . . . . . . . . . . 153
5.7 Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6 J¦zyki programowania 157
6.1 Czymjestj¦zykprogramowania? . . . . . . . . . . . . . . . . 157
6.1.1 Skªadniaisemantyka. . . . . . . . . . . . . . . . . . . 159
6.2 Ewolucjaj¦zykówprogramowania . . . . . . . . . . . . . . . . 159
6.3 Klasykacjaj¦zykówprogramowania . . . . . . . . . . . . . . 173
6.3.1 Podziaªwedªugmetodologiiprogramowania . . . . . . 173
6.3.2 Generacjej¦zykówprogramowania . . . . . . . . . . . 176
6.4 Kompilacjavs. interpretacja. . . . . . . . . . . . . . . . . . . 177
6.5 Elementyteoriij¦zykówformalnych. . . . . . . . . . . . . . . 183
6.5.1 Gramatyka . . . . . . . . . . . . . . . . . . . . . . . . 183
6.5.2 NotacjaBNF . . . . . . . . . . . . . . . . . . . . . . . 184
6.5.3 Notacjaprzyu»yciudiagramówskªadni . . . . . . . . 185
7 System operacyjny 187
7.1 Zadaniarealizowaneprzezsystemoperacyjny . . . . . . . . . 188
7.2 Systemoperacyjnyaarchitekturakomputera . . . . . . . . . 189
7.3 Klasykacjasystemówoperacyjnych . . . . . . . . . . . . . . 190
7.4 Realizacjazada« . . . . . . . . . . . . . . . . . . . . . . . . . 193
7.5 Wkierunkusystemówwielozadaniowych . . . . . . . . . . . . 196
7.6 Procesy,w¡tki,... . . . . . . . . . . . . . . . . . . . . . . . . 197
7.7 Zarz¡dzaniepami¦ci¡. . . . . . . . . . . . . . . . . . . . . . . 198
7.8 Systemplików. . . . . . . . . . . . . . . . . . . . . . . . . . . 198
7.9 Czyka»dykomputermusiposiada¢systemoperacyjny? . . . 199
7.10 Przykªadowesystemyoperacyjne . . . . . . . . . . . . . . . . 201
7.10.1 Amoeba . . . . . . . . . . . . . . . . . . . . . . . . . . 201
7.10.2 MacOS . . . . . . . . . . . . . . . . . . . . . . . . . . 202
c
2001-2003 by P. Fulma«ski & . Sobieski, Uniwersytet ódzki. Wersja RC1 z dnia: 4 stycznia 2004
[ Pobierz całość w formacie PDF ]