ΗΥ 280: Θεωρία Υπολογισμού

Πληροφορίες

Διαλέξεις

  • Πότε; :  Δευτέρα και Τετάρτη 13.00-15.00
  • Πού; : Αμφιθέατρο Στέλιος Ορφανουδάκης (ΑΜΦ ΣΟ)
  • Διδάσκων: Χαράλαμπος Ε. Τσουρακάκης
  • Email: tsourakakis@csd.uoc.gr

Φροντιστήριο

Το φροντιστήριο διδάσκεται σε εβδομαδιαία βάση από τον/την εκάστοτε βοηθό. Είναι μια εξαιρετική ευκαιρία να λύνετε προβλήματα μαζί με τους βοηθούς, σε πιο ήπιο ρυθμό από τη διάλεξη, με περισσότερο χρόνο για συζήτηση ώστε να κατανοήσετε την ύλη καλύτερα.

Πότε; : Παρασκευή 13.00-15.00
Πού; : Α113

Βοηθοί

Ώρες γραφείου

Πότε; Πού;
Χαράλαμπος Ε. ΤσουρακάκηςΔευτέρα, Τετάρτη 15.00-16.00μμΓραφείο Β303
Γιάννης Μαλλιωτάκης (PhD)Δευτέρα 11.00-12.00Διαδικτυακά (δείτε ανακοίνωση eLearn)
Γιώργος Ξανθάκης (PhD)Τετάρτη 10.00-11.00Διαδικτυακά (δείτε ανακοίνωση eLearn)
Noah Wahl (English only) (PhD)Τρίτη 11.00-12.00Διαδικτυακά (δείτε ανακοίνωση eLearn)
Ιωάννης Πλεξουσάκης (MSc) Πέμπτη 15:00-16:00B210
Άννα-Ολυμπιάς Κροκιδά (MSc) Πέμπτη 13.00-14.00B210
Μάνος Μπαλωτής (MSc) Τρίτη 12.00-13.00B210

Περίγραμμα μαθήματος (Syllabus)

Github

Βιβλία

Οποιοδήποτε από τα παρακάτω συγγράμματα μπορεί να χρησιμοποιηθεί ως βασικό βοήθημα. Ωστόσο, στο μάθημα θα καλύψουμε και ύλη πέρα από αυτή που περιλαμβάνεται στα συγγράμματα.

  1. Εισαγωγή στη Θεωρία Υπολογισμού του M. Sipser
    Αυτό είναι το προτεινόμενο, εκδόσεις ΠΕΚ, με άφθονα αντίγραφα διαθέσιμα στη βιβλιοθήκη.
  2. Στοιχεία Θεωρίας Υπολογισμού των Lewis και Παπαδημητρίου
  3. Το βιβλίο Διακριτά μαθηματικά του Μιχαήλ Κολουντζάκη και Χρήστου Παπαχριστοδούλου περιέχει 4 κεφάλαια (7 έως 10) που εντάσσονται στην ύλη μας, αλλά καλύπτει μόνο ένα μέρος του συνολικού περιεχομένου του μαθήματος. Τα αρχικά του κεφάλαια για όποιον υστερεί στο υπόβαθρο, παρέχουν εκτεταμένη κάλυψη του κεφαλαίου 0 του Sipser.

Υπάρχουν και αρκετά άλλα βιβλία και σημειώσεις στα αγγλικά. Συστήνω τα παρακάτω από τα οποία θα αντλήσουμε υλικό.

  1. Σημειώσεις Jeff Erickson πάνω σε υπολογιστικά μοντέλα
  2. Introduction to Automata Theory, Languages, and Computation των Hopcroft, Motwani, Ullman
  3. Automata, Computability and Complexity: Theory and Applications της Elaine Shi

