Wykład II Reprezentacja informacji w komputerze

Abstrakcyjny model

Maszynę  cyfrową  wynaleziono  w  celu  ułatwienia  i
przyspieszenia obliczeń.
W  większości  je  obecnych  zastosowań  większe
znaczenie ma możliwość przechowywania i dostępu
do  dużych  partii  informacji,  natomiast  sama
pierwotnie uzyskana zdolność wykonywania obliczeń
wydaje się nieistotna.
We  wszystkich  tych  przypadkach  duże  partie
informacji,

które

mają

być

przetwarzane,

reprezentują – w pewnym sensie – abstrakcyjny
model części świata rzeczywistego.

Model - uproszczenie

zbioru faktów

Informacja dostępna komputerowi stanowi pewien

wybrany zbiór danych o świecie rzeczywistym,

mianowicie zbiór danych uznanych za istotne dla

rozważanego problemu, tj. taki, co do którego ma

się przekonanie, że za jego pomocą można uzyskać

pożądane wyniki.
Dane te reprezentują model abstrakcyjny w tym

sensie,

że

pewne

właściwości

obiektów

rzeczywistych są ignorowane, ponieważ nie są

związane z badanym problemem.
Stosowany

model

jest

zatem

pewnym

uproszczeniem zbioru faktów.

Przykład - kartoteka

pracowników

Każdy

pracownik

jest

(abstrakcyjnie)

reprezentowany w kartotece przez zbiór danych
potrzebnych  bądź  to  pracodawcy,  bądź  do
prowadzenia jego rozliczeń podatkowych.
Zbiór  ten  może  zawierać  pewne  informacje
identyfikujące zatrudnionego np.. jego nazwisko
i imię czy też wysokość uposażenia.
Jednakże  nie  będzie  on  zwykle  zawierał
nieistotnych  tu  informacji  takich  jak  kolor
włosów, wzrost, czy waga.

Wybór modelu

abstrakcyjnego

Przy

rozwiązywaniu

rzeczywistych

problemów  (przy  pomocy  komputera,  bądź
bez  niego)  trzeba  dokonywać  wyboru
abstrakcyjnego  modelu  rzeczywistości,
czyli  zdefiniować  zbiór  danych  mających
reprezentować rzeczywistą sytuację.
Wybór  ten  powinien  być  podporządkowany
problemowi, który ma być rozwiązany.

Wybór reprezentacji

informacji

Potem  (po  wyborze  modelu  abstrakcyjnego)
następuje wybór reprezentacji tych informacji.
Ten wybór jest z kolei podyktowany narzędziem,
które  służy  do  rozwiązania  problemu,  czyli
możliwościami komputera.
Trzeba  również  brać  pod  uwagę  operacje,  które
mają być wykonywane na danych. (np. z punktu
widzenia  dodawania  małych  licz  mogła  by  być
wygodna  inna  reprezentacja  niż  w  wypadku
mnożenia czy dodawania dużych liczb).

Przykład – decyzje

podejmowane dla wyboru

sposobu reprezentowania

pozycji obiektu

Pierwsza decyzja może dotyczyć wyboru jako reprezentacji

pary liczb stanowiących współrzędne kartezjańskie, bądź

biegunowe.
Druga decyzja może prowadzić do reprezentacji

zmiennopozycyjnej, gdzie każda liczba rzeczywista x

(współrzędna) składa się z pary liczb całkowitych

oznaczających ułamek f i wykładnik e przy pewnej

