Pojęcia podstawowe
Informatyka dziedzina wiedzy i działalności zajmująca się gromadzeniem,
przetwarzaniem i wykorzystywaniem informacji z zastosowaniem
środków technicznych (komputerów).
Dane wartości określonego typu, opisujące wybrane własności
obiektów lub procesów
Informacje wyniki gromadzenia i przetwarzania danych, które prowadzą do
rozszerzenia wiedzy posiadanej przez odbiorcę
Wśród zagadnień składających się na dziedzinę informatyki można wyróżnić:
sprzęt służący do obliczeń
metody przetwarzania danych (algorytmy)
implementacja tych metod (programowanie)
W literaturze zachodniej na określenie tej dziedziny używa się często terminu
Information Technology.
1/22
Budowa sprzętu komputerowego
Literatura do rozdziału
[1] J.Lobur L.Null. The essentials of computer organization and architecture.
3 Ed. Jones and Bartlett Publishers, 2010.
[2] W.Stallings. Organizacja i architektura systemu komputerowego. WNT,
2000.
2/22
Historia rozwoju
Generacja zero: mechaniczne maszyny kalkulacyjne (1642 1945)
Wilhelm Schickard (1592 1635) jest uważany za twórcę pierwszego
mechanicznego kalkulator, nazwanego Calculating Clock. Mógł on dodawać i
odejmować liczby o maks. 6 cyfrach.
W 1642 r. Blaise Pascal (1623 1662) zbudował mechaniczny kalkulator nazwany
Pascaline aby pomóc swemu ojcu w obliczeniach podatkowych. Pascaline mógł
realizować dodawanie z przeniesieniem i odejmowanie.
Gottfried Wilhelm von Leibniz (1646 1716), znany matematyk, wynalazł
kalkulator o nazwie Stepped Reckoner, który mógł realizować dodawanie,
odejmowanie, mnożenie i dzielenie.
Charles Babbage (1791 1871) zbudował maszyne różnicową Difference Engine w
1822, która mechanizowała rozwiązywanie wielomianów i właściwie była
kalkulatorem, nie komputerem. Babbage zaprojektował też w 1833 r. uniwersalną
maszynę liczącą, nazwaną maszyną analityczną Analytical Engine, która mogła
realizować dowolne operacje matematyczne. Analytical Engine posiadała wiele
cech wiązanych z nowoczesnymi komputerami: jednostkę arytmetyczno-logiczną
do wykonywania obliczeń (Babbage nazywał ją młynem - mill), pamięć (store) i
urządzenia wejścia-wyjścia. Babbage zaprojektował też możliwość warunkowego
rozgałęzienia programu. Ada, Countess of Lovelace i córka poety Lorda Byrona,
zasugerowała aby Babbage napisał program (plan działania) dla tej maszyny w
celu obliczeń liczbowych. Ten fakt jest pierwszym znanym przykładem programu
komputerowego, a Ada jest uważana za pierwszego programistę komputerów.
Babbage zaprojektował użycie kart perforowanych jako nośnika danych we/wy i
programu. Użycie kart dla sterowania działaniem nie pochodziło od Babbage a,
ale od Joseph-Marie Jacquard a (1752 1834), konstruktora maszyn tkackich.
3/22
Historia rozwoju
Generacja 1: komputery lampowe (1945 1953)
W latach 1930-tych, Konrad Zuse (1910 1995) kontynuując prace Babbage a,
zastosował układy elektryczne do budowy urządzenia wg projektu Babbage a.
Komputer Zuse go, nazwany Z1, był zbudowany na przekaz
nikach
elektromechanicznych zamiast ręcznie napędzanych tarcz stosowanych przez
Babbage a. Komputer Z1 był programowalny i posiadał pamięć, jednostkę
arytmetyczną i jednostkę sterującą. Z powodu braku funduszy w Niemczech
czasu II wojny światowej, Zuse używał taśmy filmowej w miejsce kart
perforowanych jako nośnika danych wejściowych.
John Mauchly (1907 1980) i J. Presper Eckert (1929 1995) byli głównymi
twórcami komputera ENIAC, wprowadzonego do użytku w 1946 r. ENIAC jest
uważany za pierwszy całkowicie elektroniczny, uniwersalny komputer cyfrowy.
Maszyna ta używała 17,468 lamp elektronowych, zajmowała 1,800 stóp kw.
powierzchni, ważyła 30 ton i zużywała 174 kilowatów mocy. ENIAC miał pamięć
o pojemności około 1000 bitów (około 20 10-cyfrowych liczb dziesiętnych) i
używał kart perforowanych do zapisu danych. ENIAC był przeznaczony do
przyspieszenia procesu obliczenia tablic balistycznych dla artylerii w końcu II
wojny światowej.
ENIAC był maszyną pracującą w systemie dziesiętnym, nie dwójkowym. To
znaczy, że liczby były reprezentowane w formie dziesiętnej i działania
arytmetyczne były wykonywane w systemie dziesiętnym. Pamięć składała się z 20
 akumulatorów , z których każdy mógł przechowywać 10-cio cyfrową liczbę
