Στοιχεία θεωρητικής πληροφορικής

Προηγούμενα θέματα για σκέψη

• Πρέπει να κατασκευαστεί λογισμικό που θα καθοδηγεί τον ταμία ενός καταστήματος στο να δίνει τα σωστά ρέστα στους πελάτες. Καταγράψτε ενδεικτικά το περιεχόμενο κάθε στάδιου του κύκλου ζωής του λογισμικού αυτού.
• Περιγράψτε με συντομία το περιεχόμενο των απαιτήσεων ενός συστήματος διασφάλισης ποιότητας για μια από τις παρακάτω δραστηριότητες:
  • Εκδρομή στο εξωτερικό
  • Ληστεία τράπεζας
  • Διοίκηση του Ελληνικού Κράτους

Επαλήθευση αλγορίθμων

• Προϋποθέσεις
• Μετασυνθήκες
• Αναλλοίωτες συνθήκες (Invariants)
• Συνθήκες σύγκλισης (Convergents)

Παράδειγμα

Είσοδος:
  Α(1..Ν): πίνακας ακεραίων
  N : ακέραιος
Έξοδος:
  Β(1..Ν): πίνακας ακεραίων

Προϋποθέσεις:
  Ν >= 1
Μετασυνθήκες:
  Β(1..Ν) περιέχει τις τιμές του Α(1..Ν)

Μεταβλητές
  Ι : Ακέραιος

I := 1
Όσο Ι <= Ν
  Β(Ι) := Α(Ι)
  Αναλοίωτη συνθήκη: Β(1..Ι) := Α(1..Ι)
  Συνθήκη σύγκλισης: Ν - Ι
  Ι := Ι + 1
Τέλος

Αποδοτικότητα των αλγορίθμων

• Η σημειογραφία Ο()
• Γραμμική ανίχνευση Ο(ν)
• Δυαδική ανίχνευση Ο(λογ ν)
• Διπλός βρόχος Ο(ν^2)
• Κατώτερο (απόδειξης) πραγματικό και ανώτερο (αλγοριθμικό) κόστος
• Κόστος μνήμης

Πολυπλοκότητα

• Ικανοποίηση λογικών συνθηκών: Ο(2^ν)
• Σύνθεση τετραγώνων: Ο(ν!)
• Σκάκι Ν*Ν: άλυτο
• Μη αιτιοκρατική πολυωνυμική πληρότητα (non deterministic polynomial completeness)

Μη υπολογισιμότητα

Το πρόβλημα του τερματισμού (halting problem)

Τερματίζει(Πρόγραμμα, Δεδομένα)
Είσοδος: Πρόγραμμα, Δεδομένα
Έξοδος: Αληθές αν το πρόγραμμα τερματίζει με τα δεδομένα,
αλλιώς ψευδές.

Δοκιμή(Πρόγραμμα, Δεδομένα)
Αν Τερματίζει(Πρόγραμμα, Δεδομένα) Τότε
  Όσο αληθές
  Τέλος (Όσο)
Αλλιώς
  Δοκιμή := ψευδές
Τέλος (Αν)

Δοκιμή(Δοκιμή ..., Δοκιμή ...)

Αλγοριθμική οικουμενικότητα

Πεπερασμένα αυτόματα (Finite automata)

1. Ι : Τιμές εισόδου
2. Ο : Τιμές εξόδου
3. S : Πεπερασμένο σύνολο εσωτερικών καταστάσεων
4. λ : S X I -> S Συνάρτηση επόμενης κατάστασης
5. δ : S X I -> O Συνάρτηση επόμενης τιμής εξόδου

Η μηχανή του Turing

1. Πεπερασμένο αλφάβητο: Α
2. Πεπερασμένο σύνολο καταστάσεων: Μ
3. Άπειρη ταινία
4. Κεφαλή γραφής και ανάγνωσης
5. Διάγραμμα μετάπτωσης: (Α Χ Μ) -> (Α X {Δ, Α, Σ}) Χ Μ

Παραδείγματα

• Εγγραφή συμβόλου στο τέλος της ταινίας
• Αντιγραφή ταινίας
• Πρόσθεση

Η θέση των Church/Turing

Πιθανοτικοί αλγόριθμοι

Δειπνούντες φιλόσοφοι

Για πάντα
   Πέτα νόμισμα και περίμενε το ανάλογο πηρούνι
   Αν υπάρχει και το άλλο πηρούνι Τότε
      πάρε το άλλο πηρούνι
      φάε
   Αλλιώς
      Άσε τα πηρούνια
   Τέλος
Τέλος

Λειτουργική και προσδιοριστική σημασιολογία

Λειτουργική σημασιολογία (Operational semantics)

Προσδιοριστική σημασιολογία (Denotational semantics)

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

• Peter Rechenberg. Εισαγωγή στην Πληροφορική. σ. 193-220 Κλειδάριθμος, 1992.

• Michael A. Arbib. Brains, Machines, and Mathematics. McGraw-Hill, 1963.

• David Harel. Algorithmics: the Spirit of Computing. Addison-Wesley, 1987.

• David A. Schmidt. Denotational Semantics: A Methodology for Language Development. Wm. C. Brown, 1986.

Ασκήσεις

• O(ν)
• O(λογ ν)
• O(ν!)
• O(2^ν)
• O(ν^2)
• O(ν^ν)

• Περιεχόμενα

 Τελευταία αλλαγή: Δευτέρα, 2 Αυγούστου 2004 12:27 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».