Data: Representing Information

Diomidis Spinellis
Department of Management Science and Technology
Athens University of Economics and Business
Athens, Greece
dds@aueb.gr

Φυσικός κόσμος και πληροφορική

Φυσικός κόσμος

  1. Αντικείμενα
  2. Ενέργειες

Πληροφορική

  1. Δεδομένα (data)
  2. Αλγόριθμοι (algorithms)

Χάρτης καιρού


Εύρεση του κυρτού φλοιού

Αλφάβητα και κωδικοποίηση

Ορολογία

Bit (b)
0 ή 1
Byte (B)
8 bit - 28 = 256 τιμές
Word
φυσική ομάδα από bit(π.χ. 16, 32, 36, 48, 64). Στους υπολογιστές που χρησιμοποιούμε 32.
KiB/KB
Kibi/Kilo - 1024 (210)
MiB/MB
Mebi/Mega - 1.028.576 (220)
GiB/GB
Gibi/Giga - 1.073.741.824 (230)
TiB/TB
Tebi/Tera - 1.099.511.627.776 (240)
PiB/PB
Peti/Peta - 1.125.899.906.842.624 (250)

Μνημονικός κανόνας

210 είναι περίπου ίσο με 103
2N * 10 είναι περίπου ίσο με 10N * 3

Παραδείγματα κωδικοποίησης

Παράσταση χαρακτήρων

Παράσταση των χαρακτήρων "HELLO, WORLD! ABCDEFGHIJKLM 0123456789" σε διάτρητη κάρτα.

 ________________________________________________
/HELLO, WORLD! ABCDEFGHIJKLM 0123456789          |
|]]         ]  ]]]]]]]]]                         |
|  ]]]   ]]]            ]]]]                     |
|     ] ]    ]               ]                   |
|11111111111111]11111111]11111]111111111111111111|
|222222222222222]22222222]22222]22222222222222222|
|33]]3]3333]33333]33333333]33333]3333333333333333|
|44444444444]44444]44444444]44444]444444444444444|
|5]5555555555555555]55555555555555]55555555555555|
|6666]66]]6666666666]66666666666666]6666666666666|
|777777777777]7777777]77777777777777]777777777777|
|]8888]888888]88888888]88888888888888]88888888888|
|999999999]999999999999]99999999999999]9999999999|
|________________________________________________|

Παράσταση των χαρακτήρων "HELLO, WORLD! ABCDEFGHIJKLM 0123456789" σε διάτρητη ταινία.

___________
| o  o.   |
| o   .o o|
| o  o.o  |
| o  o.o  |
| o  o.ooo|
|  o o.o  |
|  o  .   |
| o o .ooo|
| o  o.ooo|
| o o . o |
| o  o.o  |
| o   .o  |
|  o  .  o|
|  o  .   |
| o   .  o|
| o   . o |
| o   . oo|
| o   .o  |
| o   .o o|
| o   .oo |
| o   .ooo|
| o  o.   |
| o  o.  o|
| o  o. o |
| o  o. oo|
| o  o.o  |
| o  o.o o|
|  o  .   |
|  oo .   |
|  oo .  o|
|  oo . o |
|  oo . oo|
|  oo .o  |
|  oo .o o|
|  oo .oo |
|  oo .ooo|
|  ooo.   |
|  ooo.  o|
___________

Εμφάνιση χαρακτήρων

Simple rendering
Simple rendering

Anti-aliased rendering
Anti-aliased rendering

ClearType rendering
ClearType rendering

Παράσταση ιστοσελίδων με HTML