Το μάθημα έχει έντονο μαθηματικό υπόβαθρο και προϋποθέτει εξοικείωση με βασικές αποδεικτικές τεχνικές. Στις πρώτες διαλέξεις θα καλύψουμε σχετικό εισαγωγικό υλικό το οποίο διδάσκεται στα διακριτά μαθηματικά (HY-118/ΜΑΘ-205) και καθ᾽όλη τη διάρκεια του μαθήματος θα εξασκηθούμε συστηματικά στη διατύπωση και κατασκευή αποδείξεων. Συστήνω το παρακάτω βιβλίο που είναι διαθέσιμο online.

  1. Book of Proof του Richard Hammack

Αξιολόγηση Φοιτητών

Ο τελικός βαθμός θα προκύψει από τα εξής:

  1. Τελική Εξέταση (70%)
  2. Πρόοδος (20%) που θα λάβει χώρα σύντομα μετά τα μέσα Οκτώβρη
  3. Ασκήσεις (10%) με προφορική εξέταση
  4. Προγραμματιστικό bonus σε Lean (5%) με προφορική εξέταση

Σημαντικές επισημάνσεις για τις ασκήσεις:

  • Το ποσοστό που αντιστοιχεί στις ασκήσεις δεν αποτυπώνει καθόλου τη πραγματική δυσκολία τους, και ο λόγος είναι πως πλέον όλες μπορούν να επιλυθούν στην εντέλεια με εργαλεία τεχνητής νοημοσύνης (πχ. GPT Astra 6, pro subscription).
  • Όμως, οι φοιτητές που θα δουλέψουν ουσιαστικά και συστηματικά πάνω στο σετ των προβλημάτων θα μάθουν καλύτερα το υλικό και θα είναι καλά προετοιμασμένοι για την τελική εξέταση.
  • Συνιστώ επίσης σε όλους τους φοιτητές να παρακολουθούν τακτικά τα φροντιστήρια της Παρασκευής και τις άφθονες ώρες γραφείου σε εβδομαδιαία βάση για να συζητούν τις ασκήσεις και το υλικό του μαθήματος.
  • Το παραδοτέο των ασκήσεων οφείλει να είναι γραμμένο σε LaTeX. Μπορείτε να το εγκαταστήσετε στον υπολογιστή σας ή εναλλακτικά και βολικά να χρησιμοποιήσετε το Overleaf.
  • Θα υπάρξει και προφορική εξέταση πάνω στο παραδοτέο των ασκήσεων για όλους ή με τυχαία δειγματοληψία ανάλογα με το πλήθος των ενεργών φοιτητών. Συνεπώς, ο,τι παραδώσετε κατ᾽ελάχιστον να το κατανοείτε.
  • Η ενασχόληση με τη Lean προσφέρει τη δυνατότητα για μπόνους. Δεν αποτελεί προϋπόθεση για να πάρετε άριστα στο μάθημα. Είναι, ωστόσο, μια σύγχρονη και χρήσιμη δεξιότητα που συνδέει τη μαθηματική απόδειξη με τον προγραμματισμό, δίνοντας στο μάθημα μια πιο πρακτική και διαδραστική διάσταση.

Δεοντολογικός Κώδικας

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

A fundamental danger, as we’ve discussed, is that AI can allow students to bypass learning. Equally concerning is that students may internalize a transactional model in which assignments are outputs, teachers are evaluators, peers are optional, and knowledge (or an MIT degree) is an optimizable commodity to be acquired or produced as efficiently as possible.

Such a mental model will not remain confined to the classroom. It will shape how students come to understand work, collaboration, and social responsibility, and they will carry that mindset with them out into the world. However sociable or responsive AI systems become, they cannot substitute for the relationships and practices necessary to grow and mature as a human being.

Η περιορισμένη ενασχόληση με την επίλυση προβλημάτων μπορεί να επηρεάσει ουσιαστικά τη μάθησή σας, χωρίς όμως να έχει δυσανάλογη επίδραση στον τελικό βαθμό, γι’ αυτό οι ασκήσεις αντιστοιχούν στο 10% της αξιολόγησης Απαραίτητη, ωστόσο, προϋπόθεση είναι κάθε εργασία που υποβάλλετε να αποτελεί προϊόν κατανόησης και προσωπικής μελέτης. Για τον λόγο αυτό, μπορεί να ζητηθεί σύντομη προφορική συζήτηση σχετικά με την εργασία σας.

