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

Το μάθημα δίνει μια γενική εποπτεία σε προχωρημένα θέματα υπολογιστικής πολυπλοκότητας που περιλαμβάνουν το P vs. NP πρόβλημα, τυχαιότητα, εφαρμογές προβλημάτων NP-complete.

1. Elmasri R. and Navathe S.B.: "Θεμελιώδεις Αρχές Συστημάτων Βάσεων Δεδομένων", Τόμος Α', 5η Έκδοση, 2007. Μετάφραση από τις Εκδόσεις Δίαυλος, 2008.
2. Ramakrishnan R. and Gehrke J.: "Συστήματα Διαχείρισης Βάσεων Δεδομένων" Τόμος Α', 2η έκδοση, McGraw Hill, 2000. Μετάφραση από τις Εκδόσεις Τζιόλα, 2002.
 

1. Toby J. Teorey: "Database Modeling & Design”, ISBN 1558605002, Morgan Kaufmann
2. Terry Halpin: “Information Modeling and Relational Databases: From Conceptual Analysis to Logical Design”, ISBN 1558606726

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

Φυσική Παρουσία.