Μάθημα : Αλγόριθμοι και Πολυπλοκότητα e-learning
Κωδικός : DEMO-A2052
-
Θεματικές Ενότητες
-
-
Εβδομάδα 1: Ασυμπτωτικός Συμβολισμός, Χρονική Πολυπλοκότητα
-
Εβδομάδα 2: Δομές Δεδομένων: Σωροί, Priority Queues,HashTables
-
Εβδομάδα 3: Η έννοια του γράφου,BFS,DFS ,συνεκτικές συνιστώσες
-
Εβδομάδα 4: Dijkstra,Kruskal,Prim,Minimum Spanning Tree
-
Εβδομάδα 5: Δυναμικός προγραμματισμός-DAGS-Bellman-Ford
-
Εβδομάδα 6: Αλγόριθμος Ford-Fulkerson για μέγιστη ροή
-
Εβδομάδα 7: Άπληστοι Αλγόριθμοι
-
Εβδομάδα 8: 0/1 Σακίδιο και Κ-βασίλισσες
-
Εβδομάδα 9: Αναδρομικοί Αλγόριθμοι
-
Εβδομάδα 10: Master Theorem& Εφαρμογές
-
Εβδομάδα 11: Προβλήματα Απόφασης
-
Εβδομάδα 12: Οι κλάσεις P και NP
-
Εβδομάδα 13: Προβλήματα NP-complete και NP-hard
-
Εβδομάδα 5: Δυναμικός προγραμματισμός-DAGS-Bellman-Ford
Περιεχόμενο: Δυναμικός Προγραμματισμός (ορισμός, βασικές αρχές), Κατευθυνόμενος Άκυκλος Γράφος (Directed Acyclic Graph-DAG), αλγόριθμος συντομότερου μονοπατιού για DAG (τοπολογική ταξινόμηση), αλγόριθμος Bellman-ford (συντομότερου μονοπατιού για DAG)-αρνητικά βάρη
Συζήτηση
Συζητήσεις
Δυναμικός Προγραμματισμός Με βάση όλο το υλικό που μελετήσατε αλλά και τις εργασίες που κάνατε στη τάξη, συζητείστε μεταξύ σας για το τι πιστεύετε ότι προσφέρει ο Δυναμικός Προγραμματισμός ως τεχνική κατασκευής αλγορίθμων.
Συζήτηση
Συζητήσεις
Αλγόριθμος Bellman ford Με βάση όλο το υλικό που μελετήσατε αλλά και την εργασία την οποία υλοποιήσατε, πιστεύετε ότι ο αλγόριθμος Bellman ford είναι ένας αποτελεσματικός τρόπος για την εύρεση του συντομότερου μονοπατιού από τον έναν κόμβο στον άλλον σε έναν DAG ή γενικότερα σε έναν γράφο ? Αιτιολογήστε την άποψή σας.