ΦΡΟΝΤ10 Γραφήματα και Βασικοί Αλγόριθμοι Γραφημάτων, Άπληστοι Αλγόριθμοι ΙI Ελάχιστα Γεννητικά Δέν

Βασικά στοιχεία σχεδιασμού και ανάλυσης αλγορίθμων, αποδοτικότητα αλγορίθμων, ασυμπτωτικός συμβολισμός, ορθότητα αλγορίθμων, βασικές δομές δεδομένων, ουρές προτεραιότητας και εφαρμογή τους στην ταξινόμηση στοιχείων (heapsort). Γραφήματα και αλγόριθμοι γραφημάτων, συνεκτικότητα και διάτρεξη γραφήματος, αναζήτηση πρώτα-κατά-βάθος, αναζήτηση πρώτα-κατά-πλάτος, ακυκλικά γραφήματα, τοπολογική διάταξη. Μέθοδος "Διαίρει & Βασίλευε" και εφαρμογές της στην ταξινόμηση στοιχείων (merge sort), αναδρομή και επίλυση αναδρομικών σχέσεων. Μέθοδοι απληστίας και δυναμικού προγραμματισμού και εφαρμογής τους σε προβλήματα βελτιστοποίησης: ελάχιστα γεννητικά δένδρα, συντομότερες διαδρομές, ροές δικτύων. Εισαγωγή σε επιλεγμένα θέματα (προσεγγιστικοί αλγόριθμοι, στοιχεία γραμμικού προγραμματισμού, τυχαιοποιημένοι αλγόριθμοι).

Εισαγωγικά - Βασικά Στοιχεία Σχεδιασμού και Ανάλυσης Αλγορίθμων
Τί είναι Αλγόριθμος ;
Βασικά Στοιχεία Ανάλυσης Αλγορίθμων
Ασυμπτωτικός Ρυθμός Αύξησης
Ορισμός ασυμπτωτικού ρυθμού αύξησης - ασυμπτωτικά άνω και κάτω φράγματα
Μέθοδος ανάλυσης της χρονικής και χωρικής πολυπλοκότητας των αλογρίθμων
Βασικές Δομές Δεδομένων, Απλοί Αλγόριθμοι, Σωρός
Εισαγωγή στις βασικές δομές δεδομένων λίστας και πίνακα
Παράθεση παραδειγμάτων βασικών αλγορίθμων για αναζήτηση, απαρίθμηση, ταξινόμηση
Εισαγωγή στο δυαδικό σωρό και τις λειτουργίες του
Ευσταθές Ταίριασμα
Ορισμός ευστάθειας στο ταίριασμα ζευγαριών
Περιγραφή και ανάλυση του αλγορίθμου πρότασης και απόρριψης
Μέθοδος «Διαίρει και Βασίλευε» και Εφαρμογές της
Εισαγωγή στη μέθοδο «Διαίρει και βασίλευε»
Περιγραφή και ανάλυση του αλγορίθμου Συγχώνευσης (merge sort)
Επισκόπηση των βασικών μεθόδων επίλυσης αναδρομικών σχέσεων
Γραφήματα και Βασικοί Αλγόριθμοι Γραφημάτων
Παράθεση βασικών ορισμών και κατηγοριών των γραφημάτων
Παρουσίαση των βασικών δομών αναπαράστασης και τρόπων διάτρεξης των γραφημάτων
Περιγραφή και ανάλυση των αλγορίθμων αναζήτησης κατά πλάτος (BFS) και κατά βάθος (DFS)
Ορισμός και έλεγχος της συνεκτικότητας των γραφημάτων
Ορισμός και έλεγχος της διμερότητας των γραφημάτων
Τοπολογική Διάταξη και Ισχυρά Συνεκτικές Συνιστώσες
Περιγραφή και ανάλυση του αλγορίθμου τοπολογικής διάταξης
Περιγραφή και ανάλυση του αλγορίθμου εύρεσης ισχυρά συνεκτικών συνιστώσεων
Άπληστοι Αλγόριθμοι Ι - Χρονοπρογραμματισμός
Εισαγωγή στo «άπληστο» μοντέλο επίλυσης
Περιγραφή και ανάλυση του αλγορίθμου χρονοπρογραμματισμού εργασιών
Άπληστοι Αλγόριθμοι ΙI - Ελάχιστα Γεννητικά Δένδρα
Ορισμός ελάχιστων γεννητικών δένδρων σε γραφήματα
Περιγραφή και ανάλυση των αλγορίθμων Prim και Kruskal για την εύρεση ελάχιστων γεννητικών δένδρων
Άπληστοι Αλγόριθμοι ΙΙΙ - Συντομότερες Διαδρομές
Ορισμός συντομότερης διαδρομής
Ανάλυση μοντέλου εύρεσης συντομότερων διαδρομών
Περιγραφή και ανάλυση του αλγορίθμου του Dijkstra
Δυναμικός Προγραμματισμός
Εισαγωγή στο Δυναμικό Προγραμματισμό
Περιγραφή και ανάλυση του σταθμισμένου χρονοπρογραμματισμού διαστημάτων

#Αλγόριθμοι #Πολυπλοκότητα_Αλγορίθμων #Δομές_Δεδομένων