Υπολογιστική Πολυπλοκότητα

Μάθημα θεωρίας του παλαιού προγράμματος σπουδών: μηχανές Turing, διαγνωσιμότητα, αναγωγές και κλάσεις πολυπλοκότητας (P, NP, co-NP, NP-πληρότητα). Δεν έχει προγραμματισμό — δουλεύεις με ορισμούς, σχεδίαση μηχανών, αποδείξεις μη διαγνωσιμότητας και αποδείξεις NP-πληρότητας. Καταργήθηκε και το αντικείμενό του καλύπτεται πλέον από το «Θεωρία Υπολογισμού και Πολυπλοκότητα».

Θέματα ⬇ Κατέβασε για AI

Με μια ματιά

Κωδικός	Δεν υπάρχει — μάθημα του παλαιού προγράμματος (ο κατάλογος 2025-26 δεν το περιλαμβάνει)
Πρόγραμμα	Παλαιό πρόγραμμα σπουδών· συγχωνεύτηκε στο νέο Discord 2025-02 (διαθέσιμο στο πλήρες πακέτο)
ECTS	Δεν βρέθηκαν πληροφορίες.
Ώρες / εβδομάδα	Δεν βρέθηκαν πληροφορίες.
Τομέας	Δεν βρέθηκαν πληροφορίες.
Διδάσκων (έως 2025)	Κατά φοιτητές, από το εαρινό 2021 το μάθημα το είχε ο κ. Τσίχλας Discord 2022-08 (διαθέσιμο στο πλήρες πακέτο)· το 2025 φοιτητές ρωτούν αν άλλαξε χέρια Discord 2025-05 (διαθέσιμο στο πλήρες πακέτο)
Αξιολόγηση	Τελική γραπτή, κάποιες χρονιές με bonus ασκήσεις ή quiz Discord 2023-10 (διαθέσιμο στο πλήρες πακέτο)
Διάρκεια εξέτασης	2 ώρες 30 λεπτά (2022–2026) Εξετάσεις 2025-06
Επιτρεπόμενο υλικό	Μία χειρόγραφη κόλλα Α4 με σημειώσεις Discord 2023-09 (διαθέσιμο στο πλήρες πακέτο)

Τι θα μάθεις

• Μηχανές Turing: τυπικός ορισμός, αιτιοκρατικές και ανταιτιοκρατικές ΤΜ, διαγνώστες, η γλώσσα και η συμπεριφορά τερματισμού μιας μηχανής, ισοδυναμία μοντέλων (ταινία άπειρη προς μία ή δύο κατευθύνσεις, κυκλική ΤΜ) Εξετάσεις 2025-06, Εξετάσεις 2026-06.
• Υπολογισιμότητα και μη διαγνωσιμότητα: ΑΠΟΔΟΧΗ_TM, πρόβλημα Τερματισμού, ΚΕΝΟΤΗΤΑ_TM, αλγοριθμικές αναγωγές και διάκριση διαγνώσιμης / αναγνωρίσιμης / συμπληρωματικά αναγνωρίσιμης γλώσσας Εξετάσεις 2026-06, Εξετάσεις 2022-08-a.
• Αναγωγές και NP-πληρότητα: SAT/3SAT, ΚΛΙΚΑ, ανεξάρτητο σύνολο, k-χρωματισμός γραφημάτων, knapsack και προβλήματα δρομολόγησης· γιατί το 2SAT ανήκει στο P Εξετάσεις 2025-06, Εξετάσεις 2022-08-a.
• Κλάσεις πολυπλοκότητας: P, NP, co-P, co-NP, NPC, co-NPC, PSpace, TIME, οι μεταξύ τους σχέσεις και η κλειστότητα κλάσεων (P ως προς συμπλήρωμα, NP ως προς ένωση) Εξετάσεις 2026-01, Εξετάσεις 2025-06.
• Έννοιες και ερωτήματα «κρίσης»: θέση Church-Turing, μεταβατικότητα των αναγωγών, Σωστό/Λάθος πάνω σε όλη την ύλη Εξετάσεις 2026-06.
• Βιβλίο αναφοράς: Sipser, «Εισαγωγή στη Θεωρία Υπολογισμού» — από εκεί προέρχονται οι ασκήσεις στις διαλέξεις Discord 2022-06 (διαθέσιμο στο πλήρες πακέτο).

Αντιστοιχία με νέο πρόγραμμα

