CSD, UoC logo

ΗΥ 280: Θεωρία Υπολογισμού, Χειμερινό Εξ. 2025 [Υπό κατασκευή]

Picasso's taurus as automaton.

Τα τέσσερα πρώτα σχέδια αποτελούν τέσσερις από τις έντεκα λιθογραφίες του Pablo Picasso στην σειρά λιθογραφιών με τίτλο Le Taureau [Wikipedia]. Το πέμπτο σχέδιο είναι μια φανταστική απεικόνιση στον κόσμο των πεπερασμένων αυτομάτων.


Περιγραφή Μαθήματος

Το μάθημα αποτελεί μια εισαγωγή στη ϑεωρία του υπολογισμού — τον κλάδο της επιστήμης των υπολογιστών που επιδιώκει να κατανοήσει ποια προβλήματα μπορούν να επιλυθούν υπολογιστικά και πόσο αποτελεσματικά μπορούν να επιλυθούν. Για να μπορούμε να διατυπώνουμε αυστηρές και ακριβείς δηλώσεις σχετικά με τον υπολογισμό, χρησιμοποιούμε αφηρημένα μαθηματικά μοντέλα υπολογιστικών συσκευών, γνωστά ως μοντέλα υπολογισμού.

Η ανάπτυξη της ύλης γίνεται στα εξής επίπεδα:

  1. Ανάπτυξη και μελέτη ουσιαστικών υπολογιστικών μοντέλων, όπως τα πεπερασμένα αυτόματα και οι ασυμφραστικές γραμματικές, τα οποία, αν και περιορισμένα, στην πράξη αποδεικνύονται εξαιρετικά χρήσιμα.
  2. Μοντέλα με πλήρη υπολογιστική ισχύ, όπως οι μηχανές Turing, και διερεύνηση των όριων του υπολογισμού.

Το μάθημα εισάγει ϑεμελιακές έννοιες σχετικές με το τι σημαίνει υπολογίζω και ποιες είναι οι δυνατότητες και οι περιορισμοί κάθε μοντέλου υπολογισμού. Περιλαμβάνει επίσης ϑεμελιώδη αποτελέσματα σχετικά με το κρίσιμο ερώτημα:

«Τι μπορούμε, αλλά και τι δεν μπορούμε να υπολογίσουμε;»

Οι μαθησιακοί στόχοι του μαθήματος είναι:

  1. Η κατανόηση του τρόπου αυστηρής συλλογιστικής σχετικά με τον υπολογισμό μέσω της χρήσης αφηρημένων, τυπικών μοντέλων.
  2. Η κατανόηση των μαθηματικών ϑεμελίων και τις δυνατότητες μοντέλων όπως τα πεπεϱασμένα αυτόματα, οι ασυμφραστικές γραμματικές και οι μηχανές Turing.
  3. Η εκμάθηση του τρόπου με τον οποίο ϑεμελιώδη ϕιλοσοφικά ερωτήματα σχετικά με τη ϕύση του υπολογισμού (Υπάρχουν προβλήματα που δεν μπορούν να λυθούν από υπολογιστές; Μπορεί κάθε πρόβλημα για το οποίο μπορούμε να επαληθεύσουμε γρήγορα μια λύση να λυθεί επίσης αποτελεσματικά;) μπορούν να τυποποιηθούν ως ακριβή μαθηματικά προβλήματα.
  4. Η απόκτηση εμπειρίας στην δημιουργική επίλυση μαθηματικών προβλημάτων και παϱαγωγής σωστών, σαφών και συνοπτικών μαθηματικών αποδείξεων.
Διδάσκων:   Κωνσταντίνος Βάρσος, varsosk [at] uoc [dot] gr
Ώρες Γραφείου:   Δευτέρα 15:00-16:00 (H-301))
    Τρίτη 17:00-18:00 PM (Η-301)
     
Βοηθοί Διδασκαλίας:   Κωνσταντίνος Αναγνωστάκης, csdp1390 [at] csd [dot] uoc [dot] gr
    Μαρία-Μυρτώ Βίλλια, mvillia [at] ics [dot] forth [dot] gr
    Εντίσα-Τζεορτζιάνα Κομοριτσάν, tzeortziana [at] csd [dot] uoc [dot] gr
    Χριστίνα Μπρόζι, brozi [at] csd [dot] uoc [dot] gr
    Γιώργος Ξανθάκης, gxanth [at] csd [dot] uoc [dot] gr
    Μερκούρης Παπαμιχαήλ, merkourisp [at] csd [dot] uoc [dot] gr
     
Ώρες Διδασκαλίας:   Δευτέρα 15:00-16:00 (ΑΜΦ. ΣΟ)
    Τρίτη 15:00-17:00 (ΑΜΦ. ΣΟ)
    Παρασκευή 15:00-17:00 (Α113)-Φροντιστήριο

Χρήσιμοι Σύνδεσμοι

Σελίδα Μαθήματος: https://www.csd.uoc.gr/~hy280/. Η σελίδα το μαθήματος περιέχει την ύλη του μαθήματος, το πρόγραμμα των διαλέξεων, τις ασκήσεις, και άλλο πρόσθετο υλικό.

eLearn: https://elearn.uoc.gr/. Οι διαφάνειες του μαθήματος περιέχονται στην πλατφόρμα eLearn. Εκεί παραδίδονται και οι ασκήσεις του μαθήματος σε pdf.


