UCZELNIA WARSZAWSKA
Kierunek INFORMATYKA I EKONOMETRIA
Programowanie komputerów
r.a. 2007/2008
Prowadzący: dr hab. in\
. Kazimierz Worwa, prof. UW MSC
Programowanie komputerów
RAZEM Wykłady Ćwiczenia Laboratoria
40 16 - 24
2
Programowanie komputerów
LITERATURA
Schildt H.:Programowanie: Wydawnictwo RM, Warszawa, 2002.
Aho A.V., Ullman J.D.: Wykłady z informatyki z przykładami w języku
C. Wydawnictwo HELION, Gliwice, 2003.
Loudon K.: Algorytmy w C. Wydawnictwo HELION, Gliwice, 2003.
Reek K.A.: Język C. Wskaz
niki. Wydawnictwo HELION, Gliwice, 2003.
3
Programowanie komputerów
Lokalizacja plików do wykładów
http://members.lycos.co.uk/pkjw84/kw/
logowanie:
nazwa u\
ytkownika 2007/2008
hasło kw
4
Programowanie komputerów
Tematyka przedmiotu
Architektura komputera
Systemy zapisu liczb
Pojęcie algorytmu  rodzaje, sposoby zapisu
Struktura programu w języku C
Procedury i funkcje
Instrukcje sterujące
Typy danych, zmienne i wyra\
enia
Statyczne struktury danych
Dynamiczne struktury danych
Operacje wejścia/wyjścia
Typy zło\
one: struktury i unie
Przykłady typowych algorytmów w języku C
(algorytmy wyszukiwania, sortowania itp.)
Zło\
oność obliczeniowa algorytmów
5
Programowanie komputerów
Programowanie komputerów
Wykład 1
Architektura komputera
Systemy zapisu liczb
Pojęcie algorytmu  rodzaje, sposoby zapisu
Elementy architektury komputerów
Architektura komputera  określa charakterystyczne cechy
komputera, wskazując sposób połączenia i współpracy
elementów składowych.
Architektura komputera określa jego elementy z punktu
widzenia jego u\
ytkownika (programisty)
7
Programowanie komputerów
Elementy architektury komputerów
Pamięć ROM
(oprogramowanie operacyjne)
Układy wyjścia
Układy wejścia
Procesor
- klawiatura - drukarka
- mysz - pamięć dyskowa
- skaner
Pamięć RAM - monitor ekranowy
- pamięć dyskowa
(programy u\
ytkowe)
- ploter
- czytniki
dokumentów
(magnetyczne MICR,
optyczne OCR)
8
Programowanie komputerów
Elementy architektury komputerów
Procesor (jednostka centralna komputera)  urządzenie do
przetwarzania informacji w sposób określony przez
u\
ytkownika. Procesor słu\
y do wykonywania (szybkiego)
elementarnych operacji
Mikroprocesor - procesor wykonany w postaci jednego
mikroukładu o wielkim stopniu scalenia
Mikrokomputer (system mikroprocesorowy)  zespół
elementów umo\
liwiających samodzielną realizację zadań
obliczeniowych. Składa się z mikroprocesora oraz urządzeń
dodatkowych (w tym urządzeń we/wy)
9
Programowanie komputerów
Elementy architektury komputerów
W skład architektury mikroprocesora wchodzą:
układ sterujący, do kierowania przebiegiem obliczeń (z
dekoderem rozkazów) .
zespół rejestrów, do przechowywania wartości danych i
wyników;
jednostka arytmetyczno-logiczna (JAL), do wykonywania
podstawowych (prostych) operacji na danych
Sygnały
sterujące
Rejestry
Argumenty,
procesora
wyniki
Układ
sterujący
JAL
10
Programowanie komputerów
Elementy architektury komputerów
Układ sterujący
Ma za zadanie sterowanie pracą wszystkich pozostałych bloków
mikroprocesora (rejestry, JAL) i mikrokomputera (pamięć,
urządzenia WE/WY).
Układ ten pobiera kolejne rozkazy do wykonania oraz dane
potrzebne do wykonania tej operacji.
Po wykonaniu operacji przekazuje uzyskane wyniki w
odpowiednie miejsce.
W skład układu sterowania wchodzi tzw. dekoder rozkazów i
rejestr rozkazów.
11
Programowanie komputerów
Elementy architektury komputerów
Rejestry mikroprocesora są wykorzystywane przez jednostkę
arytmetyczno-logiczną zazwyczaj jako z
ródło danych dla
wykonywanych operacji lub jako miejsce umieszczenia wyników
Jednostka arytmetyczno-logiczna wykonuje operacje zlecone
przez układ sterowania i ściśle współdziała z rejestrami procesora.
Typowe operacje:
działania arytmetyczne (dodawania, odejmowanie,
porównywanie dwóch liczb, zmiana znaku)
działania logiczne (suma logiczna (OR), iloczyn logiczny (AND),
suma modulo 2 (XOR), negacja)
przesunięcia (w lewo, w prawo),
działania na pojedynczych bitach (ustawianie bitu, zerowanie
bitu, testowanie bitu)
12
Programowanie komputerów
Elementy architektury komputerów
Przesyłanie
danych
Sygnały
sterujące
13
Programowanie komputerów
System dwójkowy
System dwójkowy jest naturalnym systemem informatyki
Jak zapisujemy informację?
Za pomocą zjawisk elektrycznych, magnetycznych, optycznych
Zamiast skomplikowanych pomiarów które by pozwoliły zapisać 10 cyfr
mamy proste i jednoznaczne kodowanie.
" Materiał półprzewodnikowy: gdy przyło\
ymy napięcie w jednym
kierunku przewodzi prąd (prawie idealnie), a w kierunku przeciwnym
nie przewodzi prądu. Mamy wiec dwa stany
" Podobnie jest w magnetyzmie: substancje magnetyczne mo\
na
namagnesować w dwóch kierunkach
Wadą systemu dwójkowego jest długość liczby, np.
(0010001110100101)2 = 213 + 29 + 28 + 27 + 25 + 22 + 20 = (9125)10
14
Programowanie komputerów
Jednostki informacji
Elementarną jednostką informacji jest bit
" Bit jest to podstawowa elementarna jednostka informacji
wystarczająca do zakomunikowania jednego z co najwy\
ej dwóch
jednakowo prawdopodobnych zdarzeń.
" Bit stanowi podstawę zapisu informacji w ró\
nych typach pamięci
komputera.
Wszystkie inne jednostki stanowią ró\
ną wielokrotność bitów.
" Symbolicznie wartość bitu oznacza się jako  0 lub  1
Jest to oznaczenie stosowane w matematyce oraz przy opisie
informacji przechowywanej w pamięci komputera i opisie sposobów
kodowania informacji.
15
Programowanie komputerów
Bajty
" Przyjęło się stosowanie jednostki liczącej 8 bitów, zwanej bajtem
" Bajt to podstawowa komputerowa jednostka informacji
" W praktyce stosujemy kilobajty, megabajty, gigabajty, terabajty,...
Nazwa Liczba bajtów Potoczne rozumienie
Kilobajt (kB) 210 = 1 024 103 (tysiąc)
Megabajt (MB) 220 = 1 048 576 106 (milion)
Gigabajt (GB) 230 = 1 073 741 824 109 (miliard)
Terabajt (TB) 240 = 11 099 511 627 776 1012 (bilion)
Jeden bajt mo\
e reprezentować 256 ró\
nych wartości, które mogą
oznaczać zapisywane informacje
16
Programowanie komputerów
Elementy arytmetyki komputerów
20=1
21=2
22=4
23=8
24=16
25=32
26=64
27=128
bajt (B)= 8 bitów
28=256
29=512
210B=1kB=1024B
220B=MB=1024kB=1024*1024B
230B=1GB=1024MB=1024*1024*1024B
240B=1TB=1024GB=1024*1024*1024KB=...
17
Programowanie komputerów
Systemy zapisu liczb
Na ogół operujemy systemami pozycyjnymi, np. rzymski, dziesiętny.
System pozycyjny tzn. \
e wartość danej cyfry zale\
y od jej
miejsca ( poło\
enia) w ciągu cyfr
 rzymski = system pozycyjny sekwencyjny
 dziesiętny = system pozycyjny wagowy
