Θεωρία της Πληροφορίας

Το 1948, με την εργασία « A Mathematical Theory of Communication” του Shannon γεννήθηκε μια νέα επιστημονική περιοχή, η Θεωρία της Πληροφορίας ή Θεωρία Πληροφοριών. Στόχος της είναι η θεμελίωση εννοιών και θεωρημάτων που επιτρέπουν τη μαθηματική περιγραφή της διαδικασίας της επικοινωνίας. (…)Αν και αρχικά η θεωρία της πληροφορίας αποτέλεσε τμήμα της επιστήμης των επικοινωνιών, από πολύ νωρίς οι αρχές, οι μεθοδολογίες και τα συμπεράσματά της βρήκαν εφαρμογή και σε άλλες επιστημονικές περιοχές.
Σύμφωνα με τη θεωρία πληροφοριών ένα σύστημα επικοινωνίας περιλαμβάνει τον πομπό, τον δίαυλο και τον δέκτη.

file:///C:/Users/User/Downloads/TeachN-2003-1st-IntroIT--neoMathima.pdf

3 ΤΟ ΑΛΓΟΡΙΘΜΙΚΩΣ ΣΚΕΠΤΕΣΘΑΙ
3.1 Εισαγωγή
Η ανθρώπινη σκέψη είναι µιά σύνθετη γνωστική, λογική και ψυχική διεργασία, στην
οποία σηµαντικό ρόλο παίζει η ιστορία του ανθρώπινου είδους, όπως αποτυπώνεται
στις εσωτερικές δοµές του εγκεφάλου και σε γνώσεις που µεταδίδονται κοινωνικά και
βιολογικά.
Ήδη ο Πλάτων επέµενε ότι ο ανθρώπινος εγκέφαλος διαθέτει ορισµένες έτοιµες
«υποδοµές», στις οποίες βασίζεται η περαιτέρω ανάπτυξή του. Στο ίδιο συµπέρασµα
καταλήγει η σύγχρονη επιστήµη, που αναγνωρίζει ότι ορισµένες έννοιες είναι αρχικές
και έµφυτες. Γιά παράδειγµα, η αιτιότητα εµφανίζεται στα παιδιά χωρίς κανείς να τη
διδάξει. Ο Κάντ ανέπτυξε τη θεωρία των «συνθετικών προτέρων» (synthetic a priori),
που υποστηρίζει ότι οι ορισµοί των νοητών γίνονται µε αναφορά σε τέτοιες αρχικές
έννοιες, όπως «η ευθεία γραµµή είναι ο πιό σύντοµος δρόµος µεταξύ δύο σηµείων», ή
«κάθε µεταβολή έχει µιά αιτία» (Κάντ, «Κριτική του Καθαρού Λόγου»). Η
µετασχηµατιστική γλωσσολογία (που εξετάζεται σε άλλες Ενότητες) βασίζεται επίσης
στην αρχή ότι «η γλώσσα δεν προέρχεται εµπειρικά και αποκλειστικά από το
περιβάλλον αλλά ότι κατευθύνεται κυρίως από µιά εσωτερική έµφυτη δοµή της οποίας
το βασικότερο χαρακτηριστικό είναι η άπειρη δηµιουργικότητα και πρωτοτυπία» του
ατόµου. Υποσύστηµα της ανθρώπινης σκέψης είναι η λογική. Ειδική εκδοχή της λογικής είναι η
τυπική, ή µαθηµατική, λογική (formal logic). Η τυπική λογική µπορεί να χρησιµοποιηθεί
στους Η/Υ. Αν ακολουθήσουµε την αντίστροφη πορεία, µπορούµε να αποκτήσουµε µιά
αίσθηση του δρόµου που πρέπει να διανυθεί για να φτάσει κανείς στη «σκεπτόµενη
µηχανή» που µοιάζει µε ανθρώπινο όν.
ΕΙΣΑΓΩΓΗ ΣΤΗ ΠΛΗΡΟΦΟΡΙΚΗ
35
Η τυπική λογική αναπτύχθηκε σε πλάτος και βάθος από τον Αριστοτέλη. Η µαθηµατική
λογική εισήγαγε τον «φορµαλισµό» στην Αριστοτελική λογική και την ανέπτυξε
περαιτέρω. Η Αριστοτελική λογική, ως φυσική συνέχεια της Πλατωνικής µεθόδου, είναι
ταυτόχρονα και ∆ιαλεκτική, ασχολείται δηλαδή µε τη ταξινόµηση και οργάνωση της
γνώσης, µέσα από σχήµατα που είναι παραγωγικά, όχι µόνο αναλυτικά.
Η αρχαία µέθοδος είναι κυρίως αξιωµατική. Βασίζεται σε ορισµένα αιτήµατα, όπως της
παραλληλίας του Ευκλείδη, και ορισµένες αρχές επίλυσης, όπως ο κανόνας και ο
διαβήτης. Πάνω σε αυτά οικοδοµεί ένα καλά αρθρωµένο σύστηµα χρησιµοποιώντας
καλώς προσδιορισµένες µεθόδους συµπερασµού/απόδειξης, όπως η «εις άτοπον
απαγωγή». Η αλλαγή των αιτηµάτων µπορεί να οικοδοµήσει άλλα συστήµατα (όπως
έγινε µε τις λεγόµενες µη-Ευκλείδειες γεωµετρίες). Άρα και από την άποψη αυτή η
αξιωµατική µέθοδος είναι παραγωγική. Και στην αρχαιότητα όµως αναπτύχθηκαν και άλλες προσεγγίσεις που «παραβίαζαν»
αυτή τη καθαρότητα των µεθόδων. Έτσι, εµφανίστηκαν µέθοδοι επίλυσης
προβλήµατος που δεν χρησιµοποιούσαν µόνο κανόνα και διαβήτη. Στη νεώτερη
επιστήµη, τέτοιες µέθοδοι αναπτύχθηκαν πολλές. Γιά παράδειγµα, εκτός της
αναλυτικής ολοκλήρωσης υπάρχει και η υπολογιστική ολοκλήρωση (πχ κανόνες
τραπεζίου, ή κανόνες Simpson) και ένας ολόκληρος κλάδος υπολογιστικών
µαθηµατικών. Η εµφάνιση των υπολογιστών αξιοποίησε πλήρως αυτές τις
υπολογιστικές µεθόδους. Αντιστοίχως, αναπτύχθηκαν πολλές άλλες µέθοδοι που
περιγράφονται µεν µέσω ακολουθίας λογικώς διαρθρωµένων οδηγιών, δεν
ακολουθούν όµως µιά «καθαρή» αναλυτική µέθοδο. Γιά τον λόγο αυτό συχνά οι
µέθοδοι αυτές δίνουν µιά προσεγγιστική λύση, δεν εγγυώνται όµως ότι η λύση αυτή
είναι η καλύτερη.

