Programowanie komputerów

Prowadzący:

dr hab. inż. Kazimierz Worwa, prof. UW MSC

r.a. 2007/2008

UCZELNIA WARSZAWSKA

Kierunek INFORMATYKA I EKONOMETRIA

2

Programowanie komputerów

24

-

16

40

Laboratoria

Ć

wiczenia

Wykłady

RAZEM

Programowanie komputerów

3

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. Wska

ź

niki. Wydawnictwo HELION, Gliwice, 2003.

4

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

5

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

Programowanie komputerów

Wykład 1

Architektura komputera

Systemy zapisu liczb

Poj

ę

cie algorytmu – rodzaje, sposoby zapisu

7

Programowanie komputerów

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)

8

Programowanie komputerów

Procesor

Pamięć ROM

Pamięć RAM

(oprogramowanie operacyjne)

(programy użytkowe)

Układy wejścia

Układy wyjścia

- klawiatura
- mysz
- skaner
- pamięć dyskowa

- drukarka
- pamięć dyskowa

- monitor ekranowy

- ploter

- czytniki

dokumentów

(magnetyczne MICR,

optyczne OCR)

Elementy architektury komputerów

9

Programowanie 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)

Elementy architektury komputerów

10

Programowanie 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

Rejestry

procesora

JAL

Układ

sterujący

Sygnały

sterujące

Argumenty,

wyniki

Elementy architektury komputerów

11

Programowanie 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.

Elementy architektury komputerów

12

Programowanie komputerów

Rejestry mikroprocesora s

ą

wykorzystywane przez jednostk

ę

arytmetyczno-logiczn

ą

zazwyczaj jako

ź

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)

Elementy architektury komputerów

13

Programowanie komputerów

Przesyłanie

danych

Sygnały

sterujące

Elementy architektury komputerów

14

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

= 2

13

+ 2

9

+ 2

8

+ 2

7

+ 2

5

+ 2

2

+ 2

0

= (9125)

10

15

Programowanie komputerów

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

.

Jednostki informacji

16

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

,...

Jeden bajt mo

ż

e reprezentowa

ć

256 ró

ż

nych warto

ś

ci,

które mog

ą

oznacza

ć

zapisywane informacje

10

3

(tysi

ą

c)

2

10

= 1 024

Kilobajt (kB)

10

12

(bilion)

2

40

= 11 099 511 627 776

Terabajt (TB)

10

9

(miliard)

2

30

= 1 073 741 824

Gigabajt (GB)

10

6

(milion)

2

20

= 1 048 576

Megabajt (MB)

Potoczne rozumienie

Liczba bajtów

Nazwa

17

Programowanie komputerów

Elementy arytmetyki komputerów

2

0

=1

2

1

=2

2

2

=4

2

3

=8

2

4

=16

2

5

=32

2

6

=64

2

7

=128

2

8

=256

2

9

=512

2

10

B=1kB=1024B

2

20

B=MB=1024kB=1024*1024B

2

30

B=1GB=1024MB=1024*1024*1024B

2

40

B=1TB=1024GB=1024*1024*1024KB=...

bajt (B)= 8 bitów

18

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

(x

k-1

, x

k-2

,…,x

1

,x

0

x

–1

, x

–2

, x

–m

)

gdzie:

n, m ≥ 0, N

≥

2, a

i

∈

{0,....,B-1}

B

nazywamy podstaw

ą

systemu, za

ś

a

i

jest elementem zbioru cyfr

dost

ę

pnych w danym systemie

W systemie dziesi

ę

tnym:

B = 10, a

i

∈

∈

∈

∈

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

L =

∑

a

i

B

i

i=-m

n

19

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

20

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

(x

k-1

, x

k-2

,…,x

1

,x

0

x

–1

, x

–2

, x

–m

)

Jej warto

ść

mo

ż

na przedstawi

ć

za pomoc

ą

wzoru:

gdzie B jest podstaw

ą

systemu.

Dla B=2, X nale

żą

cego do zbioru liczb ca

ł

kowitych oraz

wzór przyjmuje posta

ć

:

∑

−

−

=

=

1

k

m

i

i

i

B

x

X

}

{

1

,...,

1

,

0

x

i

−

∈

Β

}

