Πληροφορίες
Διαλέξεις
Πότε: Δευτέρα και Τετάρτη, 13:00–15:00
Πού: Αμφιθέατρο Στέλιος Ορφανουδάκης (ΑΜΦ ΣΟ)
Διδάσκων: Χαράλαμπος Ε. Τσουρακάκης
Email: tsourakakis@csd.uoc.gr
Φροντιστήριο
Πότε: Παρασκευή, 13:00–15:00
Πού: Αίθουσα Α113
Το φροντιστήριο διδάσκεται σε εβδομαδιαία βάση από τον/την εκάστοτε βοηθό.
Είναι μια εξαιρετική ευκαιρία να λύνετε προβλήματα μαζί με τους βοηθούς, σε πιο ήπιο ρυθμό από τη διάλεξη, με περισσότερο χρόνο για συζήτηση και επίλυση αποριών, ώστε να κατανοήσετε καλύτερα την ύλη.
Βοηθοί & Ώρες γραφείου
Βοηθοί
| Όνομα | Ιδιότητα | |
|---|---|---|
| Μαλλιωτάκης Ιωάννης | PhD | csdp1352@csd.uoc.gr |
| Ξανθάκης Γεώργιος | PhD | csdp1246@csd.uoc.gr |
| Noah Wahl | PhD | csdp1380@csd.uoc.gr |
| Πλεξουσάκης Ιωάννης | MSc | tem3217@tem.uoc.gr |
| Κροκίδα Άννα-Ολυμπία | MSc | csd5192@csd.uoc.gr |
| Μπαλωτής Εμμανουήλ-Παναγιώτης | MSc | csdp1498@csd.uoc.gr |
Ώρες γραφείου
Οι ώρες γραφείου είναι διαθέσιμες για ερωτήσεις, συζήτηση της ύλης και βοήθεια με τις ασκήσεις.
| Διδάσκων / Βοηθός | Πότε | Πού |
|---|---|---|
| Χαράλαμπος Ε. Τσουρακάκης |
Δευτέρα, Τετάρτη 15:00–16:00 |
Γραφείο Β303 |
| Γιάννης Μαλλιωτάκης (PhD) |
Δευτέρα 11:00–12:00 |
Διαδικτυακά
Δείτε την ανακοίνωση στο eLearn |
| Γιώργος Ξανθάκης (PhD) |
Τετάρτη 10:00–11:00 |
Διαδικτυακά
Δείτε την ανακοίνωση στο eLearn |
|
Noah Wahl (PhD)
English only |
Τρίτη 12:00–13:00 |
Διαδικτυακά
Δείτε την ανακοίνωση στο eLearn |
| Ιωάννης Πλεξουσάκης (MSc) |
Πέμπτη 15:00–16:00 |
Δια ζώσης Β210 |
| Άννα-Ολυμπιάς Κροκιδά (MSc) |
Πέμπτη 13:00–14:00 |
Δια ζώσης Β210 |
| Μάνος Μπαλωτής (MSc) |
Τρίτη 12:00–13:00 |
Δια ζώσης Β210 |
Περίγραμμα μαθήματος (Syllabus)
Github
Βιβλία & Βοηθητικό Υλικό
Οποιοδήποτε από τα παρακάτω συγγράμματα μπορεί να χρησιμοποιηθεί ως βασικό βοήθημα. Ωστόσο, στο μάθημα θα καλύψουμε και ύλη πέρα από αυτή που περιλαμβάνεται στα συγγράμματα.
Βασικά συγγράμματα
Το βασικό προτεινόμενο σύγγραμμα του μαθήματος, από τις Πανεπιστημιακές Εκδόσεις Κρήτης. Υπάρχουν άφθονα αντίγραφα διαθέσιμα στη βιβλιοθήκη.
Τα Κεφάλαια 7–10 εντάσσονται στην ύλη μας, αλλά καλύπτουν μόνο ένα μέρος του συνολικού περιεχομένου του μαθήματος.
Τα αρχικά κεφάλαια είναι ιδιαίτερα χρήσιμα για όποιον χρειάζεται ενίσχυση στο μαθηματικό υπόβαθρο και παρέχουν εκτεταμένη κάλυψη της ύλης του Κεφαλαίου 0 του Sipser.
Πρόσθετο υλικό στα αγγλικά
Θα αντλήσουμε επιπλέον υλικό από τις παρακάτω σημειώσεις και συγγράμματα.
| Συγγραφέας | Υλικό |
|---|---|
| Jeff Erickson | Σημειώσεις πάνω σε υπολογιστικά μοντέλα |
| Hopcroft, Motwani & Ullman | Introduction to Automata Theory, Languages, and Computation |
| Elaine Shi | Automata, Computability and Complexity: Theory and Applications |
Μαθηματικό υπόβαθρο & αποδείξεις
Το μάθημα έχει έντονο μαθηματικό υπόβαθρο και προϋποθέτει εξοικείωση με βασικές αποδεικτικές τεχνικές.
Στις πρώτες διαλέξεις θα καλύψουμε σχετικό εισαγωγικό υλικό το οποίο διδάσκεται στα Διακριτά Μαθηματικά (ΗΥ-118 / ΜΑΘ-205). Καθ’ όλη τη διάρκεια του μαθήματος θα εξασκηθούμε συστηματικά στη διατύπωση και κατασκευή αποδείξεων.
Book of Proof — Richard Hammack (PDF)Αξιολόγηση Φοιτητών
Ο τελικός βαθμός θα προκύψει από τα παρακάτω:
Σημαντικές επισημάνσεις για τις ασκήσεις
Το ποσοστό που αντιστοιχεί στις ασκήσεις δεν αποτυπώνει την πραγματική δυσκολία τους. Πλέον, όλες μπορούν να επιλυθούν στην εντέλεια με εργαλεία τεχνητής νοημοσύνης (π.χ. GPT Astra 6, pro subscription).
Ωστόσο, οι φοιτητές που θα δουλέψουν ουσιαστικά και συστηματικά πάνω στο σετ των προβλημάτων θα κατανοήσουν καλύτερα το υλικό και θα είναι πολύ καλύτερα προετοιμασμένοι για την τελική εξέταση.
Συνιστώ επίσης σε όλους τους φοιτητές να παρακολουθούν τακτικά τα φροντιστήρια της Παρασκευής και να αξιοποιούν τις ώρες γραφείου σε εβδομαδιαία βάση για να συζητούν τις ασκήσεις και το υλικό του μαθήματος.
Προαιρετικό bonus — Lean (+5%)
Η ενασχόληση με τη Lean προσφέρει τη δυνατότητα για bonus και συνοδεύεται από προφορική εξέταση.
Δεν αποτελεί προϋπόθεση για να πάρετε άριστα στο μάθημα. Είναι, ωστόσο, μια σύγχρονη και χρήσιμη δεξιότητα που συνδέει τη μαθηματική απόδειξη με τον προγραμματισμό, δίνοντας στο μάθημα μια πιο πρακτική και διαδραστική διάσταση.
Δεοντολογικός Κώδικας
Συνεργασία & συζήτηση
Η συνεργασία και η συζήτηση αποτελούν θεμελιώδη στοιχεία για τη γέννηση ιδεών στην ακαδημαϊκή κοινότητα. Σας ενθαρρύνουμε να συνεργάζεστε με τους συμφοιτητές σας για την αναζήτηση ιδεών και λύσεων στις ασκήσεις.
Είναι, όμως, σημαντικό να αναγνωρίζετε τον τρόπο και την πηγή της βοήθειας που λάβατε, για λόγους ακαδημαϊκής ακεραιότητας, ηθικής και αξιοπιστίας.
Χρήση Τεχνητής Νοημοσύνης
AI & Εκπαίδευση — μια χρήσιμη οπτική από το MIT
Αξίζει να διαβάσετε τον οδηγό του MIT σχετικά με την 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% της αξιολόγησης.
Απαραίτητη προϋπόθεση είναι κάθε εργασία που υποβάλλετε να αποτελεί προϊόν κατανόησης και προσωπικής μελέτης. Για τον λόγο αυτό, μπορεί να ζητηθεί σύντομη προφορική συζήτηση σχετικά με την εργασία σας.
Η αντιγραφή κατά τη διάρκεια γραπτής εξέτασης οδηγεί σε άμεσο μηδενισμό του γραπτού. Παρακαλώ μην με φέρει κανείς σε αυτή τη δύσκολη θέση· δεν αξίζει.
Διαλέξεις και Υλικό
1η διάλεξη 21/9
Οι διαφάνειες αποτελούν το βασικό υλικό μελέτης της διάλεξης.
Σχετικό υλικό
Αξίζει να ρίξετε μια ματιά — Προαιρετικά
Ξεκινήστε από τους συνδέσμους που περιέχονται στις διαφάνειες και εξερευνήστε όσα από τα παρακάτω σας κινήσουν το ενδιαφέρον.
Math’s Fundamental Flaw — Veritasium
Ένα βίντεο που ξεκινά από το παράδοξο του Russell και φτάνει μέχρι το θεώρημα μη πληρότητας του Κουρτ Γκέντελ.
Thoughts from the forest floor: a review of cognition in the slime mould Physarum polycephalum
Μια επισκόπηση του Physarum polycephalum και των γνωστικών του ικανοτήτων.
Claude, Lean και το τελευταίο θεώρημα του Fermat
Δείτε επίσης το συνοδευτικό PDF με περισσότερες λεπτομέρειες.
Η αντιστοιχία Curry–Howard — Υλικό ΗΥ546
Για μελλοντική μελέτη: στο μάθημα ΗΥ546 μπορείτε να μάθετε περισσότερα για την αντιστοιχία Curry–Howard.
The Early History of Automated Deduction
Συστήματα αρίθμησης και αριθμητικές αναπαραστάσεις
Εξερευνήστε τα συστήματα αρίθμησης στη Wikipedia και ιστορικά στοιχεία για τις αριθμητικές αναπαραστάσεις.
2η διάλεξη 23/9
Σχετικό υλικό
Αξίζει να ρίξετε μια ματιά
Το αρχικό άρθρο του Cantor (1891)
Βίντεο: η διαγωνοποίηση ως γενική τεχνική
Μια παρουσίαση σε υψηλό επίπεδο που δείχνει ότι η διαγωνοποίηση δεν είναι απλώς ένα τέχνασμα με δεκαδικές αναπτύξεις, αλλά ένας γενικός μηχανισμός για την κατασκευή αυτοαναφοράς και την απόδειξη θεμελιωδών αδυναμιών των υπολογιστικών συστημάτων.
Σύνοψη 1ης εβδομάδας
Με το πέρας της 1ης εβδομάδας, ολοκληρώσαμε την απόδειξη της μη επιλυσιμότητας του προβλήματος τερματισμού (halting problem) και την πρώτη μας αναγωγή. Στο τέλος, ξεκινήσαμε να μιλάμε για τη διαγωνοποίηση ως τεχνική.
Μπορείτε να λύσετε ολόκληρο το 1ο σετ ασκήσεων, καθώς και την 1η άσκηση από το σετ ασκήσεων της 2ης διάλεξης.
3η διάλεξη 28/9
Σχετικό υλικό
Υποχρεωτικά — Hammack
Κεφάλαια 4, 5 και 6, με έμφαση στις τεχνικές απόδειξης.
Ενότητες 12.1–12.2 και 14.1–14.2, όπου εμφανίζεται ουσιαστικά η ιδέα του dovetailing.
Ανασκόπηση — Hammack
Κεφάλαια 1, 2 και 11, για όποιον χρειάζεται μια επανάληψη στις βασικές έννοιες των Διακριτών Μαθηματικών.
Sipser — Κεφάλαιο 0
Ολόκληρο το Κεφάλαιο 0, κυρίως για εξοικείωση με τη σημειογραφία του βιβλίου.
4η διάλεξη 30/9
Σχετικό υλικό
Υποχρεωτική μελέτη
Hopcroft, Motwani, Ullman: Κεφάλαιο 1.
Hammack: Κεφάλαιο 10.
Σύνοψη 2ης εβδομάδας
Με το πέρας της 2ης εβδομάδας, κάναμε μια ανασκόπηση υλικού από τα Διακριτά Μαθηματικά και είδαμε νέες τεχνικές όπως η διαγωνοποίηση, το dovetailing, καθώς και νέες μορφές της επαγωγικής μεθόδου.
Είστε σε θέση να λύσετε όλες τις ασκήσεις που σας έχουν δοθεί, εκτός από την άσκηση 3 από το σετ 4 (“Δύο ακολουθίες, μία επαγωγική πρόταση”). Θα τελειώσω την αμοιβαία επαγωγή την επόμενη εβδομάδα.
5η διάλεξη — 5/10
Συμβολοσειρές
Σχετικό υλικό
Υποχρεωτική μελέτη — Jeff Erickson
Κεφάλαιο 1 — Strings από τις σημειώσεις Models of Computation του Jeff Erickson.
Το κεφάλαιο καλύπτει τις βασικές έννοιες για συμβολοσειρές, αναδρομικούς ορισμούς και επαγωγικές αποδείξεις πάνω σε συμβολοσειρές.
Jeff Erickson — Models of Computation (PDF)6η και 7η διάλεξη – 7/10 και 12/10
Γλώσσες
Σχετικό υλικό
Υποχρεωτική μελέτη — Jeff Erickson
Κεφάλαιο 2 — Languages από τις σημειώσεις Models of Computation του Jeff Erickson.
Το κεφάλαιο αποτελεί το βασικό συμπληρωματικό υλικό για τη μελέτη των γλωσσών και των πράξεων πάνω σε γλώσσες.
Jeff Erickson — Models of Computation (PDF)8η Διάλεξη — 15/10
Πεπερασμένα Αυτόματα — Μέρος Ι
Οι ασκήσεις είναι κοινές για την 7η και την 8η διάλεξη.
Σχετικό υλικό
Υποχρεωτική μελέτη — Sipser
Michael Sipser — Εισαγωγή στη Θεωρία Υπολογισμού
Κεφάλαιο 1, έως και την ενότητα 1.3 (συμπεριλαμβανομένης).
Προαιρετικό υλικό — Για περαιτέρω εμβάθυνση
Από το βιβλίο Beautiful Code (O’Reilly, 2007).
Μια κατασκευαστική μέθοδος μετατροπής κανονικών εκφράσεων σε μη ντετερμινιστικά πεπερασμένα αυτόματα (ε-NFA).
Φροντιστήρια
Εδώ θα αναρτάται το υλικό των εβδομαδιαίων φροντιστηρίων. Επιλέξτε την αντίστοιχη ημερομηνία για περισσότερες πληροφορίες.
16/10 — Φροντιστήριο
9/10 — Φροντιστήριο
2/10 — Φροντιστήριο
Διδάσκων: Γιάννης Μαλλιωτάκης
Διαφάνειες Φροντιστηρίου (PDF)25/9 — Αναστολή μαθημάτων και φροντιστηρίων
Στις 25/9, δεν θα γίνουν μαθήματα και φροντιστήρια από τις 10:30 έως τις 15:00 , λόγω της εκδήλωσης Υποδοχής Πρωτοετών 2026 & Reunion τάξεων 1986, 1996 και 2006 .
Χρήσιμο Υλικό
Παρακάτω μπορείτε να βρείτε ενδιαφέρον συμπληρωματικό υλικό σχετικό με το μάθημα, για όσους θέλουν να εμβαθύνουν πέρα από τις διαλέξεις.
Διαλέξεις, μαθήματα & επανάληψη
Το μάθημα του Michael Sipser είναι εξαιρετική συμπληρωματική πηγή. Το διαδικτυακό μάθημα καλύπτει σε μεγάλο βαθμό, αλλά όχι εξ ολοκλήρου, την ύλη του ΗΥ-280.
Ιδιαίτερα χρήσιμο για σύντομη επανάληψη βασικών διακριτών μαθηματικών.
Σημειώσεις και υλικό πάνω σε μαθηματικές βάσεις, λογική και θεωρία υπολογισμού.
Συμπληρωματικό υλικό για τυπικές γλώσσες, αυτόματα και υπολογισιμότητα.
Διαδραστικά εργαλεία — Αυτόματα & Regular Expressions
Δωρεάν εργαλείο για σχεδίαση και προσομοίωση αυτομάτων, γραμματικών και μηχανών Turing.
Καλή πρακτική είναι να σχεδιάζετε πρώτα το αυτόματο ή τη μηχανή Turing σε χαρτί και κατόπιν να το υλοποιείτε στο JFLAP. Το εργαλείο βοηθά στον έλεγχο της ιδέας· δεν υποκαθιστά την απόδειξη ορθότητας.
Σύντομη και διαδραστική εισαγωγή στις κανονικές εκφράσεις — μια πολύ πρακτική εφαρμογή των κανονικών γλωσσών.
Πειραματιστείτε με κανονικές εκφράσεις και δείτε βήμα προς βήμα πώς γίνεται η αναγνώριση ενός κειμένου.
Lean, τυπική επαλήθευση & αποδείξεις
Το επίσημο εισαγωγικό εγχειρίδιο για όσους θέλουν να εμβαθύνουν στην τυπική επαλήθευση και στη Lean.
Χρήσιμη ως αναφορά όταν αρχίσουμε να γράφουμε πιο ουσιαστικές αποδείξεις στη Lean.
Παραδείγματα και οργανωμένες αποδείξεις σε θέματα διακριτών μαθηματικών και λογικής.
Δωρεάν σημειώσεις για προτασιακή και κατηγορηματική λογική, αποδείξεις και θεωρία μοντέλων.
Για περαιτέρω εμβάθυνση
Χρήσιμη συμπληρωματική αναφορά για τα κεφάλαια της υπολογιστικής πολυπλοκότητας. Περισσότερα θα δούμε και στο ΗΥ-380 το εαρινό εξάμηνο.
Εγκυκλοπαιδική πηγή για κλάσεις πολυπλοκότητας όπως P, NP, PSPACE και EXP. Είναι ιδιαίτερα χρήσιμη αφού καλυφθούν οι βασικές έννοιες του μαθήματος.
Ενδιαφέρουσες συζητήσεις και διευκρινίσεις για θέματα θεωρίας υπολογισμού. Προσπαθήστε πρώτα να λύνετε μόνοι σας τις ασκήσεις.
Lean — Τυπικές Αποδείξεις & Θεωρία Υπολογισμού
Θα χρησιμοποιήσουμε τη γλώσσα Lean σε επιλεγμένα σημεία του μαθήματος, με στόχο να εξοικειωθούμε με τη διατύπωση και την αυστηρή απόδειξη μαθηματικών προτάσεων.
Η Lean θα λειτουργήσει ως συμπληρωματικό εργαλείο για την κατανόηση βασικών εννοιών της λογικής, των αποδείξεων και της Θεωρίας Υπολογισμού.
Γιατί Lean στην εποχή της Τεχνητής Νοημοσύνης;
Στην εποχή της Τεχνητής Νοημοσύνης, εργαλεία όπως η Lean αποκτούν ιδιαίτερη σημασία, καθώς επιτρέπουν να ελέγχουμε μηχανικά την ορθότητα μαθηματικών συλλογισμών και αποδείξεων, συμπεριλαμβανομένων εκείνων που παράγονται με τη βοήθεια συστημάτων ΤΝ.
Για μια ευρύτερη οπτική, αξίζει να διαβάσετε το paper του Jeremy Avigad Mathematicians in the Age of AI.
Ξεκινήστε από εδώ
Βίντεο & διαλέξεις
Μια εισαγωγή από τον δημιουργό της Lean.
Η θεμελιώδης σύνδεση μεταξύ προτάσεων και τύπων, και μεταξύ αποδείξεων και προγραμμάτων. Δείτε επίσης το βίντεο Propositions as Types.
Προτεινόμενη YouTube playlist από το Dipartimento di Matematica του UNIBO.
Για όσους θέλουν να εμβαθύνουν περισσότερο. Για τους σκοπούς του ΗΥ-280, τα δύο πρώτα βίντεο είναι αρκετά.
Βιβλία & υλικό αναφοράς
Εισαγωγή στη λογική, στους τύπους, στις tactics και στη συγγραφή τυπικών αποδείξεων.
Για να δείτε πώς συνηθισμένα μαθηματικά μεταφράζονται σε μηχανικά επαληθεύσιμες αποδείξεις.
Για όσους θέλουν να εμβαθύνουν
Η κοινότητα της Lean, όπου μπορείτε να αναζητάτε τεχνικές διευκρινίσεις σχετικά με τη γλώσσα και τη βιβλιοθήκη Mathlib.
Αναφορά του Terence Tao. Ενδιαφέρον για όσους είναι ήδη εξοικειωμένοι με τον προγραμματισμό και θέλουν να εξερευνήσουν περισσότερο το οικοσύστημα της Lean.
