Αλγόριθμοι και Πολυπλοκότητα

Πληροφορίες

Περιεχόμενο Μαθήματος



Απλές μηχανές Turing. Πρωταρχικές αναγωγικές συναρτήσεις. Αναγωγικές συναρτήσεις. μ-αναγωγικές συναρτήσεις. Τάξη πολυπλοκότητας. NC-αλγόριθμοι. Τα PComplete Προβλήματα. Αριθμοί Godel. Συνάρτηση Ackermann. Τεχνικές Σχεδίασης Αλγορίθμων. Προβλήματα από την περιοχή του Γραμμικού και Δυναμικού Προγραμματισμού.