Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Algorithms 2006f - UoA
Αλγόριθμοι
Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Πανεπιστήμιο Αθηνών
Διδάσκων: Ηλίας Κουτσουπιάς
Ώρες: Τρίτη 2-4, Αίθουσα ΣΤ -
Πέμπτη 1-3, Αίθουσα Ζ
Η σελίδα αφορά
το προπτυχιακό μάθημα “Προηγμένα Θέματα Αλγορίθμων”
το μεταπτυχιακό μάθημα “Αλγόριθμοι και Πολυπλοκότητα” του
Τμήματος Πληροφορικής και του ΜΠΛΑ.
Το μάθημα απευθύνεται σε προπτυχιακούς και μεταπτυχιακούς φοιτητές που
θέλουν να εμβαθύνουν στην σχεδίαση και ανάλυση αλγορίθμων. Στο μάθημα
αυτό μελετώνται προβλήματα και αλγόριθμοι με σκοπό την εμπέδωση των
βασικών αλλά και πιο προχωρημένων τεχνικών σχεδίασης και ανάλυσης
αλγορίθμων. Τα θέματα περιλαμβάνουν βασικούς αλγόριθμους για
προβλήματα γράφων (graph problems) όπως προβλήματα χρωματισμού, το
πρόβλημα του Hamilton, το πρόβλημα του πλανόδιου πωλητή και άλλα;
προβλήματα ροών σε δίκτυα (network flows), προβλήματα ταιριάσματος
(matching), προβλήματα αριθμητικής όπως ο Ταχύς Μετασχηματισμός
Fourier (Fast Fourier Transform), γεωμετρικά προβλήματα. Μελετώνται
ντετερμινιστικοί, πιθανοτικοί, προσεγγιστικοί αλγόριθμοι και οι
κλάσεις πολυπλοκότητας P, NP, PSPACE.
Ανακοινώσεις
H εξέταση του μαθήματος θα γίνει την 01/10/2007, 18:00. Η
εξέταση είναι κοινή για όλους, προπτυχιακούς και μεταπτυχιακούς.
Το απαιτούμενο υπόβαθρο και των προπτυχιακών και των μεταπτυχιακών
φοιτητών είναι το ίδιο: μαθηματική παιδεία και το προπτυχιακό μάθημα
“Αλγόριθμοι και Πολυπλοκότητα” του Τμήματος Πληροφορικής ή κάποιο
αντίστοιχο. Κάποιοι μεταπτυχιακοί φοιτητές, κυρίως του ΜΠΛΑ, μπορεί να
μην έχετε παρακολουθήσει τέτοιο μάθημα και σε αυτή την περίπτωση
πρέπει να μελετήσετε μόνοι τους κάποια θέματα.
Βιβλίο - Σημειώσεις
Το μάθημα θα βασιστεί κυρίως στο βιβλίο
Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
http://www.cse.ucsd.edu/~dasgupta/algorithms/
Την ίδια ύλη καλύπτουν σε μεγάλο βαθμό και τα βιβλία
J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005
Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, The MIT Press; 2nd edition, 2001
Βαθμολογία
Η βαθμολογία του μαθήματος θα βασιστεί στο τελικό διαγώνισμα (60%),
στις ασκήσεις (25%) και στην εργασία (15%). Για να περάσει όμως
κάποιος το μάθημα απαιτείται να συγκεντρώσει βαθμό 5 στο καθένα από τα
τρία. Με αυτή την έννοια, η εργασία και οι ασκήσεις είναι υποχρεωτικές.
Ασκήσεις
Οι ασκήσεις να παραδίδονται χειρόγραφες ή τυπωμένες στη Γραμματεία
Θεωρητικής Πληροφορικής. Ηλεκτρονική παράδοση ασκήσεων δεν είναι
αποδεκτή. Φυσικά δεν θα γίνονται δεκτές μετά το χρόνο παράδοσής τους.
1η άσκηση: Παράδοση 14/12/2006, 1μμ.
Λύστε τα προβλήματα από το βιβλίο Dasgupta-Papadimitriou-Vazirani:
2.5, 2.22, 3.22, 4.17, 5.7
2η άσκηση: Παράδοση 18/01/2007, 1μμ.
Λύστε τα προβλήματα από το βιβλίο Dasgupta-Papadimitriou-Vazirani:
6.2, 6.6, 6.7, 8.1, 8.9, 8.14
Εργασία
Επιλογή εργασίας μέχρι 14/12/2006
Παράδοση μέχρι 12/01/2007
Όλοι οι φοιτητές που παίρνετε το μάθημα πρέπει να κάνετε κάποια
υποχρεωτική εργασία.
Η παράδοση της εργασίας θα ακολουθηθεί από προφορική εξέταση. Oι
εργασίες πρέπει να μην είναι όλες ίδιες: Το πολύ 3 ομάδες μπορούν να
κάνουν την ίδια εργασία. Το wiki θα βοηθήσει σ' αυτό, αφού μόνο οι
πρώτες 3 ομάδες που θα δηλώσουν στο wiki μια εργασία μπορούν να την
κάνουν.
Πρέπει να επιλέξετε εργασία και να την δήλωσετε στο wiki του μαθήματος
μέχρι την 14/12/2006.
Περισσότερες πληροφορίες θα βρείτε στη σελίδα project.html.