(xk-1, xk-2,& ,x1,x0 x 1, x 2, x m)
n
L = " ai Bi
i=-m
gdzie: n, m e" 0, N e" 2, ai " {0,....,B-1}
B nazywamy podstawą systemu, zaś ai jest elementem zbioru cyfr
dostępnych w danym systemie
W systemie dziesiętnym: B = 10, ai " { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
"
"
"
18
Programowanie komputerów
Reprezentacja wartości liczbowych
Arytmetyka stałoprzecinkowa (przykłady realizacji)
Naturalny kod dwójkowy
Kod znak  moduł
System uzupełnieniowy do 2
Arytmetyka zmiennoprzecinkowa
zapis cecha-mantysa
19
Programowanie komputerów
Naturalny kod dwójkowy
Liczba X, k+m cyfrowa, z k cyframi przez przecinkiem i m
cyframi po przecinku, reprezentowana jest przez ciąg cyfr
(xk-1, xk-2,& ,x1,x0 x 1, x 2, x m)
Jej wartość mo\
na przedstawić za pomocą wzoru:
-
k 1
"{ ł - }
xi 0,1,..., 1
=
X xiBi
"
=-
i m
gdzie B jest podstawą systemu.
Dla B=2, X nale\
ącego do zbioru liczb całkowitych oraz
xi "{ 0,1 } wzór przyjmuje postać:
k -1
X =
"x 2i
i
i=-m
20
Programowanie komputerów
Naturalny kod dwójkowy
Przykłady:
1001012 = 3710
1010102 = 4210
10.12 = 2,510
101.1012 = 5,62510
110.0112 = 6,37510
21
Programowanie komputerów
Naturalny kod dwójkowy
Konwersja do systemu binarnego
Przy wyznaczaniu reprezentacji całkowitej, kolejnymi
(począwszy od najmniej znaczącej) cyframi w reprezentacji
dwójkowej są reszty z dzielenia liczby przez dwa.
Przy wyznaczaniu części ułamkowej kolejnymi cyframi będą
części całkowite podwajanych pozostałości ułamkowych
(począwszy od najbardziej znaczącej).
Przykład konwersji:
1110 X2
Liczba : Wynik Reszta
11 :2 5 1
5 :2 2 1
2 :2 1 0
Wynik konwersji: 10112
1 :2 0 1
22
Programowanie komputerów
Naturalny kod dwójkowy
Przykład konwersji: 0.12510 X2
Liczba x Wynik Część
całkowita
0.125 *2 0.25 0
0.25 *2 0.5 0
0.5 *2 1 1
Wynik konwersji: 0.12510 X2:0.0012
Wadą naturalnego systemu binarnego jest to, \
e nie mo\
na
przy jego pomocy przedstawić liczb ujemnych
23
Programowanie komputerów
Kod znak  moduł
Jedną z metod reprezentacji liczb ujemnych jest reprezentacja
znak-moduł, w której znak liczby jest kodowany
dwuwartościowo na najbardziej znaczącej pozycji.
Wartość liczby zakodowanej w tym systemie mo\
na policzyć
ze wzoru:
k-2
X = (-1)s
"x 2i
i
i=-m
gdzie s "{ 0,1 } jest kodem znaku liczby
xk-1 xk-2 xk-3 x-m
s ... ... ... ... ... ... ...
24
Programowanie komputerów
Kod znak  moduł
Przykłady:
0110112 = 2710
1110112 = -2710
0101.112 = 5,7510
1101.112 = -5,7510
25
Programowanie komputerów
Kod znak  moduł
Wadami tego systemu są:
podwójna reprezentacja zera (+0, -0):
00002 = 010
10002 = -010
konieczność osobnego przetwarzania znaków argumentowych
przy wykonywaniu operacji arytmetycznych, a zwłaszcza
sposobu wykonywania operacji dodawania i odejmowania
w zale\
ności od znaków operandów.
26
Programowanie komputerów
System uzupełnieniowy do 2 (U2)
Powszechnym sposobem reprezentacji stałoprzecinkowych
liczb znakowych (liczb całkowitych) jest dwójkowy system
uzupełnieniowy do dwóch.
Wartość liczby (xk-1,& ,x1, x0 ...x-m) dana jest wzorem:
k-2
X = -xk-12k -1 +
"x 2i
i
i=-m
kropka dziesiętna
xk-1 xk-2 xk-3 x-m
s ... ... ... ... ... ... ...
27
Programowanie komputerów
System uzupełnieniowy do 2
Przykład konwersji U2 10:
1011U2=  1*23 + 0*22 + 1*21 + 1*20 =  8 + 3 =  510
Najbardziej znaczącą pozycję liczby k-bitowej mo\
emy
traktować jako kod jej znaku.
28
Programowanie komputerów
System uzupełnieniowy do 2
Dalsze przykłady U2 10:
1010U2=  1*23 + 0*22 + 1*21 + 0*20 =  8 + 2 =  610
1101.101U2 =  1*23 + 1*22 + 0*21 + 1*20 + 1*2-1 + 0*2-2 = 1*2-3 =
=  8 + 4 + 1 + 0,5 + 0,125 =  3,62510
29
Programowanie komputerów
System uzupełnieniowy do 2
Ciąg bitów Reprezentowana wartość
0111 7
0110 6
0101 5
0100 4
0011 3
0010 2
0001 1
0000 0
1111
-1
1110
-2
1101
-3
1100
-4
1011
-5
1010
-6
1001
-7
1000
-8
30
Programowanie komputerów
Potoczne rozumienie pojęcia  algorytm
Potocznie algorytm jest rozumiany jako pewien przepis na
wykonanie zestawu czynności, prowadzących do osiągnięcia
oczekiwanego i z góry określonego celu
Dzisiejsze, uogólnione znaczenie słowa algorytm:
zbiór reguł postępowania, umo\
liwiających rozwiązanie
określonego zadania w skończonej liczbie kroków i w skończonym
czasie
Dziedzina wiedzy zajmującą się badaniem algorytmów nazywa się
algorytmiką
31
Programowanie komputerów
Pojęciowy model algorytmu
Algorytm mo\
e być rozumiany jako pewne odwzorowanie f,
które dla określonego zestawu danych wejściowych We
generuje określony zestaw danych wyjściowych Wy:
f: We Wy
Dane Dane
f
wejściowe We wyjściowe Wy
32
Programowanie komputerów
Sposoby zapisu algorytmów
Algorytm powinien precyzyjnie opisywać kolejne jego kroki.
Do przedstawienia algorytmu stosuje się:
opis werbalny,
zapis formalny, np.:
zapisy graficzne (schematy blokowe),
formalne specyfikacje programów (np.VDM)
zapisy w postaci pseudokodu (paraprogramu)
zapis algorytmu w dowolnym języku programowania
33
Programowanie komputerów
Język programowania
Język programowania jest środkiem umo\
liwiającym zapis
algorytmów w postaci zrozumiałej dla człowieka, a równocześnie
przetwarzalnej do postaci zrozumiałej dla komputera.
Przetworzenie
programu
z
ródłowego
w kod
maszynowy
Kod z
ródłowy programu
Kod wynikowy programu
(w języku programowania)
(w języku maszynowym)
34
Programowanie komputerów
Klasyfikacja algorytmów
Rozwa\
ać będziemy następujące klasy algorytmów:
algorytmy sekwencyjne - algorytmy równoległe;
algorytmy numeryczne - algorytmy nienumeryczne;
algorytmy rekurencyjne - algorytmy iteracyjne.
35
Programowanie komputerów
Przykład - pierwiastki równania kwadratowego
ax2 + bx + c = 0
Algorytm równoległy: Algorytm sekwencyjny:
START
START
"=b2-4ac
"
"
"
"=b2-4ac
"
"
"
x1=(-b-sqrt("
"))/2a
"
"
x1=(-b-sqrt(" "))/2a
"))/2a x2=(-b+sqrt("
" "
" "
x2=(-b+sqrt("
"))/2a
"
"
Wypisz x1, x2
Wypisz x1, x2
STOP
STOP
36
Programowanie komputerów
Wywołanie funkcji rekurencyjnej
Rekurencja oznacza wywołanie funkcji (procedury) przez tę
samą funkcję (procedurę)
Niepo\
ądana cecha definicji rekurencyjnych: aby wyznaczyć
n-tą wartość trzeba najpierw wyznaczyć wszystkie
 wcześniejsze wartości
Wa\
ne jest, aby kolejne wywołania funkcji (procedury)
rekurencyjnej były realizowane dla kolejnych wartości
parametrów formalnych w taki sposób, aby nie doszło do
zjawiska  nieskończonej pętli rekurencyjnych wywołań funkcji
37
Programowanie komputerów
Przykład obliczania n! dla n=5
Algorytm rekurencyjny: Algorytm iteracyjny
START
START
Silnia = 1
= 5 * 4!
i=1
= 44**3!
= 3!
N
= 3 * 2!
3 * 2!
id"
d"5
d"
d"
= 2 *1!
2* 1!
T
Silnia = Silnia*i
= 1 1
i=i+1
STOP
STOP
38
Programowanie komputerów
Przykłady funkcji rekurencyjnych
Funkcja  silnia :
1 dla n=0 (warunek zakończenia rekurencji)
n!=
n*(n-1)! dla n>0
Definicja pewnego ciągu liczb wymiernych:
1 dla n=0 (warunek zakończenia rekurencji)
f(n)=
f(n-1) + 1/f(n-1), dla n>0,
określa ciąg o wartościach:
1, 2, 5/2, 29/10, 941/290, 969581/272890,.................
39
Programowanie komputerów
Funkcja rekurencyjna  ciąg Fibonacciego
Ciąg Fibonacciego :
n dla n<2
Fib(n)=
Fib(n-2) + Fib(n-1) dla n>=2
Rekurencyjna implementacja w języku C:
long int Fib (int n)
{
Czy na pewno stos programu
if (n<2)
 wytrzyma taką realizację
funkcji
return n;
rekurencyjnej Fib?
else
return Fib(n-2) + Fib (n-1);
}
40
Programowanie komputerów
Jak procesor  widzi program?
Pisząc program w języku programowania widzimy jego
polecenia, instrukcje sterujące, zmienne, stałe itp.
Procesor potrafi jedynie wykonywać polecenia ze swojej listy
rozkazów(w postaci) języka maszynowego, czyli tzw.
assemblera.
Za przeniesienie programu z postaci z
ródłowej w języku
programowania do języka maszynowego procesora jest
odpowiedzialny  kompilator języka programowania
Przetworzenie
programu
z
ródłowego
w kod
maszynowy
Kod z
ródłowy programu
Kod wynikowy programu
(w języku programowania)
(w języku maszynowym)
41
Programowanie komputerów
42
Programowanie komputerów