3.2 Αλγοριθµική προσέγγιση, υπολογισµός, υπολογιστές
Όπως και άλλες έννοιες, έτσι και η έννοια του «αλγόριθµου» πρέπει να θεωρηθεί
αρχική. Αυτό όχι διότι δεν υπάρχει ορισµός του, αλλά διότι υπάρχουν διαφορετικοί
τρόποι ορισµού του. Εµπειρικά, ο αλγόριθµος είναι µιά ακολουθία, µιά σειρά οδηγιών
που η εφαρµογή τους οδηγεί σε κάποιο επιθυµητό αποτέλεσµα (κάποιο στόχο).
Μαθηµατικοί που θεµελίωσαν τη θεωρία του υπολογισµού, χρησιµοποίησαν
διαφορετικούς ορισµούς-προσεγγίσεις. Αφετηρία µπορεί να θεωρηθεί η προσπάθεια
του Hilbert να κατασκευαστεί ένα µαθηµατικό σύστηµα, ένας αλγόριθµος, που να
επιτρέπει:
1. την επακριβή διατύπωση όλων των προβληµάτων µε µορφή δηλώσεων που κάθε
µία θα µπορεί να είναι είτε αληθής, είτε ψευδής
2. την απόφαση (Entscheidungsproblem) αν οποιαδήποτε τέτοια δήλωση του
τυπικού συστήµατος είναι αληθής ή ψευδής. Με λιγότερο αυστηρό τρόπο, ο Leibniz επίσης είχε θέσει το ζήτηµα της
χρησιµοποίησης ενός «λογισµού» (calculus), µιάς «τέχνης» (Ars) υπολογισµού των
αποφάσεων. Το θεώρηµα της «µη-πληρότητας» του Goedel, ανάµεσα στα άλλα, έδειξε ότι δεν
υπάρχει τέτοιος υπολογιστικός αλγόριθµος, ότι το πρόβληµα του Hilbert δεν είναι
«υπολογίσιµο». Ακολούθησαν το δρόµο του Goedel µαθηµατικοί, όπως οι Alonso
Church, Stephen Kleene, Emil Post, Allan Turing, που διερεύνησαν άλλα ζητήµατα
υπολογισιµότητας (computability) και εισηγήθηκαν νέες προσεγγίσεις. Είναι
αξιοσηµείωτο ότι αυτές οι διερευνήσεις της υπολογισιµότητας έγιναν σε µιά περίοδο
(δεκαετία 1930) που δεν είχαν εµφανιστεί οι σύγχρονοι ηλεκτρονικοί υπολογιστές.
ΕΙΣΑΓΩΓΗ ΣΤΗ ΠΛΗΡΟΦΟΡΙΚΗ
37
Οι µαθηµατικοί αυτοί είχαν διαφορετικές προσεγγίσεις ως προς το «τι εστί
αλγόριθµος». Έτσι ο Goedel εννοούσε τον αλγόριθµο ως ακολουθία κανόνων για τον
σχηµατισµό µαθηµατικών συναρτήσεων, απλών και σύνθετων (που αποτελούνται από
απλές). Ο Church χρησιµοποίησε ένα ειδικό τύπο λογισµού που ονοµάστηκε Λογισµός
Λάµδα (Lambda Calculus), ενώ ο Turing µιά υποθετική µηχανή που ονοµάστηκε
Μηχανή Turing (Turing Machine).
Οι Church και Turing αντιµετώπισαν το ζήτηµα που προέκυψε από την εµφάνιση
διαφορετικών ορισµών του αλγορίθµου µε τη λεγόµενη «Θέση Church - Turing». Σε
επόµενη ενότητα αναφέρονται περισσότερα στοιχεία για τη Θέση. Εδώ αρκεί να δοθεί
η εξής διατύπωση:
1. Όλοι οι εύλογοι ορισµοί του «αλγορίθµου» που έχουν δοθεί είναι ισοδύναµοι. 2. Κάθε νέος εύλογος ορισµός του «αλγορίθµου» θα είναι ισοδύναµος µε τους
γνωστούς. Με άλλα λόγια, η Θέση σηµαίνει ότι αν κάτι µπορεί να υπολογιστεί µε ένα αλγόριθµο,
τότε µπορεί να υπολογιστεί µε κάθε άλλο αλγόριθµο. Ή, ότι αν έχουµε διατυπώσει µε
εύλογο τρόπο, ίσως µη-τυπικό, µιά ακολουθία οδηγιών, τότε µπορεί να προκύψει ένας
ισοδύναµος τυπικός αλγόριθµος. Η Θέση δεν αποδείχθηκε µε κάποιο τυπικό τρόπο. Ούτε όµως απορρίφθηκε µέχρι σήµερα. Έτσι θεωρείται αποδεκτή. Η ανάπτυξη όµως
των υπολογιστών ενίσχυσε την αποδοχή της Θέσης. Ξέρουµε ότι κάθε αλγόριθµος που
µπορεί να υλοποιηθεί σε ένα υπολογιστή, µπορεί να υλοποιηθεί σε κάθε άλλο
υπολογιστή (ανεξαρτήτως αν αυτό γίνεται ευκολότερα, ή γρηγορότερα σε ένα
υπολογιστή από ότι σε ένα άλλο). Άρα έχουµε µιά ισοδυναµία των υπολογιστικών
µηχανών µεταξύ τους, αλλά και µε τη Μηχανή Turing.
Από µιά άλλη άποψη, κάθε υπολογιστής µπορεί να «µιµηθεί», να προσοµοιώσει κάθε
άλλο υπολογιστή. Η έννοια της µίµησης (mimesis), ή της προσοµοίωσης (simulation)
έχει µακρά ιστορία, από τον Πλάτωνα (πχ «Πολιτεία»), τον Αριστοτέλη (πχ «Ποιητική»),
ΕΙΣΑΓΩΓΗ ΣΤΗ ΠΛΗΡΟΦΟΡΙΚΗ
© Γιάννης Βενέρης, Αναπληρωτής Καθηγητής ΕΜΠ 38
ως τον Turing (imitation game) και τις σύγχρονες τεχνικές της οιονεί πραγµατικότητας
(virtual reality). Μπορούµε άρα να αναφερθούµε στη καθολικότητα (universality) των
αλγορίθµων.

