Σχεδίαση και Ανάλυση Αλγορίθμων

Δημήτριος Kουκόπουλος

Περιγραφή

Βασικές έννοιες. Αναπαράσταση αλγορίθμων. Αναπαράσταση δεδομένων (γραφήματα, δέντρα, ουρές, στοίβες). Τεχνικές διάσχισης δέντρου. Κατηγορίες αλγοριθμικών προβλημάτων (P και NP προβλήματα). Τεχνική της αναγωγής-ευρετικοί αλγόριθμοι. Τεχνικές ανάλυσης αλγορίθμων (πολυπλοκότητα μέσου όρου-πολυπλοκότητα χειρότερης περίπτωσης): ανάλυση αλγορίθμων γραμμικής και δυαδικής αναζήτησης. Αλγόριθμοι και δομές δεδομένων (χρήση στοίβας-αναδρομικοί αλγόριθμοι, χρήση δέντρου και σωρού-αλγόριθμος HeapSort).  Εξισορρόπηση-Διαίρει και βασίλευε: γενική ανάλυση, παραδείγματα (αλγόριθμος γρήγορης ταξινόμησης-QuickSort, συμβολή). Μέθοδοι για προβλήματα με απαγορευτικό αριθμό περιπτώσεων: απληστία. Διάτρεξη και αλγόριθμοι γραφημάτων: αναζήτηση πρώτα κατά πλάτος-χρήση ουράς, αναζήτηση πρώτα κατά βάθος-χρήση στοίβας. Εργαστήριο: Σχεδιασμός αλγορίθμων και ανάπτυξη εφαρμογών σε προγραμματιστικό περιβάλλον.

 

Βιβλιογραφία

  1. Levitin Anany, Ανάλυση και Σχεδίαση Αλγορίθμων, ISBN: 978-960-418-732-4, Εκδ. Τζιόλα, 2018, Κ
Περισσότερα  
Κωδικός: CULTURE109
Κατηγορία: Τμήμα Διαχείρισης Πολιτισμικού Περιβάλλοντος και Νέων Τεχνολογιών » Προπτυχιακό
CC - Αναφορά - Μη Εμπορική Χρήση - Παρόμοια Διανομή
CC - Αναφορά - Μη Εμπορική Χρήση - Παρόμοια Διανομή

Θεματικές Ενότητες

Εισαγωγικές έννοιες. Αλγόριθμοι και ψηφιακά πολιτισμικά περιβάλλοντα. Ιδιότητες, κατηγορίες, απλές αναπαραστάσεις αλγορίθμων. Αξιολόγηση αλγορίθμων (ορθότητα, ποιότητα, χρόνος εκτέλεσης). Ανάλυση αλγορίθμων, μέτρα αποδοτικότητας.

Βέλτιστος αλγόριθμος, ασυμπτωτικοί συμβολισμοί. Διάγραμμα ροής. ψευδοκώδικας. Παραδείγματα.

Γραφήματα. Τρόποι αναπαράστασης γραφημάτων σε γλώσσες προγραμματισμού. Δέντρα, ουρές, στοίβα. Τρόποι αρίθμησης δέντρων.

P και NP προβλήματα. Αναγωγή. Εισαγωγή στους ευρετικούς αλγόριθμους.

Ανάλυση πολυπλοκότητας διαδοχικής και δυαδικής αναζήτησης.

Βασικές έννοιες (δομή σωρού, σωρός). Αλγόριθμοι κατασκευής σωρού και συμπλήρωσης σωρού: παράδειγμα. Αλγόριθμος ταξινόμησης σωρού: παράδειγμα.

Εξισορρόπηση. Διαίρει και Βασίλευε. Εφαρμογές της τεχνικής του διαίρει και βασίλευε στα προβλήματα της αναζήτησης (αλγόριθμος δυαδικής αναζήτησης) και της ταξινόμησης (αλγόριθμος γρήγορης ταξινόμησης QuickSort).

Εισαγωγή. Η μέθοδος της απληστίας. Εφαρμογές της μεθόδου: εύρεση μεγίστου συνάρτησης, κατάταξη έργων με προθεσμίες, πλανόδιος πωλητής. Παραδείγματα.

Αλγόριθμος αναζήτησης πρώτα κατά πλάτος-χρήση ουράς. Αλγόριθμος αναζήτησης πρώτα κατά βάθος-χρήση στοίβας. Παραδείγματα.

Εργαστηριακές ασκήσεις. Σχεδιασμός αλγορίθμων και ανάπτυξη εφαρμογών σε πολιτισμικά περιβάλλοντα.

Ανοικτό Ακαδ. Μάθημα

Ανοικτά Ακαδημαϊκά Μαθήματα
Επίπεδο: A-

Αρ. Επισκέψεων :  10656
Αρ. Προβολών :  41235

Ημερολόγιο