H HTML είναι μια εφαρμογή της SGML για την περιγραφή σελίδων στο Web. Περιοχές του κειμένου σημειώνονται με ετικέτες (tags). Κάθε ετικέτα περιλαμβάνει το όνομά της και παραμέτρους. Οι ετικέτες γράφονται ως εξής:
<όνομα ετικέτας παράμετροι>
Μια περιοχή του κειμένου μπορεί να σημειωθεί ως εξής:
<ετικέτα>
περιοχή που σημειώνεται
</ετικέτα>
Βασικές ετικέτες που υποστηρίζει η HTML είναι οι παρακάτω:
html
περιγραφή ολόκληρης σελίδας
head
επικεφαλίδα της σελίδας
body
κείμενο της σελίδας
h1-h6
επικεφαλίδες του κειμένου
p
Παράγραφος
ul
λίστα με τελείες
ol
αριθμημένη λίστας
li
στοιχείο λίστας
br
αλλαγή γραμμής
hr
οριζόντια γραμμή
img
εικόνα
a
(anchor) σημείο πρόσβασης από ή σε υπερκείμενο
pre
προστοιχειοθετημένο κείμενο
dl, dt, dd
λίστα περιγραφών, περιγραφές
i
πλάγιοι χαρακτήρες
b
έντονοι χαρακτήρες
table, tr, th/td
Πίνακας, γραμμή, επικεφαλίδα / δεδομένα
<!-- κείμενο -->
σχόλιο
Παράδειγμα σελίδας:
<!doctype html public "-//IETF//DTD HTML//EN">
<html>
<head>
<title>Τίτλος της σελίδας</title>

<meta NAME="GENERATOR" CONTENT="thread.pl">
<meta NAME="AUTHOR" CONTENT="Diomidis Spinellis">
<meta HTTP-EQUIV="Content-type" CONTENT="text/html; charset=ISO-8859-7">
<link REV="made" HREF="mailto:dds@aueb.gr"> 
<link REL="ToC" HREF=".././web/index.htm">
<link REV="Subdocument" HREF=".././web/index.htm">
<link REL="previous" HREF=".././web/http.htm">
<link REL="next" HREF=".././web/cgi.htm">

</head>

<body>
<h1>Επικεφαλίδα πρώτου επιπέδου</h1><hr />
<p>
Κείμενο που περιέχει ένα σημείο κατάληξης υπερκειμένου
<a name="G42"> (<em>με έντονο κείμενο</em>)</a> 
και μια λίστα:
<ul>
<li> στοιχείο 1 </li>
<li> στοιχείο 2 </li>
</ul>
</p>

<p>
Νέα παράγραφος με ένωση υπερκειμένου στο
<a href="http://www.aueb.gr">Οικονομικό Πανεπιστήμιο</a>
</p>

<hr />
</body>
</html>
Αυτή θα εμφανιστεί ως εξής:

Επικεφαλίδα πρώτου επιπέδου


Κείμενο που περιέχει ένα σημείο κατάληξης υπερκειμένου (με έντονο κείμενο) και μια λίστα:

