|
ΗΥ 280: Θεωρία Υπολογισμού, Χειμερινό Εξ. 2025 |
Τα τέσσερα πρώτα σχέδια αποτελούν τέσσερις από τις έντεκα λιθογραφίες του Pablo Picasso στην σειρά λιθογραφιών με τίτλο Le Taureau [Wikipedia]. Το πέμπτο σχέδιο είναι μια φανταστική απεικόνιση στον κόσμο των πεπερασμένων αυτομάτων.
Περιγραφή Μαθήματος
Το μάθημα αποτελεί μια εισαγωγή στη ϑεωρία του υπολογισμού — τον κλάδο της επιστήμης των υπολογιστών που επιδιώκει να κατανοήσει ποια προβλήματα μπορούν να επιλυθούν υπολογιστικά και πόσο αποτελεσματικά μπορούν να επιλυθούν. Για να μπορούμε να διατυπώνουμε αυστηρές και ακριβείς δηλώσεις σχετικά με τον υπολογισμό, χρησιμοποιούμε αφηρημένα μαθηματικά μοντέλα υπολογιστικών συσκευών, γνωστά ως μοντέλα υπολογισμού.
Η ανάπτυξη της ύλης γίνεται στα εξής επίπεδα:
- Ανάπτυξη και μελέτη ουσιαστικών υπολογιστικών μοντέλων, όπως τα πεπερασμένα αυτόματα και οι ασυμφραστικές γραμματικές, τα οποία, αν και περιορισμένα, στην πράξη αποδεικνύονται εξαιρετικά χρήσιμα.
- Μοντέλα με πλήρη υπολογιστική ισχύ, όπως οι μηχανές Turing, και διερεύνηση των όριων του υπολογισμού.
Το μάθημα εισάγει ϑεμελιακές έννοιες σχετικές με το τι σημαίνει υπολογίζω και ποιες είναι οι δυνατότητες και οι περιορισμοί κάθε μοντέλου υπολογισμού. Περιλαμβάνει επίσης ϑεμελιώδη αποτελέσματα σχετικά με το κρίσιμο ερώτημα:
«Τι μπορούμε, αλλά και τι δεν μπορούμε να υπολογίσουμε;»
Οι μαθησιακοί στόχοι του μαθήματος είναι:
- Η κατανόηση του τρόπου αυστηρής συλλογιστικής σχετικά με τον υπολογισμό μέσω της χρήσης αφηρημένων, τυπικών μοντέλων.
- Η κατανόηση των μαθηματικών ϑεμελίων και τις δυνατότητες μοντέλων όπως τα πεπεϱασμένα αυτόματα, οι ασυμφραστικές γραμματικές και οι μηχανές Turing.
- Η εκμάθηση του τρόπου με τον οποίο ϑεμελιώδη ϕιλοσοφικά ερωτήματα σχετικά με τη ϕύση του υπολογισμού (Υπάρχουν προβλήματα που δεν μπορούν να λυθούν από υπολογιστές; Μπορεί κάθε πρόβλημα για το οποίο μπορούμε να επαληθεύσουμε γρήγορα μια λύση να λυθεί επίσης αποτελεσματικά;) μπορούν να τυποποιηθούν ως ακριβή μαθηματικά προβλήματα.
- Η απόκτηση εμπειρίας στην δημιουργική επίλυση μαθηματικών προβλημάτων και παϱαγωγής σωστών, σαφών και συνοπτικών μαθηματικών αποδείξεων.
| Διδάσκων: | Κωνσταντίνος Βάρσος, 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 | ||
| Ώρες Διδασκαλίας: | Δευτέρα 13:00-15:00 (ΣΟ) | |
| Τρίτη 15:00-17:00 (ΣΟ) | ||
| Παρασκευή 13:00-15:00 (Α113)-Φροντιστήριο |
Χρήσιμοι Σύνδεσμοι
Σελίδα Μαθήματος: https://www.csd.uoc.gr/~hy280/. Η σελίδα το μαθήματος περιέχει την ύλη του μαθήματος, το πρόγραμμα των διαλέξεων, τις ασκήσεις, και άλλο πρόσθετο υλικό.
eLearn: https://elearn.uoc.gr/. Οι διαφάνειες του μαθήματος περιέχονται στην πλατφόρμα eLearn. Εκεί παραδίδονται και οι ασκήσεις του μαθήματος σε pdf.
Περιεχόμενα μαθήματος
- Αυτόματα και Θεωρία Τυπικής Γλώσσας. Ντετερμινιστικά πεπερασμένα αυτόματα, μη ντετερμινιστικά πεπερασμένα αυτόματα, κανονικές εκφράσεις. Μη κανονικές γλώσσες. Αυτοματα στοίβας, Γραμματικές χωρίς συμφραζόμενα, Γλώσσες χωρίς συμφραζόμενα.
- Θεωρία Υπολογισιμότητας. Μηχανές Turing και η ϑέση Church-Turing. Αποφασισιμότητα, πρόβλημα τερματισμού. Αναγωγές.
- Θεωρία Πολυπλοκότητας. Χρονική πολυπλοκότητα, Χωρική πολυπλοκότητα.
Ημερολόγιο Μαθήματος
| Ημερομηνία | Περιεχόμενο | Αναφορές |
|---|---|---|
| Διάλεξη 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 |
| Φροντιστήριο 4: 17/10 | Γλώσσες χωρίς Συμφραζόμενα | Ασκ.: Tutorial04.pdf |
| Πρόοδος: 8/11 14:00-17:00 | ||
| Διάλεξη 9: 20/10 | Αυτόματα Στοίβας | Sipser, Κεφ. 2.2 Διαφ.: Lecture09.pdf |
| Διάλεξη 10: 21/10 | Γλώσσες Χωρίς και Με Συμφραζόμενα | Sipser, Κεφ. 2.3 Διαφ.: Lecture10.pdf |
| Φροντιστήριο 5: 24/10 | Αυτόματα Στοίβας | Ασκ.: Tutorial05.pdf |
| Διάλεξη 11: 27/10 | Μηχανές Turing | Sipser, Κεφ. 3.1 Διαφ.: Lecture11.pdf |
Ασκήσεις
- Άσκηση 1, παράδοση 24/10.
Βιβλιογραφία
Τα συγγράμματα του ΗΥ-280 Θεωρία Υπολογισμού είναι:
- Εισαγωγή στην Θεωρία Υπολογισμού, M. Sipser, Πανεπιστημιακές Εκδόσεις Κρήτης
- Στοιχεία Θεωρίας Υπολογισμού, L.R. Lewis, C.H. Papadimitriou, Εκδόσεις Κριτική
- Στα κομμάτια της ύλης που δεν καλύπτονται από κάποιο ϐιβλίο ϑα δοθούν σημειώσεις.
Επιπρόσθετο Διδακτικό Υλικό
- Richard Hammack, Book of Proof. Διαθέσιμο διαδικτυακά εδώ.
Βαθμολόγηση
Ο ϐαθμός σας στο μάθημα ϑα καθοριστεί από την τελική εξέταση, τις εργασίες για το σπίτι, και μια προεραιτική πρόοδο. Πιο συγκεκριμένα, η συνολική ϐαθμολογία σας είναι
Βαθμός : 0.5 × ΤΕ + 0.3 × max{ΤΕ, Π} + 0.2 × ΦΑ,
όπου (ΦΑ) 3 υποχρεωτικά ϕυλλάδια ασκήσεων + 1 προαιρετικό (στο τέλος του εξαμήνου), (Π) Προαιρετική πρόοδος 08/11, και (ΤΕ) Τελική εξέταση.
Κώδικας Δεοντολογίας, για την Επίλυση Ασκήσεων
Η συνεργασία και η συζήτηση αποτελούν ϑεμελιώδη στοιχεία για τη γέννηση ιδεών στην ακαδημαϊκή κοινότητα, και σας ενθαρύνουμε να συνεργάζεστε με τους συμφοιτητές σας για την αναζήτηση ιδεών και λύσεων στις ασκήσεις. Είναι σημαντικό να αναγνωρίζετε τον τρόπο και την πηγή της βοήθειας που λάβατε για διάφορους λόγους, συμπεριλαμβανομένων της ακαδημαϊκής ακεραιότητας, της ηθικής, και της αξιοπιστίας. Προς αυτό, η χρήση ϐοηθών Τεχνητής Νοημοσύνης (ΑΙ) επιτρέπεται μόνο για να σας ϐοηθήσει να κατανοήσετε το υλικό του μαθήματος, αλλά όχι για να λύνει τις ασκήσεις. Είναι απαραίτητο να δηλώνετε ϱητά πώς ακριβώς χρησιμοποιήσατε το εργαλείο ΑΙ. Η μη αναφορά της χρήσης Τεχνητής Νοημοσύνης συνιστά σοβαρή παραβίαση της ακαδημαϊκής ακεραιότητας και αντιμετωπίζεται αναλόγως!
Υλικό Παλαιότερων Ετών
Θέματα Παλαιότερων Ετών |
Σημειώσεις καθ. Γ.Φ. Γεωργακόπουλου: |