Πληροφορίες

 

Διδάσκων : Λουκάς Γεωργιάδης

Διαλέξεις :  Τρίτη 4-7μμ, αίθουσα I3

Ώρες γραφείου : Δευτέρα και Τετάρτη 12-2μμ, γραφείο Γ8

 

Περισσότερες πληροφορίες στο eCourse

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

 

· T. Cormen, C. Leiserson, R. Rivest και C. Stein, Εισαγωγή στους Αλγορίθμους, τόμοι I και ΙΙ, Πανεπιστημιακές Εκδόσεις Κρήτης

· J. Kleinberg και E. Tardos, Σχεδιασμός Αλγορίθμων, Κλειδάριθμος

· S. Dasgupta, C. Papadimitriou και U. Vazirani, Αλγόριθμοι, Κλειδάριθμος

· R. Ahuja, T. Magnanti and J. Orlin, Network Flows, Prentice Hall

· A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge

· M. Mitzermacher and E. Upfal, Probability and Computing, Cambridge

· R. Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics

Προηγμένη Σχεδίαση Αλγορίθμων και Δομών Δεδομένων

Περίληψη Μαθήματος

 

Επιλεγμένα θέματα από τις ακόλουθες περιοχές: Προβλήματα βελτιστοποίησης σε δίκτυα: Αλγόριθμοι (ελαφρύτατες διαδρομές, μέγιστες ροές, συνεκτικότητα, μέγιστα ταιριάσματα, ροές ελάχιστου κόστους) και σχετικές δομές δεδομένων (σωροί Fibonacci, δυναμικά δένδρα). Τυχαιοποιημένοι αλγόριθμοι (ελαφρύτατες διαδρομές, ελαφρύτατα συνδετικά δένδρα, ελάχιστες αποκοπές, τυχαίοι περίπατοι, αλυσίδες Markov, καθολική διασπορά). Δομές δεδομένων (ουρές προτεραιότητας, δομές αναζήτησης) και μοντέλα μνήμης (RAM, εξωτερική μνήμη). Αριθμοθεωρητικοί αλγόριθμοι (κρυπτοσυστήματα, έλεγχος πρώτευσης). Άμεσοι αλγόριθμοι (προσπέλαση λίστας, σελιδοποίηση, εξισορρόπηση φορτίου). NP-δυσχερή προβλήματα και προσεγγιστικοί αλγόριθμοι (ευρετικές μέθοδοι, γραμμικός προγραμματισμός και στρογγυλοποίηση).

Εαρινό εξάμηνο

2015