Γενικά
| Σχολή
|
Σχολή Θετικών Επιστημών
|
| Τμήμα
|
Τμήμα Μαθηματικών
|
| Επίπεδο Σπουδών
|
Προπτυχιακό
|
| Κωδικός Μαθήματος
|
MAE581
|
| Εξάμηνο
|
5
|
| Τίτλος Μαθήματος
|
Σχεδίαση και Ανάλυση Αλγορίθμων
|
| Αυτοτελείς Διδακτικές Δραστηριότητες
|
Διαλέξεις, Ασκήσεις και Εργασίες (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 6)
|
| Τύπος Μαθήματος
|
Ειδίκευσης
|
| Προαπαιτούμενα Μαθήματα
|
| Γλώσσα Διδασκαλίας και Εξετάσεων
|
Ελληνική
|
| Το Μάθημα Προσφέρεται σε Φοιτητές Erasmus
|
Ναι (στην Αγγλική γλώσσα)
|
| Ηλεκτρονική Σελίδα Μαθήματος (URL)
|
Δείτε το eCourse, την Πλατφόρμα Ασύγχρονης Εκπαίδευσης του Πανεπιστημίου Ιωαννίνων.
|
Μαθησιακά Αποτελέσματα
| Μαθησιακά Αποτελέσματα
|
- Ο κύριος σκοπός του μαθήματος είναι η εισαγωγή σε θεμελιώδεις αλγοριθμικές έννοιες και τεχνικές.
- Ανάλυση αλγορίθμων, αποδοτικότητα, ασυμπτωτικός συμβολισμός.
- Συνηθισμένοι χρόνοι εκτέλεσης και βασικές δομές δεδομένων: πίνακες, λίστες, στοίβες, ουρές. Ευσταθές ταίριασμα, ορθότητα σωρός και ουρά προτεραιότητας. Μέθοδος «Διαίρει και Βασίλευε»: Εφαρμογές σε ταξινόμηση στοιχείων, Επίλυση αναδρομικών σχέσεων.
- Γραφήματα και αλγόριθμοι γραφημάτων: Διάτρεξη γραφημάτων (BFS, DFS), Συνεκτικότητα, Τοπολογική διάταξη. Μέθοδοι «Απληστείας» και «Δυναμικού Προγραμματισμού»: Ελάχιστα σκελετικά δένδρα (αλγόριθμος Prim, αλγόριθμος Kruskal), Συντομότερες διαδρομές (αλγόριθμος Dijkstra, Ροή δικτύου), Χρονοπρογραμματισμός.
- Επιλεγμένα θέματα: Υπολογιστική πολυπλοκότητα, NP-πληρότητα.
Στο μάθημα περιλαμβάνονται ατομικές και ομαδικές ασκήσεις. Στόχος του μαθήματος είναι οι φοιτητές να είναι σε θέση:
- να κατανοήσουν βασικές αλγοριθμικές τεχνικές,
- να επεκτείνουν την αλγοριθμική τους σκέψη
- να μπορούν να συνδυάζουν γνωστές τεχνικές για την επίλυση νέων προβλημάτων.
|
| Γενικές Ικανότητες
|
- Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση και των απαραίτητων τεχνολογιών
- Αυτόνομη εργασία
- Ομαδική εργασία
|
Περιεχόμενο Μαθήματος
- Βασικά στοιχεία σχεδίασης & ανάλυσης αλγορίθμων
- Ανάλυση αλγορίθμων, Αποδοτικότητα, Ασυμπτωτικός ρυθμός αύξησης
- Συνηθισμένοι χρόνοι εκτέλεσης και δομές δεδομένων (πίνακες, λίστες, ουρές, στοίβες)
- Ευσταθές ταίριασμα, ορθότητα, σωρός και ουρά προτεραιότητας
- Μέθοδος «Διαίρει και Βασίλευε», ταξινόμηση στοιχείων, και επίλυση αναδρομικών σχέσεων
- Αλγόριθμοι γραφημάτων: BFS, DFS, συνεκτικότητα, τοπολογική ταξινόμηση
- Άπληστοι αλγόριθμοι: χρονοπρογραμματισμός και συντομότερες διαδρομές (Dijkstra)
- Eλάχιστα σκελετικά δένδρα (αλγόριθμοι Prim και Kruskal), κωδικοποίηση Huffman
- Μέθοδος «δυναμικού προγραμματισμού»: Ροή δικτύου, χρονοπρογραμματισμός και σακίδια
- Επιλεγμένα θέματα: υπολογιστική πολυπλοκότητα και ΝΡ-πληρότητα.
Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση
| Τρόπος Παράδοσης
|
Στην τάξη
|
| Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών
|
Υποστήριξη Μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-class
|
| Οργάνωση Διδασκαλίας
|
| Δραστηριότητα
|
Φόρτος Εργασίας Εξαμήνου
|
| Διαλέξεις (13Χ3)
|
39
|
| Ατομικές Ασκήσεις
|
78
|
| Ομαδικές Εργασίες
|
33
|
| Σύνολο Μαθήματος
|
150
|
|
| Αξιολόγηση Φοιτητών
|
- Γραπτή τελική εξέταση (70%)
- Ερωτήσεις κατανόησης
- Σχεδίαση αλγορίθμων
- Εργασίες (30%)
- Σχεδίαση αλγορίθμων
- Ανάλυση αλγορίθμων
|
Συνιστώμενη Βιβλιογραφία
Δείτε την υπηρεσία Εύδοξος. Συγγράμματα και άλλες πηγές εκτός της υπηρεσίας Εύδοξος:
General
| School
|
School of Science
|
| Academic Unit
|
Department of Mathematics
|
| Level of Studies
|
Undergraduate
|
| Course Code
|
MAE581
|
| Semester
|
5
|
| Course Title
|
Design and Analysis of Algorithms
|
| Independent Teaching Activities
|
Lectures, laboratory exercises, tutorials, quiz (Weekly Teaching Hours: 3, Credits: 6)
|
| Course Type
|
Special Background
|
| Prerequisite Courses
|
-
|
| Language of Instruction and Examinations
|
Greek
|
| Is the Course Offered to Erasmus Students
|
Yes
|
| Course Website (URL)
|
See eCourse, the Learning Management System maintained by the University of Ioannina.
|
Learning Outcomes
| Learning outcomes
|
This course aims at introducing to students the philosophy of fundamental algorithmic background and techniques. After successfully passing this course the students will be able to:
- Understand basic algorithmic techniques
- Analyze complex algorithms
- Design new algorithmic tools
- Combine already-known techniques for solving new algorithmic problems
|
| General Competences
|
- Search for, analysis and synthesis of data and information, with the use of the necessary technology
- Working independently
- Team work
- Project planning and management.
|
Syllabus
- Fundamental concepts of design and analysis of algorithms
- Analysis of algorithms, Asymptotical growing functions
- Typical running times and data structures (lists, arrays, queues, stacks)
- Stable matching, correctness, priority queue
- «Divide & Conquer» technique, sorting, recursive formulations
- Graph algorithms: BFS, DFS, connectedness, topological ordering
- Greedy algorithms: interval scheduling & shortest paths (Dijkstra)
- Minimum spanning trees(Prim & Kruskal algorithms), Huffman coding
- Dynamic programming: maximum flow, interval scheduling, and Knapsack
- Further Topics: computational complexity and ΝΡ-completeness.
Teaching and Learning Methods - Evaluation
| Delivery
|
Lectures
|
| Use of Information and Communications Technology
|
- Use of projector and interactive board during lectures.
- Course website maintenance. Announcements and posting of teaching material (lecture slides and notes, programs).
- Announcement of assessment marks via the ecourse platform by UOI.
|
| Teaching Methods
|
| Activity
|
Semester Workload
|
| Lectures
|
39
|
| Working independently
|
78
|
| Team work
|
33
|
| Course total
|
150
|
|
| Student Performance Evaluation
|
Final written examination (70%)
- Design and analyze algorithms
Exercises (30%)
- Design and analyze algorithms
|
Attached Bibliography
See the official Eudoxus site. Books and other resources, not provided by Eudoxus: