Αλγοριθμική Θεωρία Γραφημάτων
Γενικά
| Σχολή
|
Σχολή Θετικών Επιστημών
|
| Τμήμα
|
Τμήμα Μαθηματικών
|
| Επίπεδο Σπουδών
|
Μεταπτυχιακό
|
| Κωδικός Μαθήματος
|
ΠΛ4
|
| Εξάμηνο
|
2
|
| Τίτλος Μαθήματος
|
Αλγοριθμική Θεωρία Γραφημάτων
|
| Αυτοτελείς Διδακτικές Δραστηριότητες
|
Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 7.5)
|
| Τύπος Μαθήματος
|
Επιλογής
|
| Προαπαιτούμενα Μαθήματα
|
Απαραίτητες γνώσεις από 641 - Σχεδίαση και Ανάλυση Αλγορίθμων
|
| Γλώσσα Διδασκαλίας και Εξετάσεων
|
Ελληνική
|
| Το Μάθημα Προσφέρεται σε Φοιτητές Erasmus
|
Ναι (στην Αγγλική γλώσσα)
|
| Ηλεκτρονική Σελίδα Μαθήματος (URL)
|
Δείτε το eCourse, την Πλατφόρμα Ασύγχρονης Εκπαίδευσης του Πανεπιστημίου Ιωαννίνων.
|
Μαθησιακά Αποτελέσματα
| Μαθησιακά Αποτελέσματα
|
Ο κύριος σκοπός του μαθήματος είναι η εισαγωγή σε θεμελιώδεις αλγοριθμικές τεχνικές σχετικές με προβλήματα βελτιστοποίησης και μοντελοποίησης σε γραφήματα.
- Αλγοριθμική θεωρία γραφημάτων και θεμελιώδη γραφοθεωρητικά θέματα. Σχεδίαση αποτελεσματικών αλγορίθμων και ανάλυση πολυπλοκότητας παραμετροποιημένων αλγορίθμων για ΝΡ-πλήρη προβλήματα.
- Κλάσεις γραφημάτων: Τέλεια γραφήματα. Τριγωνικά γραφήματα. Μεταβατικά γραφήματα. Διαχωρίσιμα γραφήματα. Μεταθετικά γραφήματα. Γραφήματα διαστημάτων. Συμπληρωματικά παραγόμενα γραφήματα και κατωφλικά γραφήματα.
- Αλγοριθμικά θέματα σχετικά με γραφοθεωρητικές παραμέτρους.
Στο μάθημα περιλαμβάνονται ατομικές ασκήσεις, περιληπτική συγγραφή και παρουσίαση σχετικών ερευνητικών εργασιών. Στόχος του μαθήματος είναι οι φοιτητές να είναι σε θέση:
- να κατανοήσουν τη θεωρία γραφημάτων,
- να επεκτείνουν την αλγοριθμική τους σκέψη σε προβλήματα σχετικά με τη θεωρία γραφημάτων, και
- να αντιλαμβάνονται δύσκολα επιλύσιμα προβλήματα σε κλάσεις γραφημάτων.
|
| Γενικές Ικανότητες
|
- Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση και των απαραίτητων τεχνολογιών
- Αυτόνομη εργασία
- Εργασία σε διεπιστημονικό περιβάλλον
|
Περιεχόμενο Μαθήματος
- Βασικά στοιχεία Θεωρίας Γραφημάτων
- Αλγοριθμικά προβλήματα συνδυαστικής σε γραφήματα
- Κλάσεις πολυπλοκότητας και παραμετροποιημένου-χρόνου αλγόριθμοι
- Τριγωνικά γραφήματα. Μεταβατικά γραφήματα. Διαχωρίσιμα γραφήματα.
- Μεταθετικά γραφήματα. Γραφήματα διαστημάτων. Συμπληρωματικά παραγόμενα γραφήματα και κατωφλικά γραφήματα.
- Αλγοριθμικά θέματα σχετικά με γραφοθεωρητικές παραμέτρους.
|
Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση
| Τρόπος Παράδοσης
|
Στην τάξη
|
| Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών
|
Υποστήριξη Μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-class
|
| Οργάνωση Διδασκαλίας
|
| Δραστηριότητα
|
Φόρτος Εργασίας Εξαμήνου
|
| Διαλέξεις
|
39
|
| Αυτοτελής Μελέτη
|
78
|
| Επίλυση Ασκήσεων - Εργασίες
|
70.5
|
| Σύνολο Μαθήματος
|
187.5
|
|
| Αξιολόγηση Φοιτητών
|
- Ατομικές Εργασίες (50%)
- Συγγραφή Περιληπτικών Εργασιών (20%)
- Παρουσιάσεις (30%)
|
Συνιστώμενη Βιβλιογραφία
Δείτε την υπηρεσία Εύδοξος.
Algorithmic Graph Theory
General
| School
|
School of Science
|
| Academic Unit
|
Department of Mathematics
|
| Level of Studies
|
Graduate
|
| Course Code
|
ΠΛ4
|
| Semester
|
2
|
| Course Title
|
Algorithmic Graph Theory
|
| Independent Teaching Activities
|
Lectures (Weekly Teaching Hours: 3, Credits: 7.5)
|
| Course Type
|
Special Background
|
| Prerequisite Courses
|
-
|
| Language of Instruction and Examinations
|
Greek
|
| Is the Course Offered to Erasmus Students
|
Yes (in English)
|
| 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 fundamental algorithmic techniques for solving problems related and modeled by graphs. After successfully passing this course the students will be able to:
- Understand graph theory.
- Design and analyze algorithms for graph problems.
- Understand difficult problems on graph classes.
|
| 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
All the above will give to the stundetns the opportunity to work in an international multidisciplinary environment.
|
Syllabus
- Fundamental Graph Theory
- Algorithmic and Combinatorial Graph Problems
- Complexity Classes and Parameterized Algorithms
- Chordal graphs, Comparability graphs, Split graphs
- Permutation graphs, Interval graphs, Cographs, Threshold graphs
- Algorithmic problems and width parameters
|
Teaching and Learning Methods - Evaluation
| Delivery
|
In the class
|
| Use of Information and Communications Technology
|
Use of projector and interactive board during lectures.
|
| Teaching Methods
|
| Activity
|
Semester Workload
|
| Lectures
|
39
|
| Study and analysis of bibliography
|
78
|
| Preparation of assignments and interactive teaching
|
70.5
|
| Course total
|
187.5
|
|
| Student Performance Evaluation
|
- Written work (50%)
- Essay / report (20%)
- Public presentation (30%)
|
Attached Bibliography
See the official Eudoxus site.