{

1

,

0

x

i

∈

∑

−

−

=

=

1

2

k

m

i

i

i

x

X

21

Programowanie komputerów

Naturalny kod dwójkowy

Przykłady:

100101

2

= 37

10

101010

2

= 42

10

10.1

2

= 2,5

10

101.101

2

= 5,625

10

110.011

2

= 6,375

10

22

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:

11

10

X

2

Liczba

:

Wynik Reszta

11

:2

5

1

5

:2

2

1

2

:2

1

0

1

:2

0

1

Wynik konwersji: 1011

2

23

Programowanie komputerów

Naturalny kod dwójkowy

Przykład konwersji: 0.125

10

X

2

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.125

10

X

2

:0.001

2

Wadą naturalnego systemu binarnego jest to, że nie można
przy jego pomocy przedstawić liczb ujemnych

24

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:

∑

−

−

=

−

=

2

2

)

1

(

k

m

i

i

i

s

x

X

gdzie

jest kodem znaku liczby

}

{

1

,

0

s

∈

x

k-1

x

k-2

x

k-3

x

−

m

s

...

...

...

...

...

...

...

25

Programowanie komputerów

Kod znak – moduł

Przykłady:

011011

2

= 27

10

111011

2

=

−

27

10

0101.11

2

= 5,75

10

1101.11

2

=

−

5,75

10

26

Programowanie komputerów

Kod znak – moduł

Wadami tego systemu s

ą

:

podwójna reprezentacja zera (+0, -0):

0000

2

= 0

10

1000

2

= -0

10

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.

27

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 (x

k-1

,…,x

1

, x

0

...x

-m

) dana jest wzorem:

∑

−

−

=

−

−

+

−

=

2

1

1

2

2

k

m

i

i

i

k

k

x

x

X

x

k-1

x

k-2

x

k-3

x

−

m

s

...

...

...

...

...

...

...

kropka dziesiętna

28

Programowanie komputerów

System uzupełnieniowy do 2

Przyk

ł

ad konwersji U2

10:

1011

U2

= –1*2

3

+ 0*2

2

+ 1*2

1

+ 1*2

0

= – 8 + 3 = – 5

10

Najbardziej znacz

ą

c

ą

pozycj

ę

liczby k-bitowej mo

ż

emy

traktowa

ć

jako kod jej znaku.

29

Programowanie komputerów

System uzupełnieniowy do 2

Dalsze przykłady U2

10:

1010

U2

= –1*2

3

+ 0*2

2

+ 1*2

1

+ 0*2

0

= – 8 + 2 = – 6

10

1101.101

U2

= –1*2

3

+ 1*2

2

+ 0*2

1

+ 1*2

0

+ 1*2

-1

+ 0*2

-2

= 1*2

-3

=

= – 8 + 4 + 1 + 0,5 + 0,125 = – 3,625

10

30

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

31

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

ą

32

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

wejściowe

We

Dane

wyjściowe

Wy

f

33

Programowanie komputerów

S

posoby 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

34

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.

Kod źródłowy programu
(w języku programowania)

Kod wynikowy programu
(w języku maszynowym)

Przetworzenie

programu

źródłowego

w kod

maszynowy

35

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.

36

Programowanie komputerów

Przykład - pierwiastki równania kwadratowego

START

STOP

∆∆∆∆

=b

2

-4ac

x

1

=(-b-sqrt(

∆∆∆∆

))/2a

x

2

=(-b+sqrt(

∆∆∆∆

))/2a

Wypisz x

1

, x

2

START

STOP

∆∆∆∆

=b

2

-4ac

x

1

=(-b-sqrt(

∆∆∆∆

))/2a

x

2

=(-b+sqrt(

∆∆∆∆

))/2a

Wypisz x

1

, x

2

Algorytm równoległy: Algorytm sekwencyjny:

0

c

bx

ax

2

=

+

+

37

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”

38

Programowanie komputerów

Przykład obliczania n! dla n=5

Algorytm rekurencyjny: Algorytm iteracyjny

START

STOP

= 5 * 4!

= 4 * 3!

3 * 2!

2 * 1!

1

= 4 * 3!

= 3 * 2!

= 2 * 1!

= 1

START

STOP

Silnia = 1

i=1

i

≤≤≤≤

5

Silnia = Silnia*i

i=i+1

T

N

39

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,.................

40

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)

{

if (n<2)

return n;

else

return Fib(n-2) + Fib (n-1);

}

Czy na pewno stos programu

„wytrzyma” taką realizację

funkcji

rekurencyjnej Fib?

41

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

ź

ródłowej w j

ę

zyku

programowania do j

ę

zyka maszynowego procesora jest

odpowiedzialny „kompilator j

ę

zyka programowania”

Kod źródłowy programu
(w języku programowania)

Kod wynikowy programu
(w języku maszynowym)

Przetworzenie

programu

źródłowego

w kod

maszynowy

42

Programowanie komputerów