5.1 Εισαγωγή στην αναπαράσταση οντοτήτων µέσω ιδιοτήτων
Ως πρωτογενείς θεωρούµε τις οντότητες που κάθε τύπος προγράµµατος χειρίζεται.
Αυτά µπορεί να είναι αρχεία και κατάλογοι για το λειτουργικό σύστηµα, φράσεις- παράγραφοι για την επεξεργασία κειµένου, µέρη σχεδίου για τα προγράµµατα ΣµΥ,
κτλ.
Η γενική τάση για την αναπαράσταση των πρωτογενών οντοτήτων οποιασδήποτε
κατηγορίας στη σύγχρονη Πληροφορική Τεχνολογία εµπνέεται από τις αντιλήψεις του
«αντικειµενοστρεφούς προγραµµατισµού» (object oriented programming), που θέλει
κάθε οντότητα να παριστάνεται µέσω ενός συνόλου ιδιοτήτων και των αντίστοιχων
τιµών που αυτές µπορεί να λάβουν, και από ορισµένες άλλες δηλώσεις που
καθορίζουν τη «συµπεριφορά» της οντότητας. Μπορούµε να κατανοήσουµε τον τρόπο αυτό παράστασης και µε τους όρους της
συµβατικής γλώσσας. Οι ιδιότητές αναφέρονται σε αυτά που µπορούµε να
αποδώσουµε σε κάθε ουσιαστικό µέσω του ρήµατος «είναι»:
ΤΟ ΤΡΑΠΕΖΙ ΕΙΝΑΙ ΞΥΛΙΝΟ
ΤΟ ΤΡΑΠΕΖΙ ΕΙΝΑΙ ΚΟΚΚΙΝΟ
ΤΟ ΤΡΑΠΕΖΙ ΕΙΝΑΙ ΜΙΚΡΟ
Ο ΦΟΙΒΟΣ ΕΙΝΑΙ ΨΗΛΟΣ
...
Πρόκειται δηλαδή για σταθερές ιδιότητες του αντικειµένου. OBJECT_ ATTRIBU ATTRIBU … ATTRIBU BEHAVIO BEHAVIO … BEHAVIO
ΕΙΣΑΓΩΓΗ ΣΤΗ ΠΛΗΡΟΦΟΡΙΚΗ
95
Για κάθε αντικείµενο/ουσιαστικό µπορούµε επίσης να χρησιµοποιήσουµε διάφορα
ρήµατα:
ΤΟ ΤΡΑΠΕΖΙ ΕΣΠΑΣΕ
ΤΟ ΤΡΑΠΕΖΙ ΧΡΗΣΙΜΟΠΟΙΗΘΗΚΕ
Ο ΦΟΙΒΟΣ ΤΡΕΧΕΙ
...
Πρόκειται δηλαδή για «ενέργειες», ή «συµπεριφορές», του αντικειµένου, που
συνιστούν µεταβολή της κατάστασής του. Τα παραπάνω αποτελούν αρχέγονους
µηχανισµούς της σκέψης και της γλώσσας που η Πληροφορική Τεχνολογία αξιοποιεί.
Ορισµένα σχετικά στοιχεία δίνονται στην επόµενη Ενότητα.
Παρατηρούµε ότι κάθε µία από τις παραπάνω διατυπώσεις αποτελείται από τρία
στοιχεία: το πρώτο είναι το όνοµα του αντικειµένου, το δεύτερο κάποια ιδιότητά του (ή
χαρακτηριστικό του, µε την ευρεία έννοια) και το τρίτο µια τιµή που λαµβάνει η ιδιότητα. Αυτό µπορεί να γραφεί ως εξής:
<ΑΝΤΙΚΕΙΜΕΝΟ> <Ι∆ΙΟΤΗΤΑ> <ΤΙΜΗ>
<OBJECT> <PROPERTY> <VALUE>
(Στα αγγλικά, αντί της λέξης property (ιδιότητα) µπορεί να χρησιµοποιηθεί και η λέξη
attribute (χαρακτηριστικό)).
Η διατεταγµένη αυτή τριάδα µπορεί να θεωρηθεί µε την έννοια του πλαισίου (frame),
το οποίο έχει κάποιες "θέσεις" (slots) στις οποίες "τοποθετούνται" πράγµατα (fillers):
<FRAME> <SLOTS> <FILLERS>
Γενικότερα, και πιο απλά, είναι µια διατεταγµένη τριάδα, τέτοια ώστε τα δύο πρώτα
µέλη της να ορίζουν (µονοσήµαντα) το τρίτο.
ΕΙΣΑΓΩΓΗ ΣΤΗ ΠΛΗΡΟΦΟΡΙΚΗ
© Γιάννης Βενέρης, Αναπληρωτής Καθηγητής ΕΜΠ 96
<A> <B> <C>
Οι περιγραφές που δόθηκαν προηγουµένως µπορεί να γραφούν µε διαφορετικό τρόπο
για να εκφραστούν καλύτερα στη µορφή
<ΑΝΤΙΚΕΙΜΕΝΟ> <Ι∆ΙΟΤΗΤΑ> <ΤΙΜΗ>
ΤΟ ΤΡΑΠΕΖΙ ΕΙΝΑΙ ΞΥΛΙΝΟ
ΤΡΑΠΕΖΙ ΥΛΙΚΟ ΞΥΛΟ
ΤΟ ΤΡΑΠΕΖΙ ΕΙΝΑΙ ΜΙΚΡΟ
ΤΡΑΠΕΖΙ ΜΕΓΕΘΟΣ ΜΙΚΡΟ
ΤΟ ΤΡΑΠΕΖΙ ΕΙΝΑΙ ΚΟΚΚΙΝΟ
ΤΡΑΠΕΖΙ ΧΡΩΜΑ ΚΟΚΚΙΝΟ
Το όνοµα και οι ιδιότητες ορίζουν το «είδος», ενώ αυτά µαζί µε τις τιµές των ιδιοτήτων
ορίζουν ένα συγκεκριµένο «εκπρόσωπο» του είδους. Όπως δίνουµε τιµές στις ιδιότητες ενός αντικειµένου, µπορούµε και να τις ανακαλούµε. Επειδή οι ιδιότητες ορίζονται ως διατεταγµένες τριάδες, για την ανάκληση τιµών θα
πρέπει να χρησιµοποιήσουµε τα δύο πρώτα στοιχεία της διατεταγµένης τριάδας. ∆ηλαδή, δίνοντας τα <A> <B> θα πάρουµε το <C>.
Για κάθε αντικείµενο <A>, όλα τα ζεύγη των <B> <C> συγκροτούν τη λίστα ιδιοτήτων
του αντικειµένου αυτού. Από τα παραπάνω µπορούµε να κάνουµε µια πρώτη διάκριση των ιδιοτήτων σε δύο
τύπους. Ο πρώτος τύπος περιλαµβάνει ιδιότητες που οι τιµές τους είναι δεδοµένα, ενώ
ο δεύτερος περιλαµβάνει ιδιότητες που οι τιµές τους είναι εντολές προγραµµατισµού. Όµως οι προηγµένες γλώσσες προγραµµατισµού (όπως η LOGO και η LISP)
χειρίζονται µε τον ίδιο τρόπο τα δεδοµένα και τις εντολές προγραµµατισµού. Όπως τα
προγράµµατα τροποποιούν τα δεδοµένα, το ίδιο µπορεί να τροποποιούν και τα
προγράµµατα. Άρα, ένα πρόγραµµα µπορεί να µαθαίνει τόσο νέες γνώσεις, όσο και
ΕΙΣΑΓΩΓΗ ΣΤΗ ΠΛΗΡΟΦΟΡΙΚΗ
97
νέους "τρόπους σκέψης". Αυτό αποτελεί µια από τις βασικές προσεγγίσεις της
Τεχνητής Νοηµοσύνης.
Αυτές οι ιδιότητες χρησιµοποιούνται στη Τεχνητή Νοηµοσύνη, και επιτρέπουν την
αναπαράσταση γνώσεων (knowledge representation) στον υπολογιστή,
προσοµοιώνοντας τους µηχανισµούς των µνηµονικών συνδέσµων (associative
memory) που χρησιµοποιεί ο εγκέφαλος.
Η περιγραφή οντοτήτων και σχέσεων µέσω ιδιοτήτων/κατηγορούµενων
χρησιµοποιείται και στον «κατηγορικό λογισµό» (predicate calculus), που συνήθως
δηλώνει τη σχέση:
<A> <B> <C>
µε τον συµβολισµό: