Αλγόριθμοι και Πολυπλοκότητα - Βιντεομάθημα

Καλωσορίσατε στο μάθημα "Αλγόριθμοι και Πολυπλοκότητα". Μέσα στα πλαίσια του μαθήματος θα παρουσιαστούν έννοιες όπως: Aσυμπτωτικός συμβολισμός. Ουρές Προτεραιότητας: Σωρός. Αλγόριθμοι ταξινόμησης, Union - Find, Αλγόριθμοι Διαίρει-και-Βασίλευε: Πολλαπλασιασμός αριθμών και πινάκων, Ύψωση σε δύναμη, Quicksort, πιθανοτική Quicksort. Το πρόβλημα της επιλογής, δυαδική αναζήτηση, αναζήτηση με Παρεμβολή, άπληστοι Αλγόριθμοι, δυναμικός προγραμματισμός.

Στόχοι Μαθήματος

Εξοικείωση με τις βασικές έννοιες του μαθήματος.

Προαπαιτούμενες Γνώσεις

Η πληροφορία δεν είναι διαθέσιμη.

Περιεχόμενα

Τεχνικές για ασυμπτωτική εκτίμηση υπολογιστικής πολυπλοκότητας, κριτήρια για επιλογή αλγορίθ­μων, πολυωνυμικοί αλγόριθμοι. Ουρές προτεραιότητας, σωρός, διαχείριση ξένων συνόλων, union — find. Επεξεργασία δεδομένων (ταξινόμηση, επιλογή, αναζήτηση). Μέθοδοι. σχεδιασμού αποδοτικών αλγορίθμων: "διαίρει και βασίλεύε", άπληστοι αλγόριθμοι, δυναμικός προγραμματισμός. Εφαρμογές σε προβλήματα γραφημάτων: αναζήτηση κατά βάθος, αναζήτηση κατά πλάτος, ελάχιστο συνδετικό δέν­δρο, συντομότερα μονοπάτια, μέγιστη ροή και ελάχιστη τομή. Υπολογισιμότητα και πολυπλοκότητα. Κλάσεις υπολογιστικής πολυπλοκότητας και αναγωγές. Οι κλάσεις Ρ και. ΝΡ, ΝΡ-complete προβλή­ματα. Κλάσεις χωρικής πολυπλοκότητας. Εργαστήριο: Μια σειρά αλγοριθμικών προβλημάτων που πρέπει να λυθούν σε C/C+ +.