Τέλος, η αντιγραφή κατά τη διάρκεια γραπτής εξέτασης οδηγεί σε άμεσο μηδενισμό του γραπτού. Παρακαλώ μην με φέρει κανείς σε αυτή τη δύσκολη θέση, δεν αξίζει.

Διαλέξεις και Υλικό

Διάλεξη 21/9

Διάλεξη 23/9

Σημείωση: Με το πέρας της 2ης διάλεξης, τελειώσαμε την απόδειξη της μη επιλυσιμότητας του halting προβλήματος, και την πρώτη μας αναγωγή. Στο τέλος ξεκινήσαμε να μιλάμε για τη διαγωνοποίηση ως τεχνική. Από το set ασκήσεων της 2ης διάλεξης, μπορείτε να λύσετε την 1η άσκηση και ολόκληρο το 1ο set.
  • Οι διαφάνειες της 2ης διάλεξης είναι διαθέσιμες εδώ
  • Οι ασκήσεις της 2ης διάλεξης είναι διαθέσιμες εδώ
    • Σχετικό Υλικό
    • Αξίζει να ρίξετε μια ματιά
      • Το αρχικό paper του Cantor (1891)
      • Το βίντεο εδώ είναι high-level αλλά δείχνει πως η διαγωνιοποίηση δεν είναι απλώς ένα τέχνασμα με δεκαδικές αναπτύξεις αλλά ένας γενικός μηχανισμός για την κατασκευή αυτοαναφοράς και για την απόδειξη θεμελιωδών αδυναμιών των υπολογιστικών συστημάτων.

Διάλεξη 28/9

  • Οι διαφάνειες της 3ης διάλεξης είναι διαθέσιμες εδώ
  • Οι ασκήσεις της 3ης διάλεξης είναι διαθέσιμες εδώ
    • Σχετικό Υλικό
      • Υποχρεωτικά: Hammack Κεφ. 4, 5, 6, με έμφαση στις τεχνικές απόδειξης, Κεφ. 12.1–12.2, Κεφ. 14.1–14.2, όπου είναι ουσιαστικά η ιδέα του dovetailing.
      • Ανασκόπηση: Hammack Κεφ. 1, 2, 11, για όποιον νιώθει ότι δεν θυμάται τα Διακριτά.
      • Sipser: Κεφ. 0 ολόκληρο, κυρίως για τη σημειογραφία του βιβλίου.

Φροντιστήρια

Φροντιστήριο 25/9

ΔΕΝ θα γίνουν μαθήματα και φροντιστήρια από τις 10:30 το πρωί έως τις 15:00 το απόγευμα, λόγω της εκδήλωσης Υποδοχής Πρωτοετών 2026 & Reunion τάξεων 1986, 1996 και 2006

Φροντιστήριο 2/10

Υπεύθυνος: Γιάννης Μαλλιωτάκης
Περιεχόμενο: Επίλυση ασκήσεων πάνω στο υλικό των δύο πρώτων εβδομάδων

Χρήσιμο Υλικό

