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

Με την επιτυχή ολοκλήρωση του μαθήματος, ο φοιτητής/τρια θα:

• Έχει την γνώση να αναλύει αλγορίθμους (ελαφρύτατες διαδρομές, μέγιστες ροές, συνεκτικότητα, μέγιστα ταιριάσματα, ροές ελάχιστου κόστους) και σχετικές δομές δεδομένων (σωροί Fibonacci, δυναμικά δένδρα) σε προβλήματα βελτιστοποίησης
• Έχει την δεξιότητα να εφαρμόζει τυχαιοποιημένους αλγόριθμους όπως ελαφρύτατες διαδρομές, ελαφρύτατα συνδετικά δένδρα, ελάχιστες αποκοπές, τυχαίοι περίπατοι, αλυσίδες Markov, καθολική διασπορά.
• Έχει την ικανότητα να επιλύει NP-δυσχερή προβλήματα και προσεγγιστικοί αλγόριθμοι (ευρετικές μέθοδοι, γραμμικός προγραμματισμός και στρογγυλοποίηση).

Δεν απαιτούνται.

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

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

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