Σκοπός του μαθήματος:
Να καταλάβουμε τι κοινό έχουν οι αλγόριθμοι που χρησιμοποιούμε
και πώς τους κρίνουμε ως προς την πολυπλοκότητά τους.
Μπορούμε να τους κατανοούμε και να τους κρίνουμε χρησιμοποιώντας αυστηρά
μαθηματικά εργαλεία;
Συνοπτικά Περιεχόμενα:
Μαθηματικοί ορισμοί για σχέσεις, αλφάβητα, συμβολοσειρές, γλώσσες.
Πεπερασμένα αυτόματα. Push-down αυτόματα.Μηχανές Turing. Τυπικές γλώσσες.
Πολυωνυμικοί αλγόριθμοι και NP-πλήρη προβλήματα. Τεχνικές για ασυμπτωτική
ανάλυση προγραμμάτων και κριτήρια για την επιλογή αλγορίθμων. Βέλτιστοι
αλγόριθμοι, αλγόριθμοι "διαίρει και βασίλευε", δυναμικός προγραμματισμός,
εξαντλητική αναζήτηση, γράφοι AND/OR, backtracking, branch and bound, ευριστικοί
αλγόριθμοι greedy.
Ωρες Μαθήματος (Φθινόπωρο-Χειμώνας 2003-4)
Ημέρα | Ώρες | Αίθουσα |
Δευτέρα | 14:00 - 16:00 | 2 |
Τετάρτη | 11:00 - 13:00 | 2 |
Ανακοινώσεις: (0)
Διδάσκων:
Α. Ντελόπουλος