Παρουσίαση/Προβολή

(5.004) -  Παρασκευή Φραγκοπούλου

Περιγραφή Μαθήματος

Μαθησιακά Αποτελέσματα

Το μάθημα πραγματεύεται το πεδίο των αλγορίθμων με έμφαση στην ανάλυση τους, τεχνικές σχεδιασμού τους, και τεχνολογίες υλοποίησής τους. Σαν μάθημα κορμού απευθύνεται σε όλους τους φοιτητές του Τμήματος οι οποίοι πρόκειται να ασχοληθούν με την ανάπτυξη προγραμμάτων σε ανώτερο επίπεδο και την ανάπτυξη εφαρμογών λογισμικού.

Περιεχόμενο Μαθήματος

Ενότητες Θεωρητικών Διαλέξεων

Εισαγωγή: Γενικά περί αλγορίθµων. Ανάλυση αλγορίθµων, ασυµπτωτικός συµβολισµός, ρυθµός αύξησης συναρτήσεων, ανάλυση πολυπλοκότητας.

• Αναζήτηση: Σειριακή αναζήτηση, δυαδική αναζήτηση, αναζήτηση κατά οµάδες, αναζήτηση Fibonacci.
• Ταξινόµηση: Ταξινόµηση µε εισαγωγή, ταξινόµηση µε επιλογή, ταξινόµηση µε αντιµετάθεση, ταξινόµηση παρεµβολής µε φθίνοντα διαστήµατα, ταξινόµηση µε διαµερισµό (merge-sort). Συγχώνευση (merge). Ταχυταξινόµηση (quicksort), ταξινόμηση σωρού (heap-sort), ταξινόµηση σε γραµµικό χρόνο. Διάµεσοι, ελάχιστο και µέγιστο.
• Γράφοι: Γενικά, ορισµοί, αποθήκευση. ∆ιάσχιση, προβλήµατα. Αναζήτηση σε γράφους, τοπολογική ταξινόµηση, ισχυρά συνδεδεµένες συνιστώσες, ελαφρύτατα συνδετικά δέντρα (Prim και Kruskal), οµοαφετηριακές διαδροµές (Bellman-Ford, Dijkstra). Περιοδεύων πωλητής.
• ∆υναµικός προγραµµατισµός, άπληστοι αλγόριθµοι, πιθανοκρατικοί αλγόριθµοι (επιλογή θεµάτων).

Εργαστηριακές Ασκήσεις

Στο εργαστήριο του μαθήµατος εκπονούνται προγραμματιστικές ασκήσεις που αποτελούν εφαρµογή των θεμάτων που διδάσκονται στο αντίστοιχο µάθηµα της θεωρίας. Ο διδάσκων θα αξιολογεί τον τρόπο ανάπτυξης και τα αποτελέσµατα των ασκήσεων. Δίνονται επίσης εργασίες για κατ' οίκον προετοιµασία, στην ανάπτυξη και στα αποτελέσµατα των οποίων εξετάζεται ο φοιτητής. Οι εργαστηριακές ασκήσεις αναπτύσσονται στη γλώσσα προγραμματισμού C και στο προγραμματιστικό περιβάλλον DevC++. Περιλαμβάνουν τα παρακάτω θέματα:

• Αλγόριθμοι αναζήτησης (σειριακή αναζήτηση, δυαδική αναζήτηση επαναληπτικός και αναδρομικός αλγόριθμος, κτλ.).
• Αλγόριθμοι ταξινόμησης (επαναληπτικοί αλγόριθμοι: ταξινόμηση με εισαγωγή, με επιλογή, με αντιμετάθεση; αναδρομικοί αλγόριθμοι: ταξινόμηση συγχώνευσης, ταχεία ταξινόμηση; ταξινόμηση σωρού, κτλ.).
• Αλγόριθμοι γράφων (υλοποίηση γράφου με δυσδιάστατο πίνακα και λίστες γειτονικών κορυφών, BFS, DFS, τοπολογική ταξινόμηση, κτλ.).

Προτεινόμενη Βιβλιογραφία:

• «Αλγόριθμοι Σχεδίαση και Εφαρμογές», Michael T. Goodrich, Roberto Tamassia, Εκδόσεις Γιούρδας, ISBN 978-960- 512-697-1.
• Σημειώσεις μαθήματος.

Ημερομηνία δημιουργίας

Δευτέρα 4 Οκτωβρίου 2021