Παρακάτω μπορείτε να βρείτε ενδιαφέρον υλικό που άπτεται του μαθήματος μας για όσους ενδιαφέρονται να πάνε πέρα από τις διαλέξεις.

  1. MIT OCW 18-404 του Michael Sipser είναι εξαιρετικό. Μάλιστα το διαδικτυακό μάθημα του καλύπτει σε μεγάλο βαθμό (αλλά όχι εξ ολοκλήρου) την ύλη του 280.
  2. Το JFLAP είναι ένα δωρεάν εργαλείο για σχεδίαση και προσομοίωση αυτομάτων, γραμματικών και μηχανών Turing. Μια καλή πρακτική είναι να σχεδιάζετε πρώτα τα αυτόματα ή τις μηχανές Turing σε χαρτί και κατόπιν να τα υλοποιείτε στο JFLAP. Το εργαλείο βοηθά στον έλεγχο της ιδέας, δεν υποκαθιστά την απόδειξη ορθότητας.
  3. Για τα κεφάλαια της πολυπλοκότητας, χρήσιμη συμπληρωματική αναφορά είναι το Computational Complexity του Christos Papadimitriou. Περισσότερα θα δούμε και στο ΗΥ 380, το εαρινό εξάμηνο.
  4. Το RegexOne προσφέρει μια σύντομη, διαδραστική εισαγωγή στις κανονικές εκφράσεις — μια πολύ πρακτική εφαρμογή των κανονικών γλωσσών.
  5. Το Regular Expressions 101 επιτρέπει να πειραματιστείτε με κανονικές εκφράσεις και να δείτε βήμα-βήμα πώς αναγνωρίζεται ένα κείμενο.
  6. Το Complexity Zoo είναι μια εγκυκλοπαιδική πηγή για κλάσεις πολυπλοκότητας, όπως P, NP, PSPACE και EXP. Είναι ιδιαίτερα χρήσιμο αφού καλυφθούν οι βασικές έννοιες του μαθήματος.
  7. Στο CS Theory Stack Exchange μπορείτε να βρείτε ενδιαφέρουσες συζητήσεις και διευκρινίσεις για θέματα θεωρίας υπολογισμού. Προσπαθήστε πρώτα να λύνετε μόνοι σας τις ασκήσεις.
  8. Για όσους θέλουν να εμβαθύνουν στην τυπική επαλήθευση και στη Lean, το Theorem Proving in Lean είναι το επίσημο εισαγωγικό εγχειρίδιο.
  9. Η τεκμηρίωση του Mathlib είναι χρήσιμη ως αναφορά, όταν αρχίσουμε να γράφουμε πιο ουσιαστικές αποδείξεις στη Lean.
  10. Το ProofWiki περιέχει παραδείγματα και οργανωμένες αποδείξεις σε θέματα διακριτών μαθηματικών και λογικής.
  11. Η πλατφόρμα Open Logic Project προσφέρει δωρεάν σημειώσεις για προτασιακή και κατηγορηματική λογική, αποδείξεις και θεωρία μοντέλων.
  12. Για σύντομη επανάληψη βασικών διακριτών μαθηματικών, το MIT Mathematics for Computer Science είναι ιδιαίτερα χρήσιμο.
  13. Σημειώσεις από Stanford και το 15-453 Formal Languages, Automata, and Computation από CMU

LEAN

Θα χρησιμοποιήσουμε τη γλώσσα Lean σε επιλεγμένα σημεία του μαθήματος, με στόχο να εξοικειωθούμε με τη διατύπωση και την αυστηρή απόδειξη μαθηματικών προτάσεων. Η Lean θα λειτουργήσει ως συμπληρωματικό εργαλείο για την κατανόηση βασικών εννοιών της λογικής, των αποδείξεων και της Θεωρίας Υπολογισμού. Δεν απαιτείται προηγούμενη εμπειρία με τη Lean.

Στην εποχή της Τεχνητής Νοημοσύνης, εργαλεία όπως η Lean αποκτούν ιδιαίτερη σημασία, καθώς επιτρέπουν να ελέγχουμε μηχανικά την ορθότητα μαθηματικών συλλογισμών και αποδείξεων, συμπεριλαμβανομένων εκείνων που παράγονται με τη βοήθεια συστημάτων ΤΝ.

Μπορείτε:

  • να ρίξετε μια καλή ματιά στο εξής paper του Jeremy Avigad “Mathematicians in the Age of AI“
  • να δείτε μια εισαγωγή στην Lean από τον Leo De Moura ο οποίος είναι ο δημιουργός της.