Postgraduate Section 4 1001

• Ελληνικά
• English

Αλγοριθμική Θεωρία Γραφημάτων

Γενικά

Σχολή	Σχολή Θετικών Επιστημών
Τμήμα	Τμήμα Μαθηματικών
Επίπεδο Σπουδών	Μεταπτυχιακό
Κωδικός Μαθήματος	ΠΛ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.