podstawie (np. x=f·2

Kolejna decyzja – wynikająca ze świadomości, że dane

trzeba przechowywać w pamięci maszyny cyfrowej – może

prowadzić do dwójkowej, pozycyjnej reprezentacji liczb.
Ostatnią decyzją może być sposób realizacji reprezentacji

(np. zapis za pomocą strumienia magnetycznego).

Nie musimy sami

podejmować wszystkich

decyzji

Pierwsza z decyzji zależy od problemu, natomiast

następne zależą coraz bardziej od stosowanego

narzędzia i jego technologii.
Nie można żądać od programisty (na szczęście) by

podejmował decyzje o sposobie reprezentowania liczb

czy

wręcz

charakterystyce

urządzenia

przechowującego informacje.
Takie decyzje na „niskim szczeblu” zostawia się

projektantom komputerów, którzy mają najwięcej

potrzebnych

informacji

temat

stosowanych

technologii i mogą podjąć najbardziej sensowne decyzje

odpowiednie dla wszystkich (bądź prawie wszystkich)

zastosowań, w których odgrywa rolę pojęcie liczby.

Język programowania –

maszyna abstrakcyjna

Na tym tle widać wyraźnie znaczenie języków

programowania. Język programowania reprezentuje

bowiem pewną abstrakcyjną maszynę, która rozumie

występujące w nim terminy, stanowiące pewien

wyższy poziom abstrakcji w stosunku do obiektów

używanych przez rzeczywisty komputer.
Programista używając takiego języka „wyższego

poziomu” jest więc uwolniony od problemów

reprezentacji liczb (choć w pewnym sensie zostaje też

stosowaną

reprezentacją

skrępowany),

jeśli

oczywiście liczba należy do elementarnych obiektów

danego języka.

Pod spodem jednak masa

bitów,

ale nas to zwykle nie

interesuje

Znaczenie używania języka oferującego odpowiedni zbiór

podstawowych

pojęć

abstrakcyjnych

wspólnych

dla

większości problemów przetwarzania danych polega głównie

na niezawodności programów wynikowych.
Łatwiej napisać program przy użyciu znanych pojęć liczb,

zbiorów, ciągów, czy powtórzeń (iteracji) zamiast bitów,

słów czy skoków.
Oczywiście komputer będzie reprezentował wszystkie dane

– zarówno liczby, zbiory, jak i ciągi – jako wielką masę bitów.

Fakt ten jest jednak dotąd nieistotny dla programisty, jak

długo nie musi się on interesować problemem reprezentacji

wybranych przez siebie pojęć i dopóki może być pewien, że

odpowiednie reprezentacje w komputerze (czy translatorze)

są wystarczając do jego celów.

Abstrakcyjne pojęcia

winny być jednak „bliskie”

komputerowi

Dokonanie przez inżyniera (czy twórcę translatora)
odpowiedniego wyboru jest tym łatwiejsze, im
bliższe

danemu

komputerowi

są

pojęcia

abstrakcyjne.
Zwiększa

się

wówczas

również

prawdopodobieństwo, że pojedynczy wybór będzie
odpowiedni dla prawie wszystkich zastosowań.
Fakty te ograniczają w pewien sposób możliwe
oddalenie poziomu abstrakcji używanych pojęć od
danego komputera.

Wszystkie dane mają

swoje typy

W matematyce zmienne klasyfikuje się zgodnie z ich pewnymi

istotnymi właściwościami.
Rozróżnia się zmienne rzeczywiste, zespolone i logiczne lub

też zmienne reprezentujące pojedyncze wartości, zbiory

wartości, zbiory zbiorów, a także funkcje, funkcjonały, zbiory

funkcji, itd.
W przetwarzaniu danych klasyfikacja zmiennych jest pojęciem

równie ważnym (jeśli nie ważniejszym).
Każda stała, zmienna, wyrażenie, czy funkcja jest

pewnego typu.
Typ ten dokładnie charakteryzuje zbiór wartości, do którego

może należeć stała, bądź jakie może przyjmować zmienna czy

wyrażenie, bądź jakie mogą być generowane przez funkcję.

Deklaracja typu

W tekstach matematycznych można zazwyczaj określić

typ zmiennej na podstawie kroju czcionki, jaką ją

oznaczamy.
W programach komputerowych nie jest to możliwe

ponieważ stosujemy jeden ogólnie dostępny krój

czcionek.
Szeroko przyjęto zatem stosowanie zasady, że typ danej

podaj się explicite w deklaracji stałej, zmiennej czy

funkcji oraz że deklaracja ta poprzedza w tekście

programu użycie owej stałej, zmiennej czy funkcji.
Zasada ta jest szczególnie istotna, jeśli się zwróci uwagę

na fakt, że kompilator musi dokonać wyboru

reprezentacji obiektów wewnątrz pamięci maszyny.

Od zakresu wartości

zależy wielkość

potrzebnego obszaru

pamięci

Oczywiście  wielkość  obszaru  pamięci
przydzielonego  zmiennej  należy  wybrać
odpowiednio do zakresu wartości, które ta
zmienna może przyjmować.
Jeśli  informacje  o  zakresie  wartości  są
znane kompilatorowi można uniknąć, tzw.
dynamicznej  alokacji  pamięci,  co  jest
kluczem

efektywnej

realizacji

algorytmu.

Cechy charakterystyczne

pojęcia typu

Typ danych określa zbiór wartości, do którego należy stała

bądź które może przyjmować zmienna lub wyrażenie albo

które mogą być generowane przez operator lub funkcję.
Typ wartości oznaczonej przez stałą, zmienną lub wyrażenie

można określić na podstawie ich postaci bądź deklaracji ,

bez konieczności wykonywania procesu obliczeniowego.
Każdy operator lub funkcja ma argumenty ustalonego typu,

jak również daje wynik ustalonego typu. Jeśli operator

dopuszcza argumenty wielu typów (np. „+” oznacza

dodawanie zarówno liczb całkowitych jak i rzeczywistych), to

typ uzyskiwanego wyniku jest określany za pomocą

specyficznych dla danego języka reguł.

Typy nadają monotonnym

bitom interpretację

W konsekwencji kompilator może korzystać z informacji o

typach w celu sprawdzenia poprawności wielu konstrukcji.
Na przykład przypisanie wartości logicznej (prawda-fałsz) do

zmiennej arytmetycznej (liczba) może zostać wykryte bez

potrzeby wykonywania programu, na etapie jego kompilacji.
Ten rodzaj redundancji w tekście programu jest niezwykle

pomocny przy tworzeniu programów i należy go uznać za

podstawową zaletę dobrych języków programowania wysokiego

poziomu (w stosunku do kodu maszynowego czy też kodu

adresów symbolicznych).
Ostatecznie dane w pamięci będą stanowiły jednolitą masę

bitów bez jakiejkolwiek struktury. Jednakże to właśnie ta

struktura abstrakcyjna umożliwia programistom rozpoznawać

znaczenie danych w monotonnym krajobrazie pamięci maszyny.

Wartości i typy składowe,

typ podstawowy

Nowe typy w większości języków programowania
definiuje

się

pomocą

typów

danych

zdefiniowanych wcześniej.
Wartości

takiego

nowego

typu

są

zwykle

konglomeratami

wartości

składowych

(component values) o pierwotnie zdefiniowanych
typach składowych (constituent types) i mówi się,
że są one ustrukturowane.
Jeśli występuje tylko jeden typ składowy, tzn.
wszystkie składowe są tego samego typu to ów typ
nazywa się typem podstawowym (base type).

Moc typu

Liczbę  różnych  wartości  należących
do  typu  T  nazywa  się  mocą
(cardinality) T.
Moc  typu  pozwala  określić  wielkość
pamięci

potrzebnej

reprezentowania zmiennej x typu T.

Typy wyliczeniowe

Ponieważ typy składowe również mogą być

ustrukturyzowane itd. tworzy się więc w rezultacie

całe hierarchie struktur; niemniej oczywiście

elementarne składowe muszą być atomowe.
Potrzebna jest więc pewna notacja służąca do

określenia

takich

typów

prostych

nieustrukturyzowanych.

Narzuca

się

metoda

polegająca na wyliczeniu wartości tworzących typ.
Np. w programie dotyczącym figur geometrycznych

można określić typ prosty o nazwie kształt, którego

wartości mogą być oznaczone identyfikatorami

prostokąt, kwadrat, elipsa, okrąg.

Typy standardowe

Oprócz takich typów definiowanych
przez programistę muszą istnieć
pewne typy standardowe (standard
types),

które

są

zdefiniowane

wcześniej

(przez

producenta

kompilatora).
Na ogół typy standardowe zawierają
liczby i wartości logiczne.

Typy uporządkowane i

skalarne

Jeśli wartości typu są uporządkowane,
to

typ

będziemy

nazywali

uporządkowanym

(porządkowym,

ordered) lub skalarnym (scalar).
W przypadku typu wyliczeniowego
przyjmuje

się,

że

wartości

są

uporządkowane zgodnie z kolejnością
ich wyliczenia.

Strukturalizacja typów

Przyjmując powyższe zasady, możemy definiować typy

proste, następnie zaś budować konglomeraty – typy

złożone, o dowolnym stopniu zagnieżdżenia.
W rzeczywistości nie wystarczy dysponować tylko jedną

ogólną metodą tworzenia typów złożonych. W związku z

różnymi praktycznymi problemami reprezentacji i

zastosowań

język

programowania

ogólnego

przeznaczenia

powinien

oferować

wiele

metod

strukturalizacji typów danych.
W sensie matematycznym wszystkie te metody mogą

być równoważne; różnice polegają na wyborze

operatorów stosowanych do konstruowania wartości i

wybierania składowych tych wartości.

Podstawowe statyczne

struktury danych

Podstawowymi strukturami danych
złożonych są:
tablica,
rekord,
zbiór,
i ciąg (plik).

Struktury dynamiczne

Bardziej wyrafinowane struktury nie są zwykle

definiowane jako typy „statyczne”, lecz są

„dynamiczne” generowane podczas wykonania

programu i mogą w tym procesie zmieniać swój

kształt i rozmiary.
Będziemy na dalszych wykładach omawiać te

struktury. Są to

– listy,
– pierścienie,
– drzewa,
– i ogólne grafy skończone.

Operatory i ich składanie

Zmienne i ich typy wprowadza się do programu w celu

użycia ich w obliczeniach. W związku z tym musi istnieć

pewien podzbiór operatorów.
Dla

standardowych

typów

danych

językach

programowania proponuje się pewną liczbę prostych,

standardowych (atomowych) operacji wraz z pewną liczbą

metod ich składania (tworzenia operacji złożonych) za

pomocą proponowanych operatorów prostych.
Problem składania operacji uważa się często za esencję

sztuki programowania. Jednakże w trakcie wykładów

okaże się, że właściwe, trafne składanie danych jest

problemem równie podstawowym, jak i ważnym.

Operatory proste

Porównanie i przypisanie

Najważniejszymi

operatorami

prostymi

są

porównanie i przypisanie, tzn. test na równość (i

uporządkowanie w wypadku typów skalarnych)

oraz instrukcja narzucająca równość.
Istnieje fundamentalna różnica między tymi

operatorami stąd większość języków programowania

stosuje dwa różne oznaczenia.
Te dwie podstawowe operacje definiuje się dla

większości typów danych, ale należy zaznaczyć, że

ich wykonanie może się wiązać, ze znaczną stratą

czasu wykonania, jeśli dane są duże i/lub mają

złożoną strukturę.

Konwersje typów

Oprócz testu na równość (czy na uporządkowanie) i

przypisania wprowadza się klasę fundamentalnych operacji

zwanych operacjami konwersji typów.
Są one odwzorowaniami typów danych na inne typy (są

szczególnie istotne w przypadku typów złożonych).
Wartości

złożone

generuje

się

pomocą

tzw.

konstruktorów, a wartości składowe wybiera się za pomocą

tzw. selektorów.
Konstruktory i selektory stanowią więc operacje konwersji

typów będące funkcjami typów składowych na typy złożone i

vice versa.
Każda metoda strukturalizacji będzie się wiązała z określoną

parą złożoną z konstruktora i selektora, o wyraźnie odrębnych

oznaczeniach.

Typy wyliczeniowe

(enumerated)

W wielu programach stosuje się liczby

całkowite

wtedy,

gdy

właściwości

numeryczne nie są potrzebne, a liczba

całkowita reprezentuje wybór spośród pewnej

małej liczby wartości.
W tych wypadkach dobrze jest wprowadzić

nowy prosty typ danych T, wyliczając zbiór

wszystkich możliwych wartości c

, c

, ..., c

T=(c

, c

, ..., c

)

Mocą typu T jest wartość funkcji moc(T)=n .

Przykłady typów

wyliczeniowych

kształt=(prostokąt, kwadrat, elipsa, okrąg)
kolor=(czerwony, żółty zielony)
płeć=(mężczyzna, kobieta)
Boolean=(false, true)
dzieńtygodnia=(poniedziałek, wtorek, środa, czwartek, piątek,

sobota, niedziela)
waluta=(euro, funt, dolar, korona, rubel, jen)
przeznaczenie=(piekło, czyściec, niebo)
środeklokomocji=(pociąg, autobus, samochód, statek, samolot)
ranga=(szeregowiec,

kapral,

sierżant,

porucznik,

major,

pułkownik, generał)
obiekt=(stała, typ, zmienna, procedura, funkcja)
struktura=(plik, tablica, rekord, zbiór)

Typy wyliczeniowe

są bardziej obrazowe

Definicja typu wyliczeniowego wprowadza nie tylko nowy

identyfikator typu, ale jednocześnie zbiór identyfikatorów

oznaczających poszczególne wartości definiowanego typu.
Identyfikatorów tych można używać w programie jako

stałych, a ich wystąpienia czynią program bardziej

zrozumiałym.
Wprowadźmy na przykład zmienne r: ranga czy p: płeć.
Możliwe

wówczas

są

przypisania

p:=mężczyzna;

r:=major.
Są one bardziej obrazowe niż ich numeryczne odpowiedniki

p:=0; r:=4 oparte na założeniu, że do oznaczeń używamy

liczb naturalnych według kolejności ich wyliczania.

Uporządkowanie w typach

wyliczeniowych

Ponadto translator może dzięki temu

wykrywać „nierozważne” stosowanie

operatorów do typów nienumerycznych

np. p:=p+1;
Wprowadza się jednak operatory funkcji

generujących

następnik

bądź

poprzednik argumentu.
Uporządkowanie

wartości

typu

określa następująca reguła (c

)



(i<j)

Standardowe typy proste

Standardowe typy proste są to takie

typy, które na większości maszyn

cyfrowych występują jako „możliwości

wbudowane”.
Należą do nich

– zbiór liczb całkowitych,
– zbiór wartości logicznych,
– zbiór znaków alfanumerycznych,
– zbiór liczb rzeczywistych.

Typ całkowity

Typ Integer stanowi podzbiór wszystkich liczb

całkowitych, którego zakres zależy od możliwości

danej maszyny.
Jednakże zakłada się, że wszystkie operacje na

danych tego typu są dokładne i odpowiadają

podstawowym

prawom

arytmetyki

oraz,

że

wykonanie programu zostanie przerwane jeśli wynik

znajdzie się poza reprezentowanym podzbiorem.
Standardowe operatory dostarczają tu czterech

podstawowych

operacji:

dodawania

(+),

odejmowania (-), mnożenia (*) i dzielenia (div)

Typ rzeczywisty

Oznacza pewien podzbiór liczb rzeczywistych. Podczas

gdy zakłada się, że arytmetyka liczb całkowitych daje

wyniki dokładne, to dla arytmetyki liczb rzeczywistych

dopuszcza się wyniki niedokładne w ramach pewnych

błędów zaokrąglenia spowodowanych wykonywaniem

obliczeń na skończonej licznie cyfr.
Jest to zasadniczy powód dla którego w większości

języków programowania wyraźnie odróżnia się typy

całkowite i rzeczywiste.
Oferowany zestaw działań jest tożsamy z zestawem

zdefiniowanym dla liczb całkowitych, z tym że dzielenie

oznacza się symbolem / oznaczającym dzielenie
zwracające wartość rzeczywistą

Typ logiczny

Dwie  wartości  standardowego  typu  logicznego  są
najczęściej  oznaczane  identyfikatorami  false  i
true.
Do  operatorów  logicznych  zaliczamy  koniunkcję
(,  and,  iloczyn  logiczny),  alternatywę  (,  or,

sumę logiczną) i negację (~, not).

pq

pq

true

false

true

false

true

false

true

false

true

false

true

Porównania dają wyniki typu

logicznego

Zauważmy,

że

zastosowanie

operatora

porównania daje wynik typu logicznego.
W związku z tym wynik porównania może być
przypisany do zmiennej logicznej  bądź użyty
jako argument operatora logicznego.
Np.  dla  zmiennych  p  i  q  typu  logicznego  i
zmiennych całkowitych x=5, y=8, z=10 dwie
instrukcje  przypisania:  p:=x=y  i  p:=(x<y)  

(yz) dają w rezultacie p=false i q=true.

Typ znakowy

Obejmuje zbiór znaków alfanumerycznych.
Niestety jak mówiliśmy na poprzednim wykładzie

nie istnieje ogólnie przyjęty standardowy zbiór

znaków stosowany we wszystkich systemach

komputerowych.
Typ znakowy najczęściej reprezentuje obecnie dane

z kodu ASCII (bądź jednego z jego narodowych

wariantów). Nie należy jednak tego uznawać za

niezmiennik i sposób kodowania zależy od

konkretnego komputera i zainstalowanego na nim

systemu operacyjnego, a nawet od stosowanego

oprogramowania.

Założenia dotyczące

zbioru znaków

Aby konstruować niezależne od komputera algorytmy, w

których korzysta się ze znaków musimy przyjąć pewne

założenia dotyczące typu znakowego:
Zawiera znaki łacińskie, cyfry arabskie i pewną liczbę innych

znaków graficznych, jak np. znaki przystankowe.
Podzbiory liter i cyfr są uporządkowane i spójne, tzn.

– (‘A’x)  (x‘Z’)x jest literą
– (‘0’x)  (x‘9’)x jest cyfrą

Zawiera znak pusty (spację), którego można używać jako

separatora.
W większości języków wprowadza się wzajemnie odwrotne

funkcje pozwalające dokonywać konwersji typu znakowego

na całkowity i odwrotnie.

Typy okrojone

Często się zdarza, że zmienna przyjmuje

wartości jedynie z pewnego przedziału wartości

określonego typu.
Wyraża się to definiując typ okrojony, zgodnie

z formatem T=min..max, gdzie min i max

stanowią granice przedziału.
Przykłady

– rok=1900..2099
– litera=‘A’..’Z’
– cyfra=‘0’..’9’
– oficer=porucznik..generał

(nie) Dozwolone użycie

typu okrojonego

Dla zmiennych y: rok i L: Litera
– dozwolone są przypisania y:=1973 i

L:=‘W’

– natomiast niedozwolone y:=1291 i

L:=‘9’.

Dopuszczalność  przypisań  y:=i  czy  L:=c,
gdzie  i  jest  liczbą  całkowitą,  a  c  wartością
znakową  można  sprawdzić  dopiero  podczas
wykonania programu.

Document Outline