• Κατά φοιτητή (2023), ο διδάσκων είχε πει σε μάθημα ότι η Υπολογιστική Πολυπλοκότητα θα υπάρχει μέχρι τον Σεπτέμβριο 2024 και μετά θα συγχωνευθεί με τη Θεωρία Υπολογισμού Discord 2023-08 (διαθέσιμο στο πλήρες πακέτο). Τον Ιούνιο 2026, σε ερώτηση «ποιος το κάνει;», φοιτητής απαντά «κανείς, έχει καταργηθεί» Discord 2026-06 (διαθέσιμο στο πλήρες πακέτο).
• Στο νέο πρόγραμμα (2025-26) το αντικείμενο καλύπτεται από το υποχρεωτικό μάθημα «Θεωρία Υπολογισμού και Πολυπλοκότητα» του 6ου εξαμήνου (6 ECTS, τομέας ΕΘ) Κατάλογος. Πρόκειται για μεγαλύτερο μάθημα που ενσωματώνει και την παλιά «Θεωρία Υπολογισμού» (αυτόματα, κανονικές εκφράσεις, γραμματικές).
• Για φοιτητές που χρωστούν το παλιό μάθημα: το 2024-25 συζητήθηκαν μεταβατικές διατάξεις Discord 2024-11 (διαθέσιμο στο πλήρες πακέτο) και ζητήματα δήλωσης/βαθμών στο Progress Discord 2024-06 (διαθέσιμο στο πλήρες πακέτο). Δεν βρέθηκαν επίσημες λεπτομέρειες για τη διαδικασία.

Εξετάσεις

Σύνολο 13 συνεδρίες, με τις πιο πρόσφατες γραμμένες και χωρίς λύσεις· λεπτομέρειες στο Εξετάσεις και στις ανακλήσεις από το Discord.

• Δομή (2025–2026): 5 θέματα, συνήθως 2 μονάδες το καθένα, σε 2 ώρες 30 λεπτά. Τυπικά: (1) δίνεται ΤΜ — «είναι διαγνώστης; ποια γλώσσα αναγνωρίζει;», (2) αναγωγή για NP-πληρότητα, (3) μη διαγνωσιμότητα γλώσσας με αναγωγή από την ΑΠΟΔΟΧΗ_TM, (4) κλειστότητα κλάσεων ή σχηματική ιεραρχία, (5) Σωστό/Λάθος με αρνητική βαθμολόγηση Εξετάσεις 2025-06, Εξετάσεις 2026-06.
• Παλαιότερες μορφές: το 2020-21 η εξέταση ήταν ηλεκτρονική, πολλαπλής επιλογής και συμπλήρωσης κενών, με Zoom/ταυτοποίηση και αρνητική βαθμολόγηση Εξετάσεις 2021-06-mcq, Discord 2021-06 (διαθέσιμο στο πλήρες πακέτο). Από τον Φεβρουάριο 2022 και μετά είναι δια ζώσης γραπτή με ανοιχτά θέματα Εξετάσεις 2022-08-a.
• Επαναλαμβανόμενα θέματα: φοιτητές αναφέρουν ότι οι τύποι ασκήσεων είναι «ίδιοι τα τελευταία 3 χρόνια» και ότι ο διδάσκων ανεβάζει παλιά θέματα με λύσεις στο eClass Discord 2025-06 (διαθέσιμο στο πλήρες πακέτο). «Safe bet» θεωρείται το θέμα με τις σχέσεις/σύνολα γλωσσών Discord 2025-09 (διαθέσιμο στο πλήρες πακέτο).
• Επιτρεπόμενο υλικό: μία χειρόγραφη κόλλα Α4 μπρος-πίσω Discord 2023-09 (διαθέσιμο στο πλήρες πακέτο), Discord 2022-06 (διαθέσιμο στο πλήρες πακέτο). Το 2025 φοιτητής γράφει «μια κόλλα επιτρέπεται», ενώ άλλοι σχεδίαζαν να πάρουν 3-4 κόλλες — μην το θεωρείς δεδομένο Discord 2025-05 (διαθέσιμο στο πλήρες πακέτο), Discord 2025-06 (διαθέσιμο στο πλήρες πακέτο).
• Λύσεις: υπάρχουν για 2020-06, 2021-06, 2023-01, 2023-05 (community) και για 2021-06-mcq, 2021-09 (ai-unverified — πρέπει να λυθούν ξανά πριν τις εμπιστευτείς)· τα θέματα 2024-09 έως 2026-06 δεν έχουν λύσεις Εξετάσεις.
• Παγίδες κατά φοιτητές: η βάση και το επιτρεπόμενο υλικό άλλαζαν και προκαλούσαν σύγχυση (αναφορές για βάση 4 και 4,25 στο ίδιο διάστημα) Discord 2022-06 (διαθέσιμο στο πλήρες πακέτο), Discord 2024-06 (διαθέσιμο στο πλήρες πακέτο). Ο διδάσκων «δεν αλλάζει σχεδόν ποτέ βαθμούς» Discord 2025-06 (διαθέσιμο στο πλήρες πακέτο), και το Σωστό/Λάθος έχει αρνητική βαθμολόγηση, οπότε οι τυχαίες απαντήσεις ρισκάρουν Εξετάσεις 2026-06. Δεν υπάρχει πρόοδος· κατά φοιτητές μόνο τελική εξέταση, κάποιες χρονιές με bonus Discord 2023-10 (διαθέσιμο στο πλήρες πακέτο), Discord 2022-03 (διαθέσιμο στο πλήρες πακέτο).