dziesiętną.
Główną wadą ENIAC-a była konieczność programowania ręcznego poprzez
przełączniki i połączenia przewodami.
4/22
Historia rozwoju
The ENIAC, 1946
5/22
Historia rozwoju
Główne kategorie sprzętu
obliczeniowego:
Proste maszyny liczące
(program sprzętowy), np.
maszyna szyfrująca Enigma,
używająca wirujących tarcz
kodujących, kalkulatory
elektroniczne)
Uniwersalne komputery,
(program ładowany do
pamięci). Proces
programowania jest
ułatwiony przez fakt, że
program jest reprezentowany
w formie pozwalającej na
przechowywanie go w
pamięci obok danych.
Komputer może pobierać
kolejne instrukcje programu z
pamięci do wykonania,
ponadto program może być
modyfikowany przez zmianę
Figure: Sprzętowe i programowe podejście do
wartości zawartych w
obliczeń [2]
pamięci.
6/22
Historia rozwoju
Architektura von Neumann a
Koncepcja tej architektury (opublikowana przez von Neumann a w 1945 r.), była
oparta na pracach Johna Mauchly i J. Presper Eckert, twórców ENIAC a.
Komputer von Neumann a składa
się z:
pamięci przechowującej dane
i instrukcje programu
jednostki sterującej, która
pobiera rozkazy z pamięci,
interpretuje je i powoduje ich
wykonanie w sposób zależny
od wartości danych
jednostki
arytmetyczno-logicznej
(ALU), która wykonuje
działania arytmetyczne i inne
(logiczne, przesunięcia, itd.)
na danych
układów wejścia-wyjścia,
działających pod kontrolą
Figure: Architektura von Neumann a [1]
jednostki sterującej
Taki system przesyła wszystkie dane przez jednostkę arytmetyczno-logiczną (dokładnie
- przez akumulator, który jest częścią ALU), co jest powodem wąskiego gardła (von
Neumann bottleneck).
7/22
Historia rozwoju
Zmodyfikowana architektura von Neumann a
Opisana architektura została zoptymalizowana przez wprowadzenie magistral (system
bus model).
Magistrala danych (data bus)
przesyła dane między pamięcią
główną a rejestrami procesora
(CPU).
Magistrala adresowa (address
bus) utrzymuje adres danej, która
jest przesyłana.
Magistrala sterująca (control bus)
rozprowadza sygnały sterujące
przepływem danych w systemie.
Inne ulepszenia podstawowej architektury von Neumann a to: wykorzystanie rejestrów
indeksowych (index registers) do adresowania, obsługa danych zmiennoprzecinkowych
(floating point data), użycie przerwań (interrupts) i asynchronicznych operacji
wejścia/wyjścia (asynchronous I/O), wprowadzenie pamięci wirtualnej (virtual
memory) i rejestrów ogólnego przeznaczenia (general registers).
8/22
Komputer IAS - pierwszy przykład architektury von Neumann a
Zbudowany w Princeton Institute for
Advanced Studies. IAS działa
powtarzając wykonywanie cyklu
rozkazu. Każdy cykl rozkazu składa
się z dwu części:
Cyklu pobrania (fetch cycle), w
którym kod operacji następnej
instrukcji jest ładowany do
rejestru IR a pole adresu jest
ładowane do rejestru MAR.
Instrukcja może być pobrana z
rejestru IBR, lub z pamięci
poprzez załadowanie słowa do
rejestru MBR, a potem do IBR,
IR i MAR.
Cyklu wykonania, który zaczyna
się gdy kod operacji jest w
rejestrze IR. Jednostka sterująca
interpretuje kod operacji i
wykonuje instrukcję, wysyłając
odpowiednie sygnały sterujące
tak aby przesłać dane lub
wykonać działania arytmetyczne
w ALU. 9/22
Figure: Schemat blokowy komputera IAS
Komputer IAS
Zbiór rejestrów
Jednostka sterująca i ALU zawierają specjalne komórki pamięci, nazywane rejestrami,
o następującym przeznaczeniu:
Rejestr buforowy pamięci (Memory buffer register) (MBR): przechowuje słowo,
które ma być zapisane do pamięci lub układu wyjścia, lub słowo które ma być
odczytane z pamięci lub układu wejścia.
Rejestr adresowy pamięci (Memory address register) (MAR): przechowuje adres
w pamięci słowa, które ma być zapisane z lub odczytane do rejestru MBR.
Rejestr rozkazu (Instruction register) (IR): zawiera 8-bitowy kod operacji
instrukcji właśnie wykonywanej.
Rejestr buforowy rozkazu (Instruction buffer register) (IBR): przechowuje
tymczasowo prawostronną instrukcję z bieżącego słowa pamięci.
Licznik programu (Program counter) (PC): zawiera adres następnej pary
instrukcji do do pobrania z pamięci.
Akumulator (Accumulator) (AC) i multiplier quotient (MQ): przechowuje
tymczasowo argumenty i rezultaty operacji ALU. na przykład, rezultat mnożenia
dwu liczb 40-bitowych jest liczbą 80-bitową; najbardziej znaczące 40 bitów sa
zapisywane we AC, a najmniej znaczące w MQ.
10/22
Komputer IAS
Organizacja pamięci
Pamięć komputera IAS składała się z 1000 komórek, zwanych słowami, każde o
długości 40 liczb binarnych (bitów). Zarówno program jak i dane były przechowywane
w tej pamięci. Liczby i instrukcje były reprezentowane w formie binarnej.
Liczby były reprezentowane z użyciem bitu znaku i 39-bitów kodujących wartość.
Słowo mogło też przechowywać dwie 20-bit instrukcje. Każda z nich składała się z
8-bitowego kodu operacji (opcode) określającego operację do wykonania i 12-bitowego
adresu określającego jedno ze słów w pamięci (numerowanych do 0 do 999).
Figure: Organizacja pamięci komputera IAS [2]
11/22
Komputer IAS
Zbiór instrukcji
Komputer IAS miał
21 instrukcji, w 5
grupach:
Przesyłanie danych:
między pamięcią a
rejestrami ALU lub
między dwoma
rejestrami ALU.
Skok bezwarunkowy:
Normalnie, jednostka
sterująca wykonuje
instrukcje kolejno. Aby
to zmienić, wykonuje się
skok bezwarunkowy
(realizacja pętli).
Skok warunkowy:
rozgałęzienie oparte o
warunek, pozwala
realizować decyzje.
Arytmetyczne: operacje
wykonywane przez ALU.
Modyfikacja adresu:
umożliwia obliczenie
nowego adresu i
wstawienie go do
instrukcji w pamięci.
12/22
Model warstwowy systemu komputerowego
Figure: Model warstwowy systemu komputerowego [1]
13/22
Arytmetyka komputerów
Dwójkowy system liczbowy - przedstawienie liczb naturalnych
System dwójkowy jest systemem pozycyjnym (tak jak dziesiętny), co oznacza,
że waga danej cyfry zależy od jej pozycji w liczbie.
Liczby naturalne
Dla liczby A, jej reprezentacja (zwana inaczej rozwinięciem) dana jest
zależnością:
A = bn-1 " 2n-1 + ... + b1 " 21 + b0 " 20
gdzie bi jest i-tym bitem (cyfrą binarną), a n jest ilością bitów rozwinięcia.
Na przykład:
liczba dwójkowa 110012
oznacza liczbę dziesiętną 25 = 24 + 23 + 20
14/22
Dwójkowy system liczbowy
Liczby całkowite ujemne - reprezentacja znak-moduł
Bit znaku poprzedza właściwe bity liczby - jest bitem najbardziej znaczącym.
Gdy najbardziej znaczący bit jest równy 0, to liczba jest dodatnia i jej wartość
oblicza się ze wzoru:
A = bn-2 " 2n-2 + ... + b1 " 21 + b0 " 20
Gdy najbardziej znaczący bit jest równy 1, to liczba jest ujemna i jej wartość
oblicza się ze wzoru:
A = -(bn-2 " 2n-2 + ... + b1 " 21 + b0 " 20)
Na przykład:
010010112 = 1 " 26 + 1 " 23 + 1 " 21 + 1 " 20 = 7510
110010112 = -(1 " 26 + 1 " 23 + 1 " 21 + 1 " 20) = -7510
Wady tej reprezentacji:
Dodawanie i odejmowanie wymagają rozważania zarówno znaków jak i modułów
liczb
Istnieją dwie reprezentacje liczby 0 (000000002 i 100000002)
15/22
Liczby całkowite ujemne
Reprezentacja U2 (uzupełnienia do dwóch, czyli podstawy systemu liczbowego)
Podobnie jak w reprezentacji znak-moduł, najbardziej znaczący bit jest bitem
znaku, tutaj jednak ma wagę 2n-1 i znak ujemny. Dla liczby całkowitej jej
przedstawienie w tym kodzie jest dane wzorem:
A = -bn-1 " 2n-1 + bn-2 " 2n-2 + ... + b1 " 21 + b0 " 20
Jeśli A jest dodatnie, to bit znaku bn-1 jest zerem. Pozostałe bity reprezentują
moduł liczby w identyczny sposób jak w reprezentacji znak-moduł
Zero jest traktowane jak wartość dodatnia i dlatego ma bit znaku 0 i moduł
złożony z samych zer. Stąd zakres dodatnich liczb całkowitych to [0, 2n-1 - 1] ,
czyli dla n=8 zakres ten to [0, 127] (z wartością maksymalną gdy wszystkie bity
modułu są 1). Większe liczby wymagają więcej bitów w słowie
Dla liczb ujemnych bit znaku bn-1 jest 1. Pozostałe n-1 bity określają dowolną z
2n-1 wartości, stąd zakres tych liczb to [-2n-1, -1], czyli dla n=8 zakres ten to
[-128, -1]
Zalety reprezentacji U2:
zapewnia jednolitą realizację dodawania i odejmowania, dlatego jest powszechnie
używana jako reprezentacja liczb całkowitych w większości procesorów
brak podwójnej reprezentacji zera, stąd zwiększony o 1 zakres liczb możliwych do
przedstawienia
16/22
Liczby całkowite ujemne
U2 - przykład, Konwersja liczb binarnych dla różnych długości słów
Na przykład:
010010112 = 1 " 26 + 1 " 23 + 1 " 21 + 1 " 20 = 7510
101101012 = -1 " 27 + 1 " 25 + 1 " 24 + 1 " 22 + 1 " 20 = -7510
Konwersja liczb binarnych dla różnych długości słów
Jeśli należy rozszerzyć ilość bitów liczby z n do m, (przy czym n < m) to:
Dla reprezentacji znak-moduł należy przesunąć bit znaku do najdalszej
lewej pozycji, a pozostałe wolne bity wypełnić zerami
Dla reprezentacji uzupełnienia do dwóch należy przesunąć bit znaku do
najdalszej lewej pozycji, a pozostałe wolne bity wypełnić kopiami bitu
znaku (dla liczb dodatnich wypełnia się zerami, dla liczb ujemnych 
jedynkami).
17/22
Konwersja między systemami dziesiętnym i binarnym
Konwersja dziesiętnej liczby całkowitej dodatniej
Konwersja z postaci binarnej na dziesiętną jest prosta i wynika bezpośrednio z
rozwinięcia
Konwersja liczby całkowitej dodatniej z postaci dziesiętnej na binarną jest
wykonywana metodą dzielenia przez 2. Jeśli mamy liczbę dziesiętną N to po
podzieleniu jej przez 2 otrzymujemy iloraz N1 oraz resztę r1, zgodnie z
zależnością:
N = 2 " N1 + r1 , gdzie r1 jest 0 lub 1
Następnie dzielimy iloraz N1 przez 2, otrzymując nowy iloraz N2 oraz resztę r2:
N1 = 2 " N2 + r2 , gdzie r2 jest 0 lub 1
Stąd:
N = 2 " (2 " N2 + r2) + r1 = 22 " N2 + 21 " r2 + 20 " r1
Ponieważ N > N1 > N2..., postępujemy tak dalej aż do otrzymania ilorazu
Nk = 1 i reszty rk równej 0 lub 1.
Algorytm konwersji z postaci dziesiętnej na binarną
Konwersja jest wykonywana metodą dzielenia przez 2. Kolejne reszty rk i ostatni iloraz
Nk = 1 dają cyfry binarne w kolejności rosnącego znaczenia.
Czy to znaczy, że zawsze MSB (najbardziej znaczący bit) jest równy 1?
NIE, to zależy od przzyjętej długości słowa: kiedy jest dłuższe niż trzeba dla
danej liczby, pozostałe bity będą zerami.
The division-remainder method employs the idea that successive divisions by the
base are in fact successive subtractions by powers of the base. The remainders
that we get when we sequentially divide by the base end up being the digits of
the result, which are read from bottom to top.
18/22
Konwersja między systemami dziesiętnym i binarnym
Konwersja dziesiętnej liczby całkowitej dodatniej - przykłady
1310 = 11012 1610 = 100002
13 : 2 = 6 r 1 16 : 2 = 8 r 0
6 : 2 = 3 r 0 8 : 2 = 4 r 0
3 : 2 = 1 r 1 4 : 2 = 2 r 0
2 : 2 = 1 r 0
19/22
Konwersja między systemami dziesiętnym i binarnym
Konwersja dziesiętnej liczby całkowitej ujemnej
Aby przekształcić liczbę całkowitą ujemną do postaci binarnej należy:
1
wykonać konwersję liczby dodatniej o tym samym module
2
zanegować ją (patrz poniżej):
Dla reprezentacji znak-moduł negowanie sprowadza się do odwrócenia bitu
znaku
Dla reprezentacji uzupełnienia do dwóch należy wziąć uzupełnienie Boole a
każdego bitu liczby (łącznie z bitem znaku) i traktując wynik jako liczbę
całkowitą bez znaku dodać 1.
UWAGA: występują tu dwa przypadki szczególne, które muszą być
odpowiednio traktowane:
1
A = 0. Wtedy A = 000000002 w reprezentacji U2. Uzupełnienie bitowe
111111112. Po dodaniu do niego 1 otrzymujemy przeniesienie, które jest
ignorowane, tak że w rezultacie otrzymujemy poprawny wynik negacji zera
równy zero.
2
Negowanie wzoru bitowego złożonego z 1 z następującymi n - 1 zerami
daje w wyniku tę samą liczbę. Na przykład:
-12810 = 100000002. Uzupełnienie bitowe = 011111112. Po dodaniu do
niego 1 otrzymujemy 100000002 = -12810. Problem powstaje, ponieważ
12810 nie może być reprezentowane na 8 bitach.
20/22
Arytmetyka liczb całkowitych
Dodawanie
Przy przyjętej długości słowa, możemy otrzymać wynik większy niż
dopuszczalny  występuje wtedy tzw. przepełnienie. Taki przypadek jest
odpowiednio sygnalizowany przez ALU i wynik operacji jest odrzucany.
Reguła przepełnienia
Jeśli są dodawane dwie liczby dodatnie lub dwie ujemne, to przepełnienie
występuje wtedy i tylko wtedy, gdy wynik ma znak przeciwny
W pewnych warunkach może wystąpić tzw. przeniesienie - poza końcem słowa
pojawia się bit, który musi być ignorowany.
21/22
Dwójkowy system liczbowy
Dodawanie liczb całkowitych - przykłady
(-7) + (+5) = (-2) (-4) + (+4) = (0)
1001 1100
0101 0100
    
1110 = -2 10000 przeniesienie, bit ignorowany
0000 = 0
(+4) + (+5) = (?)
(-4) + (-1) = (-5)
0100
0101 1100
   1111
1001 przepełnienie, zgodnie z
  
regułą: wynik jest ujemny,
11011 przeniesienie, bit ignorowany
a oba argumenty dodatnie
1011 = -5
22/22