Αλγόριθμοι και Πολυπλοκότητα
Γενικά
Κωδικός: ΥΠ25
Γλώσσα: Ελληνική
Τρόπος διδασκαλίας: Δια ζώσης
Προαπαιτούμενα:
Φόρτος εργασίας
- Διαλέξεις: 39.0 ώρες
- Εργαστήριο: 0.0 ώρες
- Μελέτη: 68.0 ώρες
- Εργασία: 18.0 ώρες
Περιεχόμενο Μαθήματος
Η έννοια του αλγορίθμου και πολυπλοκότητας. Αναδρομικοί αλγόριθμοι και αναδρομικές εξισώσεις. Αλγόριθμοι ταξινόμησης και επιλογής. Σωροί και ουρές προτεραιότητας. Τεχνικές αναζήτησης: μετασχηματισμός κλειδιού hashing, δένδρα αναζήτησης. Δυναμικός προγραμματισμός, Άπληστοι greedy αλγόριθμοι. Αλγόριθμοι γραφημάτων: αναζήτηση σε γράφημα, ελάχιστο συνδέον δένδρο, συντομότεροι δρόμοι, μέγιστη ροή. Γενικά θέματα: ταξινόμηση μέσω δικτύων, αλγόριθμοι σύγκρισης συμβολοσειρών, αριθμητικοί αλγόριθμοι, NP-complete, προβλήματα.
1η εβδομάδα Διάλεξη: Εισαγωγή.
2η εβδομάδα Διάλεξη: Ανάλυση Αλγορίθμων
3η εβδομάδα Διάλεξη: Αλγόριθμοι Γραφημάτων
4η εβδομάδα Διάλεξη: Άπληστοι Αλγόριθμοι Ι
5η εβδομάδα Διάλεξη: Άπληστοι Αλγόριθμοι ΙΙ
6η εβδομάδα Διάλεξη: Διαίρει και Βασίλευε Ι
7η εβδομάδα Διάλεξη: Διαίρει και Βασίλευε ΙΙ
8η εβδομάδα Διάλεξη: Δυναμικός Προγραμματισμός Ι
9η εβδομάδα Διάλεξη: Δυναμικός Προγραμματισμός ΙΙ
10η εβδομάδα Διάλεξη: Δίκτυα, Μέγιστη Ροή και Ελάχιστη Αποκοπή
11η εβδομάδα Διάλεξη: NP Υπολογιστική Δυσεπιλυσιμότητα Ι
12η εβδομάδα Διάλεξη: NP Υπολογιστική Δυσεπιλυσιμότητα ΙΙ
13η εβδομάδα Διάλεξη: Αντιμετώπιση NP-Πληρότητας
Μαθησιακά Αποτελέσματα
Σκοπός του μαθήματος είναι η εξοικείωση των φοιτητών με την σχεδίαση και την ανάλυση αλγορίθμων για την επίλυση βασικών προβλημάτων. Οι φοιτητές θα γνωρίσουν τις βασικότερες μεθόδους σχεδίασης αλγορίθμων και τις βασικότερες αρχές ανάλυσης και μέτρησης της αποδοτικότητας των αλγορίθμων. Τέλος θα γνωρίσουν τις βασικότερες κλάσεις πολυπλοκότητας.
Φοιτητές που ολοκληρώνουν το μάθημα θα είναι σε θέση να γνωρίζουν:
- Τις βασικές τεχνικές σχεδιασμού αλγορίθμων.
- Αρχές ανάλυσης και μέτρησης της αποδοτικότητας των αλγορίθμων.
- Τρόπους αντιμετώπισης της NP-Πληρότητας
Δεξιότητες
- Προσαρμογή σε νέες καταστάσεις
- Λήψη αποφάσεων
- Αυτόνομη εργασία
- Προαγωγή της ελεύθερης, δημιουργικής και επαγωγικής σκέψης