Υλικό & τρόπος μελέτης

• Δεν υπάρχει φάκελος eclass/ στο αποθετήριο· το υλικό βρίσκεται σε other/ και Previous Exams/.
• Βιβλίο: Sipser — Εισαγωγή στη Θεωρία Υπολογισμού (διαθέσιμο στο πλήρες πακέτο). Φοιτητής (2025) προτείνει «μια καλή ανάγνωση του βιβλίου» και μετά τα παλιά θέματα Discord 2025-02 (διαθέσιμο στο πλήρες πακέτο).
• Σημειώσεις φοιτητή της εαρινής περιόδου 2021 (14 αρχεία): π.χ. Computational Complexity 2021-03-03 (διαθέσιμο στο πλήρες πακέτο).
• Συγκεντρωτικά θέματα/λύσεις: Σύνολο ύλης και θεμάτων (διαθέσιμο στο πλήρες πακέτο), Θέματα με λύσεις 2022 (διαθέσιμο στο πλήρες πακέτο), Σημειώσεις CA (διαθέσιμο στο πλήρες πακέτο).
• Ασκήσεις πάνω σε μηχανές Turing: Παραδείγματα σε ΤΜ (διαθέσιμο στο πλήρες πακέτο), Ιδιότητες γλωσσών (διαθέσιμο στο πλήρες πακέτο).
• Παλιά θέματα με μεταγραφές: Εξετάσεις και ανακλήσεις. Φοιτητής (2024) έγραψε ότι όποιος διάβαζε από τα προηγούμενα θέματα περνούσε Discord 2024-06 (διαθέσιμο στο πλήρες πακέτο).
• Δεν βρέθηκαν διαφάνειες του μαθήματος στο αποθετήριο, αν και φοιτητές τις αναφέρουν ως βασικό υλικό Discord 2021-06 (διαθέσιμο στο πλήρες πακέτο). Επίσης δεν βρέθηκαν βίντεο· το 2022 φοιτητές ανέφεραν ότι τα βίντεο στο ιστολόγιο του eClass δεν έπαιζαν Discord 2022-08 (διαθέσιμο στο πλήρες πακέτο).

Πηγές & αξιοπιστία

• Discord: 1398 μηνύματα σε 13 περιόδους (2021-01 έως 2026-09), με τις περισσότερες συζητήσεις στο 2020-2023 και λίγες τα τελευταία χρόνια Discord (διαθέσιμο στο πλήρες πακέτο). Είναι ανεπίσημες γνώμες φοιτητών, όχι ανακοινώσεις.
• Εξετάσεις: 13 συνεδρίες· 6 με αρχείο λύσεων, από τις οποίες δύο ai-unverified. Τα θέματα 2024-09 έως 2026-06 είναι χωρίς λύσεις και αρκετές μεταγραφές είναι μερικές ή με δυσανάγνωστα σημεία Εξετάσεις, Εξετάσεις 2026-01.
• Δεν υπάρχει εγγραφή στον κατάλογο 2025-26 ούτε επίσημο περίγραμμα, άρα ECTS, ώρες, τομέας και διδάσκων του παλιού μαθήματος δεν επιβεβαιώνονται από επίσημη πηγή.
• Δεν βρέθηκαν πληροφορίες για ποσοστά επιτυχίας, κατανομή βαθμών ή επίσημες λύσεις. Το υλικό σε other/ είναι ανεπίσημο (σημειώσεις φοιτητών, σαρωμένα αρχεία).

Αρχεία του φακέλου

Παράγεται αυτόματα από tools/render_readmes.py — αλλαγές εδώ χάνονται στην επόμενη εκτέλεση.

Φάκελος	Περιεχόμενο
discord/ (διαθέσιμο στο πλήρες πακέτο)	13 περίοδοι συζητήσεων Discord · 1398 μηνύματα
Previous Exams/	13 συνεδρίες εξετάσεων · 6 με αρχείο λύσεων · 36 πρωτότυπα αρχεία (33 εικόνες) · 3 κείμενα (sidecar) · 35 μεταγραφές · ανακλήσεις από Discord
other/	51 αρχεία (19 εικόνες) · 24 κείμενα (sidecar) · 1 μεταγραφές