https://eclass.uoa.gr/courses/MATH830/ΑνακοινώσειςTue, 23 Jun 2026 00:58:15 +0300elhttps://eclass.uoa.gr/modules/announcements/index.php?an_id=661556&course=MATH830<p>Καλησπέρα σε όλα,</p> <p>Οι βαθμοί της εξέτασης στις 22/6 είναι αναρτημένοι στα έγγραφα.</p> <p>Παρακαλώ<span> </span><strong>δώστε προσοχή</strong><span> </span>στα παρακάτω:</p> <p>1) Τα e-mail με αιτήματα αναβαθμολόγησης ως επί το πλείστον<span> </span><strong>δεν</strong><span> </span>θα απαντηθούν. Θα λειφθούν όμως όλα υπόψιν.</p> <p>2) Δεν υπάρχει<span> </span><strong>απολύτως κανένας λόγος</strong><span> </span>να στείλετε περισσότερα του ενός e-mail για αναβαθμολόγηση.</p> <p>3) Οι τελικοί βαθμοί θα αναρτηθούν στο τέλος της πρώτης εβδομάδας του<span> </span><strong>Ιούλη.</strong></p> <p> </p> <p>Γ.Λ.</p> <p> </p> <p>Υ.Γ.: ο αριθμός μητρώου 1112202000291 δεν έχει δηλώσει το μάθημα και πήρε βαθμό 2.</p>Tue, 23 Jun 2026 00:58:15 +0300Tue, 23 Jun 2026 00:58:15 +0300661556https://eclass.uoa.gr/modules/announcements/index.php?an_id=651073&course=MATH830<p>Καλησπέρα σε όλα,</p> <p> </p> <p>Η ύλη του μαθήματος για τις εξετάσεις αποτελείται από τα <strong>κεφάλαια 7 και 8 του βιβλίου Sipser</strong>. Συγκεκριμένα, για κόσμο που μελετάει από άλλες πηγές:</p> <p>1) Ασυμπτωτικός συμβολισμός (Big-O notation). Όχι εξειδικευμένα πράγματα.</p> <p>2) Ντετερμινιστικές και μη ντετερμινιστικές μηχανές Turing. Πολυταινιακές μηχανές. Όχι αποδείξεις ισοδυναμίας μοντέλων, κυρίως να ξέρετε τι είναι και να μπορείτε να χειριστείτε τέτοιες μηχανές.</p> <p>3) Κλάσεις χρονικής πολυπλοκότητας P, NP, EXP. Συμπληρωματικές κλάσεις (πχ coNP).</p> <p>4) Αναγωγές πολυωνυμικού χρόνου. NP-πληρότητα. NP-πλήρη προβλήματα σχετιζόμενα με λογικούς τύπους, γραφήματα και σύνολα ακεραίων. <strong>Όχι</strong> θεώρημα Cook-Levin.</p> <p>5) Κλάσεις χωρικής πολυπλοκότητας PSPACE, L, NL. Θεώρημα Savitch.</p> <p>6) PSPACE πληρότητα, NL πληρότητα και αντίστοιχα προβλήματα. NL=coNL. </p> <p> </p> <p>Αν υπάρξει χρόνος να καλυφθούν περισσότερα πράγματα από αυτά στο μάθημα (μάλλον δύσκολο), τα όποια έξτρα πράγματα δούμε <strong>δεν θα περιλαμβάνονται στην εξεταστέα ύλη.</strong> </p> <p> </p> <p>Γ.Λ.</p> <p> </p>Tue, 05 May 2026 13:58:19 +0300Tue, 05 May 2026 13:58:19 +0300651073