ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ
Χαράλαμπος Κωνσταντόπουλος
Διδάσκων
Aναπληρωτής Καθηγητής Χ. Κωνσταντόπουλος
email: konstant@unipi.gr
Ωρες γραφείου: Δευτέρα 12:00-13:00, Πέμπτη 10:00-12:00, Γρ. 104 Κτίριο Γρ. Λαμπράκη
Περιγραφή
Το αντικείμενο του μαθήματος είναι η παρουσίαση των βασικών εννοιών της Θεωρίας Υπολογι-σμού.Συγκεκριμένα, παρουσιάζονται τα εξής θέματα: Κανονικές Γλώσσες, Πεπερασμένα Αυτόματα, Ανταιτιοκρατία, Μη κανονικές γλώσσες, Ασυμφρα-στικές Γλώσσες, Ασυμφραστικές Γραμματικές, Αυτόματα στοίβας, Μη ασυμφραστικές γλώσσες, το Δόγμα Church-Turing, Μηχανές Turing, Παραλλαγές μηχανών Turing, o ορισμός του αλγορίθμου, Διαγνώσιμες γλώσσες, η τεχνική της Αναγωγής, Χρονική Πολυπλοκότητα, Κλάση P, κλάση NP, NP-πληρότητα, Το θεώρημα Cook-Levin, Χωρική Πολυπλοκότητα, Το θεώρημα του Savitch, η κλάση PSPACE, PSPACE-πληρότητα
Συγγράμματα
ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ (μτφρ. της 3ης διεθνούς έκδοσης), Michael Sipser, Πανεπιστημιακές Εκδόσεις Κρήτης
Στοιχεία θεωρίας υπολογισμού, Lewis Harry R.,Παπαδημητρίου Χρίστος Χ., Εκδόσεις Κριτική.
ΛιγότεραΔιδάσκων
Aναπληρωτής Καθηγητής Χ. Κωνσταντόπουλος
email: konstant@unipi.gr
Ωρες γραφείου: Δευτέρα 12:00-13:00, Πέμπτη 10:00-12:00, Γρ. 104 Κτίριο Γρ. Λαμπράκη
Περιγραφή
Το αντικείμενο του μαθήματος είναι η παρουσίαση των βασικών εννοιών της Θεωρίας Υπολογι-σμού.Συγκεκριμένα, παρουσιάζονται τα εξής θέματα: Κανονικές Γλώσσες, Πεπερασμένα Αυτόματα, Ανταιτιοκρατία, Μη κανονικές γλώσσες, Ασυμφρα-στικές Γλώσσες, Ασυμφραστικές Γραμματικές, Αυτόματα στοίβας, Μη ασυμφραστικές γλώσσες, το Δόγμα Church-Turing, Μηχανές Turing, Παραλλαγές μηχανών Turing, o ορισμός του αλγορίθμου, Διαγνώσιμες γλώσσες, η τεχνική της Αναγωγής, Χρονική Πολυπλοκότητα, Κλάση P, κλάση NP, NP-πληρότητα, Το θεώρημα Cook-Levin, Χωρική Πολυπλοκότητα, Το θεώρημα του Savitch, η κλάση PSPACE, PSPACE-πληρότητα
Συγγράμματα
ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ (μτφρ. της 3ης διεθνούς έκδοσης), Michael Sipser, Πανεπιστημιακές Εκδόσεις Κρήτης
Στοιχεία θεωρίας υπολογισμού, Lewis Harry R.,Παπαδημητρίου Χρίστος Χ., Εκδόσεις Κριτική.
Διδάσκων
Aναπληρωτής Καθηγητής Χ. Κωνσταντόπουλος
email: konstant@unipi.gr
Ωρες γραφείου: Δευτέρα 12:00-13:00, Πέμπτη 10:00-12:00, Γρ. 104 Κτίριο Γρ. Λαμπράκη
Περιγραφή
Το αντικείμενο του μαθήματος είναι η παρουσίαση των βασικών εννοιών της Θεωρίας Υπολογι-σμού.Συγκεκριμένα, παρουσιάζονται τα εξής θέματα: Κανονικές Γλώσσες, Πεπερασμένα Αυτόματα, Ανταιτιοκρατία, Μη κανονικές γλώσσες, Ασυμφρα-στικές Γλώσσες, Ασυμφραστικές Γραμματικές, Αυτόματα στοίβας, Μη ασυμφραστικές γλώσσες, το Δόγμα Church-Turing, Μηχανές Turing, Παραλλαγές μηχανών Turing, o ορισμός του αλγορίθμου, Διαγνώσιμες γλώσσες, η τεχνική της Αναγωγής, Χρονική Πολυπλοκότητα, Κλάση P, κλάση NP, NP-πληρότητα, Το θεώρημα Cook-Levin, Χωρική Πολυπλοκότητα, Το θεώρημα του Savitch, η κλάση PSPACE, PSPACE-πληρότητα
Συγγράμματα
ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ (μτφρ. της 3ης διεθνούς έκδοσης), Michael Sipser, Πανεπιστημιακές Εκδόσεις Κρήτης
Στοιχεία θεωρίας υπολογισμού, Lewis Harry R.,Παπαδημητρίου Χρίστος Χ., Εκδόσεις Κριτική.