Περιεχόμενα μαθήματος

  1. Αυτόματα και Θεωρία Τυπικής Γλώσσας. Ντετερμινιστικά πεπερασμένα αυτόματα, μη ντετερμινιστικά πεπερασμένα αυτόματα, κανονικές εκφράσεις. Μη κανονικές γλώσσες. Αυτοματα στοίβας, Γραμματικές χωρίς συμφραζόμενα, Γλώσσες χωρίς συμφραζόμενα.
  2. Θεωρία Υπολογισιμότητας. Μηχανές Turing και η ϑέση Church-Turing. Αποφασισιμότητα, πρόβλημα τερματισμού. Αναγωγές.
  3. Θεωρία Πολυπλοκότητας. Χρονική πολυπλοκότητα, Χωρική πολυπλοκότητα.

Ημερολόγιο Μαθήματος

Ημερομηνία Περιεχόμενο Αναφορές
Διάλεξη 1: 22/9 Μαθηματικό υπόβαθρο, Πεπερασμένα Αυτόματα Sipser, Κεφ. 0, 1.1.1-1.1.3. Διαφ.: Lecture01.pdf
Διάλεξη 2: 23/9 Πεπερασμένα Αυτόματα, Αιτιοκρατία Sipser, Κεφ. 1.1.4-1.1.5, 1.2.1. Διαφ.: Lecture02.pdf
Φροντιστήριο 1: 26/9 Πεπερασμένα Αυτόματα Ασκ.: Tutorial01.pdf
Διάλεξη 3: 29/9 Αιτιοκρατία Sipser, Κεφ. 1.2.1. Διαφ.: Lecture03.pdf
Διάλεξη 4: 30/9 Αιτιοκρατία, Κανονικές Εκφράσεις Sipser, Κεφ. 1.2.2, 1.2.3, 1.3.1. Ισοδυναμία NFA με DFA. Διαφ.: Lecture04.pdf. Υλικό: Equivalence NFA DFA.pdf
Φροντιστήριο 2: 3/10 Αιτιοκρατία Ασκ.: Tutorial02.pdf
Διάλεξη 5: 6/10 Κανονικές Εκφράσεις Sipser, Κεφ. 1.3.2, 1.4. Διαφ.: Lecture05.pdf
Διάλεξη 6: 7/10 Μη Κανονικές Γλώσσες Sipser, Κεφ. 1.4. Θεώρημα Myhill-Nerode. Διαφ.: Lecture06.pdf. Υλικό: Myhill-Nerode.pdf
Φροντιστήριο 3: 10/10 Κανονικές και Μη Κανονικές Γλώσσες Ασκ.: Tutorial03.pdf
Διάλεξη 7: 13/10 Γλώσσες Χωρίς Συμφραζόμενα Sipser, Κεφ. 2.1.1-2.1.3. Διαφ.: Lecture07.pdf
Διάλεξη 8: 14/10 Γλώσσες Χωρίς Συμφραζόμενα Sipser, Κεφ. 2.1.4, 2.1.5. Διαφ.: Lecture08.pdf
Πρόοδος: 8/11 14:00-16:00

Ασκήσεις

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

Τα συγγράμματα του ΗΥ-280 Θεωρία Υπολογισμού είναι:

Επιπρόσθετο Διδακτικό Υλικό

Βαθμολόγηση

Ο ϐαθμός σας στο μάθημα ϑα καθοριστεί από την τελική εξέταση, τις εργασίες για το σπίτι, και μια προεραιτική πρόοδο. Πιο συγκεκριμένα, η συνολική ϐαθμολογία σας είναι

Βαθμός : 0.5 × ΤΕ + 0.3 × max{ΤΕ, Π} + 0.2 × ΦΑ,

όπου (ΦΑ) 3 υποχρεωτικά ϕυλλάδια ασκήσεων + 1 προαιρετικό (στο τέλος του εξαμήνου), (Π) Προαιρετική πρόοδος 08/11, και (ΤΕ) Τελική εξέταση.

Κώδικας Δεοντολογίας, για την Επίλυση Ασκήσεων

Η συνεργασία και η συζήτηση αποτελούν ϑεμελιώδη στοιχεία για τη γέννηση ιδεών στην ακαδημαϊκή κοινότητα, και σας ενθαρύνουμε να συνεργάζεστε με τους συμφοιτητές σας για την αναζήτηση ιδεών και λύσεων στις ασκήσεις. Η χρήση ϐοηθών Τεχνητής Νοημοσύνης (ΑΙ) επιτρέπεται στον ϐαθμό που σας ϐοηθάει να κατανοήσετε το υλικό του μαθήματος, αλλά όχι για να λύνει τις ασκήσεις. Είναι απαραίτητο να δηλώνετε ϱητά πώς ακριβώς χρησιμοποιήσατε το εργαλείο ΑΙ. Η μη αναφορά της χρήσης Τεχνητής Νοημοσύνης συνιστά σοβαρή παραβίαση της ακαδημαϊκής ακεραιότητας και αντιμετωπίζεται αναλόγως!

Υλικό Παλαιότερων Ετών

Θέματα Παλαιότερων Ετών

Σημειώσεις καθ. Γ.Φ. Γεωργακόπουλου: