Εισαγωγή στους Αλγορίθμους 2013-2014
Χρήστος Ζαρολιάγκης
Στόχος μαθήματος: Η εισαγωγή των φοιτητών σε θεμελιώδεις αλγοριθμικές έννοιες και τεχνικές.
Ύλη: Βασικά στοιχεία σχεδιασμού και ανάλυσης αλγορίθμων, αποδοτικότητα αλγορίθμων, ασυμπτωτικός συμβολισμός, ορθότητα αλγορίθμων, βασικές δομές δεδομένων, ουρές προτεραιότητας και εφαρμογή τους στην ταξινόμηση στοιχείων (heapsort). Γραφήματα και αλγόριθμοι γραφημάτων, συνεκτικότητα και διάτρεξη γραφήματος, αναζήτηση πρώτα-κατά-βάθος, αναζήτηση πρώτα-κατά-πλάτος, ακυκλικά γραφήματα, τοπολογική διάταξη. Μέθοδος "Διαίρει & Βασίλευε" και εφαρμογές της στην ταξινόμηση στοιχείων (mergesort), αναδρομή και επίλυση αναδρομικών σχέσεων. Μέθοδοι απληστίας και δυναμικού προγραμματισμού και εφαρμογής τους σε προβλήματα βελτιστοποίησης: ελάχιστα γεννητικά δένδρα, συντομότερες διαδρομές, ροές δικτύων. Εισαγωγή σε επιλεγμένα θέματα (προσεγγιστικοί αλγόριθμοι, στοιχεία γραμμικού προγραμματισμού, τυχαιοποιημένοι αλγόριθμοι).
Τμηματική Ομάδα Εργασίας:
Λιγότερα
Στόχος μαθήματος: Η εισαγωγή των φοιτητών σε θεμελιώδεις αλγοριθμικές έννοιες και τεχνικές.
Ύλη: Βασικά στοιχεία σχεδιασμού και ανάλυσης αλγορίθμων, αποδοτικότητα αλγορίθμων, ασυμπτωτικός συμβολισμός, ορθότητα αλγορίθμων, βασικές δομές δεδομένων, ουρές προτεραιότητας και εφαρμογή τους στην ταξινόμηση στοιχείων (heapsort). Γραφήματα και αλγόριθμοι γραφημάτων, συνεκτικότητα και διάτρεξη γραφήματος, αναζήτηση πρώτα-κατά-βάθος, αναζήτηση πρώτα-κατά-πλάτος, ακυκλικά γραφήματα, τοπολογική διάταξη. Μέθοδος "Διαίρει & Βασίλευε" και εφαρμογές της στην ταξινόμηση στοιχείων (mergesort), αναδρομή και επίλυση αναδρομικών σχέσεων. Μέθοδοι απληστίας και δυναμικού προγραμματισμού και εφαρμογής τους σε προβλήματα βελτιστοποίησης: ελάχιστα γεννητικά δένδρα, συντομότερες διαδρομές, ροές δικτύων. Εισαγωγή σε επιλεγμένα θέματα (προσεγγιστικοί αλγόριθμοι, στοιχεία γραμμικού προγραμματισμού, τυχαιοποιημένοι αλγόριθμοι).
Τμηματική Ομάδα Εργασίας:
Στόχος μαθήματος: Η εισαγωγή των φοιτητών σε θεμελιώδεις αλγοριθμικές έννοιες και τεχνικές.
Ύλη: Βασικά στοιχεία σχεδιασμού και ανάλυσης αλγορίθμων, αποδοτικότητα αλγορίθμων, ασυμπτωτικός συμβολισμός, ορθότητα αλγορίθμων, βασικές δομές δεδομένων, ουρές προτεραιότητας και εφαρμογή τους στην ταξινόμηση στοιχείων (heapsort). Γραφήματα και αλγόριθμοι γραφημάτων, συνεκτικότητα και διάτρεξη γραφήματος, αναζήτηση πρώτα-κατά-βάθος, αναζήτηση πρώτα-κατά-πλάτος, ακυκλικά γραφήματα, τοπολογική διάταξη. Μέθοδος "Διαίρει & Βασίλευε" και εφαρμογές της στην ταξινόμηση στοιχείων (mergesort), αναδρομή και επίλυση αναδρομικών σχέσεων. Μέθοδοι απληστίας και δυναμικού προγραμματισμού και εφαρμογής τους σε προβλήματα βελτιστοποίησης: ελάχιστα γεννητικά δένδρα, συντομότερες διαδρομές, ροές δικτύων. Εισαγωγή σε επιλεγμένα θέματα (προσεγγιστικοί αλγόριθμοι, στοιχεία γραμμικού προγραμματισμού, τυχαιοποιημένοι αλγόριθμοι).
Τμηματική Ομάδα Εργασίας:
- Τί είναι Αλγόριθμος ;
- Βασικά Στοιχεία Ανάλυσης Αλγορίθμων
- Ορισμός ασυμπτωτικού ρυθμού αύξησης - ασυμπτωτικά άνω και κάτω φράγματα
- Μέθοδος ανάλυσης της χρονικής και χωρικής πολυπλοκότητας των αλογρίθμων
- Εισαγωγή στις βασικές δομές δεδομένων λίστας και πίνακα
- Παράθεση παραδειγμάτων βασικών αλγορίθμων για αναζήτηση, απαρίθμηση, ταξινόμηση
- Εισαγωγή στο δυαδικό σωρό και τις λειτουργίες του
- Ορισμός ευστάθειας στο ταίριασμα ζευγαριών
- Περιγραφή και ανάλυση του αλγορίθμου πρότασης και απόρριψης
- Εισαγωγή στη μέθοδο «Διαίρει και βασίλευε»
- Περιγραφή και ανάλυση του αλγορίθμου Συγχώνευσης (merge sort)
- Επισκόπηση των βασικών μεθόδων επίλυσης αναδρομικών σχέσεων
- Παράθεση βασικών ορισμών και κατηγοριών των γραφημάτων
- Παρουσίαση των βασικών δομών αναπαράστασης και τρόπων διάτρεξης των γραφημάτων
- Περιγραφή και ανάλυση των αλγορίθμων αναζήτησης κατά πλάτος (BFS) και κατά βάθος (DFS)
- Ορισμός και έλεγχος της συνεκτικότητας των γραφημάτων
- Ορισμός και έλεγχος της διμερότητας των γραφημάτων
- Περιγραφή και ανάλυση του αλγορίθμου τοπολογικής διάταξης
- Περιγραφή και ανάλυση του αλγορίθμου εύρεσης ισχυρά συνεκτικών συνιστώσεων
- Εισαγωγή στo «άπληστο» μοντέλο επίλυσης
- Περιγραφή και ανάλυση του αλγορίθμου χρονοπρογραμματισμού εργασιών
- Ορισμός ελάχιστων γεννητικών δένδρων σε γραφήματα
- Περιγραφή και ανάλυση των αλγορίθμων Prim και Kruskal για την εύρεση ελάχιστων γεννητικών δένδρων
- Ορισμός συντομότερης διαδρομής
- Ανάλυση μοντέλου εύρεσης συντομότερων διαδρομών
- Περιγραφή και ανάλυση του αλγορίθμου του Dijkstra
- Εισαγωγή στο Δυναμικό Προγραμματισμό
- Περιγραφή και ανάλυση του σταθμισμένου χρονοπρογραμματισμού διαστημάτων
Ανοικτό Ακαδ. Μάθημα
Αρ. Επισκέψεων : 13620
Αρ. Προβολών : 87919
