Σχεδίαση και Ανάλυση Αλγορίθμων
Δημήτριος Kουκόπουλος
Βασικές έννοιες. Αναπαράσταση αλγορίθμων. Αναπαράσταση δεδομένων (γραφήματα, δέντρα, ουρές, στοίβες). Τεχνικές διάσχισης δέντρου. Κατηγορίες αλγοριθμικών προβλημάτων (P και NP προβλήματα). Τεχνική της αναγωγής-ευρετικοί αλγόριθμοι. Τεχνικές ανάλυσης αλγορίθμων (πολυπλοκότητα μέσου όρου-πολυπλοκότητα χειρότερης περίπτωσης): ανάλυση αλγορίθμων γραμμικής και δυαδικής αναζήτησης. Αλγόριθμοι και δομές δεδομένων (χρήση στοίβας-αναδρομικοί αλγόριθμοι, χρήση δέντρου και σωρού-αλγόριθμος HeapSort). Εξισορρόπηση-Διαίρει και βασίλευε: γενική ανάλυση, παραδείγματα (αλγόριθμος γρήγορης ταξινόμησης-QuickSort, συμβολή). Μέθοδοι για προβλήματα με απαγορευτικό αριθμό περιπτώσεων: απληστία. Διάτρεξη και αλγόριθμοι γραφημάτων: αναζήτηση πρώτα κατά πλάτος-χρήση ουράς, αναζήτηση πρώτα κατά βάθος-χρήση στοίβας. Εργαστήριο: Σχεδιασμός αλγορίθμων και ανάπτυξη εφαρμογών σε προγραμματιστικό περιβάλλον.
Βιβλιογραφία
- Levitin Anany, Ανάλυση και Σχεδίαση Αλγορίθμων, ISBN: 978-960-418-732-4, Εκδ. Τζιόλα, 2018, Κωδ. Βιβλίου στον Εύδοξο: 68370088.
- Jon Kleiberg, Eva Tardos, Σχεδιασμός Αλγορίθμων, ISBN: 978-960-461-207-9, Εκδ. Κλειδάριθμος, 2009, Κωδ. Βιβλίου στον Εύδοξο: 13898.
- Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Αλγόριθμοι, Εκδ. Κλειδάριθμος, 2009.
- Θ. Παπαθεοδώρου, Αλγόριθμοι: Εισαγωγικά Θέματα και Παραδείγματα, Εκδ. Πανεπιστημίου Πατρών, 2001.
- G. Rawlins, Αλγόριθμοι: Ανάλυση και Σύγκριση, Εκδ. Κριτική, 2004.
- Π. Μποζάνης, Αλγόριθμοι, Σχεδιασμός και Ανάλυση, Εκδ. Τζιόλα, 2003.
- N. Wirth, Αλγόριθμοι και Δομές Δεδομένων, Εκδ. Κλειδάριθμος, 2004.
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, Mc Graw Hill Press, 2009.
- A. Aho, J. Ullman, J. Hopcroft, Data Structures and Algorithms, Addison-Wesley Press, 1983.
- R. Sedgewick, Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching and Graph Algorithms, 3rd Edition, Addison-Wesley Press, 2001.
Βασικές έννοιες. Αναπαράσταση αλγορίθμων. Αναπαράσταση δεδομένων (γραφήματα, δέντρα, ουρές, στοίβες). Τεχνικές διάσχισης δέντρου. Κατηγορίες αλγοριθμικών προβλημάτων (P και NP προβλήματα). Τεχνική της αναγωγής-ευρετικοί αλγόριθμοι. Τεχνικές ανάλυσης αλγορίθμων (πολυπλοκότητα μέσου όρου-πολυπλοκότητα χειρότερης περίπτωσης): ανάλυση αλγορίθμων γραμμικής και δυαδικής αναζήτησης. Αλγόριθμοι και δομές δεδομένων (χρήση στοίβας-αναδρομικοί αλγόριθμοι, χρήση δέντρου και σωρού-αλγόριθμος HeapSort). Εξισορρόπηση-Διαίρει και βασίλευε: γενική ανάλυση, παραδείγματα (αλγόριθμος γρήγορης ταξινόμησης-QuickSort, συμβολή). Μέθοδοι για προβλήματα με απαγορευτικό αριθμό περιπτώσεων: απληστία. Διάτρεξη και αλγόριθμοι γραφημάτων: αναζήτηση πρώτα κατά πλάτος-χρήση ουράς, αναζήτηση πρώτα κατά βάθος-χρήση στοίβας. Εργαστήριο: Σχεδιασμός αλγορίθμων και ανάπτυξη εφαρμογών σε προγραμματιστικό περιβάλλον.
Βιβλιογραφία
- Levitin Anany, Ανάλυση και Σχεδίαση Αλγορίθμων, ISBN: 978-960-418-732-4, Εκδ. Τζιόλα, 2018, Κ
Βασικές έννοιες. Αναπαράσταση αλγορίθμων. Αναπαράσταση δεδομένων (γραφήματα, δέντρα, ουρές, στοίβες). Τεχνικές διάσχισης δέντρου. Κατηγορίες αλγοριθμικών προβλημάτων (P και NP προβλήματα). Τεχνική της αναγωγής-ευρετικοί αλγόριθμοι. Τεχνικές ανάλυσης αλγορίθμων (πολυπλοκότητα μέσου όρου-πολυπλοκότητα χειρότερης περίπτωσης): ανάλυση αλγορίθμων γραμμικής και δυαδικής αναζήτησης. Αλγόριθμοι και δομές δεδομένων (χρήση στοίβας-αναδρομικοί αλγόριθμοι, χρήση δέντρου και σωρού-αλγόριθμος HeapSort). Εξισορρόπηση-Διαίρει και βασίλευε: γενική ανάλυση, παραδείγματα (αλγόριθμος γρήγορης ταξινόμησης-QuickSort, συμβολή). Μέθοδοι για προβλήματα με απαγορευτικό αριθμό περιπτώσεων: απληστία. Διάτρεξη και αλγόριθμοι γραφημάτων: αναζήτηση πρώτα κατά πλάτος-χρήση ουράς, αναζήτηση πρώτα κατά βάθος-χρήση στοίβας. Εργαστήριο: Σχεδιασμός αλγορίθμων και ανάπτυξη εφαρμογών σε προγραμματιστικό περιβάλλον.
Βιβλιογραφία
- Levitin Anany, Ανάλυση και Σχεδίαση Αλγορίθμων, ISBN: 978-960-418-732-4, Εκδ. Τζιόλα, 2018, Κ
Εισαγωγικές έννοιες. Αλγόριθμοι και ψηφιακά πολιτισμικά περιβάλλοντα. Ιδιότητες, κατηγορίες, απλές αναπαραστάσεις αλγορίθμων. Αξιολόγηση αλγορίθμων (ορθότητα, ποιότητα, χρόνος εκτέλεσης). Ανάλυση αλγορίθμων, μέτρα αποδοτικότητας.
Βέλτιστος αλγόριθμος, ασυμπτωτικοί συμβολισμοί. Διάγραμμα ροής. ψευδοκώδικας. Παραδείγματα.
Γραφήματα. Τρόποι αναπαράστασης γραφημάτων σε γλώσσες προγραμματισμού. Δέντρα, ουρές, στοίβα. Τρόποι αρίθμησης δέντρων.
P και NP προβλήματα. Αναγωγή. Εισαγωγή στους ευρετικούς αλγόριθμους.
Ανάλυση πολυπλοκότητας διαδοχικής και δυαδικής αναζήτησης.
Βασικές έννοιες (δομή σωρού, σωρός). Αλγόριθμοι κατασκευής σωρού και συμπλήρωσης σωρού: παράδειγμα. Αλγόριθμος ταξινόμησης σωρού: παράδειγμα.
Εξισορρόπηση. Διαίρει και Βασίλευε. Εφαρμογές της τεχνικής του διαίρει και βασίλευε στα προβλήματα της αναζήτησης (αλγόριθμος δυαδικής αναζήτησης) και της ταξινόμησης (αλγόριθμος γρήγορης ταξινόμησης QuickSort).
Εισαγωγή. Η μέθοδος της απληστίας. Εφαρμογές της μεθόδου: εύρεση μεγίστου συνάρτησης, κατάταξη έργων με προθεσμίες, πλανόδιος πωλητής. Παραδείγματα.
Αλγόριθμος αναζήτησης πρώτα κατά πλάτος-χρήση ουράς. Αλγόριθμος αναζήτησης πρώτα κατά βάθος-χρήση στοίβας. Παραδείγματα.
Ανοικτό Ακαδ. Μάθημα
Αρ. Επισκέψεων : 5669
Αρ. Προβολών : 40483