Νέα παράγραφος με ένωση υπερκειμένου στο Οικονομικό Πανεπιστήμιο (http://www.aueb.gr)


Ιστορία αριθμητικών συστημάτων

Συστήματα παράστασης

Το δυαδικό σύστημα

Ακέραιοι αριθμοί

Μετατροπές

Πρόσθεση και πολλαπλασιασμός

Πρόσθεση

Ψηφίο 1Ψηφίο 2'AθροισμαΚρατούμενο
0000
0110
1010
1101

Παράδειγμα:

  1110
+10111
------
100101
Δηλαδή 11102 + 101112 = 1001012 ή 1410 + 2310 = 3710

Πολλαπλασιασμός

Παράδειγμα:
  1011
X   11
------
  1011
+1011
------
100001
Δηλαδή 10112 + 112 = 1000012 ή 1110 + 310 = 3310

Αρνητικοί αριθμοί και αφαίρεση

Αφαίρεση με το μέθοδο του συμπληρώματος

Παράδειγμα 1
X      = 4 - 3        <=>
X + 10 = 4 + (10 - 3) <=>
X + 10 = 4 + 7        <=>
X      = 4 + 7 - 10   <=>
X      = 11 - 10      <=>
X      = 1
Παράδειγμα 2
X       = 45 - 23         <=>
X + 100 = 45 + (100 - 23) <=>
X + 100 = 45 + 77         <=>
X       = 45 + 77 - 100   <=>
X       = 122 - 100       <=>
X       = 22
Η εύρεση του συμπληρώματος (complement) ως προς ένα ΒN (π.χ. 10 - 3 ή 100 - 23) και η απαλειφή του όρου ΒN στο τέλος είναι πράξεις εύκολες. Αν θεωρήσουμε πως όλοι οι αριθμοί μας είναι μικρότεροι από ΒN/2 και στο τέλος κάθε πράξης απαλείφουμε τον όποιο όρο ΒN τότε μπορούμε να παριστάνουμε τους αρνητικούς αριθμούς ως θετικούς με βάση το συμπλήρωμά τους από το ΒN (π.χ. το -3 ως 7 για ΒN = 101 ή το -23 ως 77 για ΒN = 102) και να κάνουμε πρόσθεση αντί για αφαίρεση.

Εύρεση του συμπληρώματος στο δυαδικό σύστημα

Παράδειγμα για τον αριθμό 01002 και ΒN = 24 (100002):
10000
-0100
-----
 1100
Στο δυαδικό σύστημα το αποτέλεσμα της αφαίρεσης του αριθμού Α από το ΒN (δηλαδή η παράσταση του -Α με το μέθοδο του συμπληρώματος) μπορεί να υπολογιστεί εύκολα με δύο ισοδύναμους τρόπους:
  1. Αντιστρέφουμε τα 0 σε 1 και 1 σε 0 και προσθέτουμε 1:
    0100 -> 1011
    1011 + 1 = 1100
    
  2. Αντιγράφουμε από δεξιά προς τα αριστερά όλα τα 0 και το πρώτο 1 και αντιστρέφουμε τα υπόλοιπα 0 σε 1 και 1 σε 0:
    0 -> 0 (αντιγραφή)
    0 -> 0 (αντιγραφή)
    1 -> 1 (αντιγραφή)
    0 -> 1 (αντιστροφή)
    

Παράδειγμα παράστασης

Για ΒN = 24 οι αριθμοί που μπορούν να παρασταθούν είναι οι -8...7:
 0 0000
 1 0001
 2 0010
 3 0011
 4 0100
 5 0101
 6 0110
 7 0111
-8 1000
-7 1001
-6 1010
-5 1011
-4 1100
-3 1101
-2 1110
-1 1111
Παρατηρούμε πως οι θετικοί αριθμοί έχουν ως πρώτο ψηφίο 0 και οι αρνητικοί αριθμοί έχουν ως πρώτο ψηφίο 1.

Παράδειγμα αφαίρεσης

Το αποτέλεσμα του 510 - 210 θα βρεθεί ως 0101 + 1110:
 0101
+1110
-----
10011
Με την απαλειφή του όρου 100002 το αποτέλεσμα είναι 112 δηλαδή 310.

Αριθμοί κινητής υποδιαστολής

Το πρότυπο IEEE-488

Ο τρόπος παράστασης του αριθμού κινητής υποδιαστολής μπορεί να διαφέρει σε πολλά σημεία από υπολογιστή σε υπολογιστή (μήκος σημαινόμενου και εκθέτη, παράσταση αρνητικού σημαινόμενου και εκθέτη, κανονικοποίηση του σημαινόμενου). Σήμερα οι περισσότεροι υπολογιστές παριστάνουν τους αριθμούς κινητής υποδιαστολής σύμφωνα με το πρότυπο IEEE-488. Για αριθμούς διπλής ακρίβειας π.χ. Έτσι ο αριθμός καταλαμβάνει συνολικά 64 bit:
Π ΕΕΕΕΕΕΕΕΕΕΕ ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
Για παράδειγμα το π στο δυαδικό σύστημα εφράζεται ως:
11.0010 0100 0011 1111 0110 1010 1000 1000 1000 0101 1010 0011 0000 10.... και στο πρότυπο ΙΕΕΕ-488 με εκθέτη 1 (που παριστάνεται ως 1024) ως:
Π ΕΕΕΕΕΕΕΕΕΕΕ ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
0 10000000000 1001001000011111101101010100010001000010110100011000

Προγράμματα

Συμπίεση δεδομένων χωρίς απώλειες

Για τη συμπίεση δεδομένων (data compression) χωρίς απώλειες (lossless) χρησιμοποιούνται οι παρακάτω τρόποι: Εφαρμογές:

Συμπίεση δεδομένων με απώλειες

Εφαρμογές:

Ανίχνευση και διόρθωση λαθών

Έλεγχος λαθών

Διόρθωση λαθών

Απόσταση Hamming είναι ο αριθμός των bit κατά τον οποίο διαφέρουν δύο λέξεις.
Α	000000
Β	001111
Γ	010011
Δ	011100
Ε	100110
Ζ	101001
Θ	110101
Ι	111010
Αν η απόσταση είναι N μπορούμε να διαπιστώσουμε λάθη N-1 bit και να διορθώσουμε λάθη N-2 bit.

Βιβλιογραφία

Παράρτημα: ο πίνακας ASCII

Ο παρακάτω πίνακας εμφανίζει τους χαρακτήρες του πίνακα ASCII που μπορούν να εμφανιστούν στην οθόνη μαζί με την τιμή τους σε δεκαεξαδικό σύστημα και την αντίστοιχη περιγραφή.
        20    Space
 !      21    Exclamation mark
 "      22    Quotation mark
 #      23    Number sign
 $      24    Dollar sign
 %      25    Percent sign
 &      26    Ampersand
 '      27    Apostrophe
 (      28    Left parenthesis
 )      29    Right parenthesis
 *      2a    Asterisk
 +      2b    Plus sign
 ,      2c    Comma
 -      2d    Hyphen-minus
 .      2e    Full stop
 /      2f    Solidus
 0      30    Digit zero
 1      31    Digit one
 2      32    Digit two
 3      33    Digit three
 4      34    Digit four
 5      35    Digit five
 6      36    Digit six
 7      37    Digit seven
 8      38    Digit eight
 9      39    Digit nine
 :      3a    Colon
 ;      3b    Semicolon
 <      3c    Less-than sign
 =      3d    Equals sign
 >      3e    Greater-than sign
 ?      3f    Question mark
 @      40    Commercial at (papaki)
 A      41    Latin capital letter a
 B      42    Latin capital letter b
 C      43    Latin capital letter c
 D      44    Latin capital letter d
 E      45    Latin capital letter e
 F      46    Latin capital letter f
 G      47    Latin capital letter g
 H      48    Latin capital letter h
 I      49    Latin capital letter i
 J      4a    Latin capital letter j
 K      4b    Latin capital letter k
 L      4c    Latin capital letter l
 M      4d    Latin capital letter m
 N      4e    Latin capital letter n
 O      4f    Latin capital letter o
 P      50    Latin capital letter p
 Q      51    Latin capital letter q
 R      52    Latin capital letter r
 S      53    Latin capital letter s
 T      54    Latin capital letter t
 U      55    Latin capital letter u
 V      56    Latin capital letter v
 W      57    Latin capital letter w
 X      58    Latin capital letter x
 Y      59    Latin capital letter y
 Z      5a    Latin capital letter z
 [      5b    Left square bracket
 \      5c    Reverse solidus
 ]      5d    Right square bracket
 '      5e    Circumflex accent
 _      5f    Low line
 `      60    Grave accent
 a      61    Latin small letter a
 b      62    Latin small letter b
 c      63    Latin small letter c
 d      64    Latin small letter d
 e      65    Latin small letter e
 f      66    Latin small letter f
 g      67    Latin small letter g
 h      68    Latin small letter h
 i      69    Latin small letter i
 j      6a    Latin small letter j
 k      6b    Latin small letter k
 l      6c    Latin small letter l
 m      6d    Latin small letter m
 n      6e    Latin small letter n
 o      6f    Latin small letter o
 p      70    Latin small letter p
 q      71    Latin small letter q
 r      72    Latin small letter r
 s      73    Latin small letter s
 t      74    Latin small letter t
 u      75    Latin small letter u
 v      76    Latin small letter v
 w      77    Latin small letter w
 x      78    Latin small letter x
 y      79    Latin small letter y
 z      7a    Latin small letter z
 {      7b    Left curly bracket
 |      7c    Vertical line
 }      7d    Right curly bracket
 ~      7e    Tilde

Παράρτημα: οι νεοελληνικοί χαρακτήρες στο πρότυπο Unicode

Ο παρακάτω πίνακας εμφανίζει τους νεοελληνικούς χαρακτήρες στο πρότυπο κωδικοποίησης Unicode μαζί με την τιμή τους σε δεκαεξαδικό σύστημα και την αντίστοιχη περιγραφή.
'Α  0386 Capital alpha with acute
 Έ  0388 Capital epsilon with acute
 Ή  0389 Capital eta with acute
 Ί  038a Capital iota with acute
 Ό  038c Capital omicron with acute
 Ύ  038e Capital upsilon with acute
 Ώ  038f Capital omega with acute
 ΐ  0390 Small iota with acute and diaeresis
 Α  0391 Capital alpha
 Β  0392 Capital beta
 Γ  0393 Capital gamma
 Δ  0394 Capital delta
 Ε  0395 Capital epsilon
 Ζ  0396 Capital zeta
 Η  0397 Capital eta
 Θ  0398 Capital theta
 Ι  0399 Capital iota
 Κ  039a Capital kappa
 Λ  039b Capital lamda
 Μ  039c Capital mu
 Ν  039d Capital nu
 Ξ  039e Capital xi
 Ο  039f Capital omicron
 Π  03a0 Capital pi
 Ρ  03a1 Capital rho
 Σ  03a3 Capital sigma
 Τ  03a4 Capital tau
 Υ  03a5 Capital upsilon
 Φ  03a6 Capital phi
 Χ  03a7 Capital chi
 Ψ  03a8 Capital psi
 Ω  03a9 Capital omega
 ϊ  03aa Capital iota with diaeresis
 ϋ  03ab Capital upsilon with diaeresis
 ά  03ac Small alpha with acute
 έ  03ad Small epsilon with acute
 ή  03ae Small eta with acute
 ί  03af Small iota with acute
 ΰ  03b0 Small upsilon with acute and diaeresis
 α  03b1 Small alpha
 β  03b2 Small beta
 γ  03b3 Small gamma
 δ  03b4 Small delta
 ε  03b5 Small epsilon
 ζ  03b6 Small zeta
 η  03b7 Small eta
 θ  03b8 Small theta
 ι  03b9 Small iota
 κ  03ba Small kappa
 λ  03bb Small lamda
 μ  03bc Small mu
 ν  03bd Small nu
 ξ  03be Small xi
 ο  03bf Small omicron
 π  03c0 Small pi
 ρ  03c1 Small rho
 ς  03c2 Small final sigma
 σ  03c3 Small sigma
 υ  03c4 Small tau
 υ  03c5 Small upsilon
 φ  03c6 Small phi
 χ  03c7 Small chi
 ψ  03c8 Small psi
 ω  03c9 Small omega
 ϊ  03ca Small iota with diaeresis
 ϋ  03cb Small upsilon with diaeresis
 ό  03cc Small omicron with acute
 ύ  03cd Small upsilon with acute
 ώ  03ce Small omega with acute