ΣΥΝΔΥΑΣΤΙΚΗ ΚΑΙ ΘΕΩΡΙΑ ΓΡΑΦΗΜΑΤΩΝ
| Τίτλος | ΣΥΝΔΥΑΣΤΙΚΗ ΚΑΙ ΘΕΩΡΙΑ ΓΡΑΦΗΜΑΤΩΝ / Conbinatorics and Graph Theory |
| Κωδικός | 0572 |
| Σχολή | Θετικών Επιστημών |
| Τμήμα | Μαθηματικών |
| Κύκλος / Επίπεδο | 1ος / Προπτυχιακό |
| Περίοδος Διδασκαλίας | Εαρινή |
| Υπεύθυνος/η | Βασίλειος Καραγιάννης |
| Κοινό | Ναι |
| Κατάσταση | Ενεργό |
| Course ID | 600015304 |
Πρόγραμμα Σπουδών: ΠΠΣ Τμήμα Μαθηματικών (2014-σήμερα)
Εγγεγραμμένοι φοιτητές: 99
| Κατεύθυνση | Τύπος Παρακολούθησης | Εξάμηνο | Έτος | ECTS |
|---|---|---|---|---|
| Κορμός | Επιλογής | Εαρινό | - | 5 |
| Τίτλος | ΣΥΝΔΥΑΣΤΙΚΗ ΚΑΙ ΘΕΩΡΙΑ ΓΡΑΦΗΜΑΤΩΝ |
| Ακαδημαϊκό Έτος | 2020 – 2021 |
| Περίοδος Τάξης | Εαρινή |
| Διδάσκοντες άλλων Κατηγοριών | |
| Ώρες Εβδομαδιαία | 3 |
| Class ID | 600166729
|
Τύπος Μαθήματος 2016-2020
- Επιστημονικής Περιοχής
- Ανάπτυξης Δεξιοτήτων
Τύπος Μαθήματος 2011-2015
Ειδικού Υποβάθρου / Κορμού
Τρόπος Παράδοσης
- Πρόσωπο με πρόσωπο
Ηλεκτρονική Διάθεση Μαθήματος
- e-Οδηγός Σπουδών https://qa.auth.gr/el/class/1/600166729
Erasmus
Το μάθημα προσφέρεται και σε φοιτητές
προγραμμάτων ανταλλαγής.
Γλώσσα Διδασκαλίας
- Ελληνικά (Διδασκαλία, Εξέταση)
Προαπαιτήσεις
Γενικές Προαπαιτήσεις
Βασικές γνώσεις στα αντικείμενα της Γραμμικής Άλγεβρας, Θεωρίας Αριθμών και Άλγεβρας.
Μαθησιακά Αποτελέσματα
Με την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα:
1) μπορούν να χρησιμοποιήσουν ειδικές μεθόδους Απαρίθμησης, Κατανομής, Διαμερίσεων και Διαιρέσεων
2) μπορούν να χρησιμοποιήσουν τις ιδιότητες των Γραφημάτων (Γράφων) και Τυχαίων Γραφημάτων ως αναπαράσταση πολύπλοκων συστημάτων
Γενικές Ικανότητες
- Εφαρμογή της γνώσης στην πράξη
- Αυτόνομη εργασία
- Ομαδική εργασία
- Εργασία σε διεθνές περιβάλλον
- Εργασία σε διεπιστημονικό περιβάλλον
Περιεχόμενο Μαθήματος
1.ΤΕΧΝΙΚΕΣ ΑΠΑΡΙΘΜΗΣΗΣ: Θεμελιώδης Αρχή Απαρίθμησης, Μεταθέσεις – Διατάξεις –Συνδυασμοί, Διωνυμικοί συντελεστές, Αρχή Συμπερίληψης Εξαίρεσης, Διαταράξεις, Αρχή του Περιστερώνα ή Dirichlet, Αρχή Αντανάκλασης, Κίνηση σε Δικτυωτά, Λεξικογραφική μέθοδος καταγραφής μεταθέσεων.
2. ΕΙΔΙΚΑ ΘΕΜΑΤΑ ΑΠΑΡΙΘΜΗΣΗΣ: Το τρίγωνο του Pascal και οι αριθμοί Fibonacci, Διοφαντικές εξισώσεις και Διαμερίσεις, Προβλήματα Ταξινόμησης (σφαιρίδια σε κελιά, αριθμοί Stirling, Bell, Catalan), Γεννήτριες Συναρτήσεις.
3. ΓΡΑΦΗΜΑΤΑ: Βασικές Έννοιες (τάξη, μέγεθος, συνδετικότητα, κατεύθυνση, γείτονες, περίπατος, διαδρομή, μονοπάτι, κύκλος, συμπλήρωμα, διμερή, πράξεις, βαθμός, γεωδαισιακή, απόσταση, διάμετρος, ακτίνα), Ιδιότητες-Χαρακτηριστικοί Πίνακες (Θεωρήματα σχετικά με τους βαθμούς, ισομορφία, πίνακες συνδέσεων, αντιστοιχιών, γραμμογράφημα), Υπογραφήματα, μονοπάτια, δένδρα, παράγοντες, τομές, γέφυρες, Θεωρήματα Kirchoff, Dirac, Menger, Ειδικά Γραφήματα (Επίπεδα, Euler, Hamilton, n-κύβοι, Κώδικες Gray, Αριθμοί Ramsey), Χρωματισμοί (βασικά θεωρήματα, χρωματικά πολυώνυμα, αλγόριθμοι χρωματισμού)
4. ΕΙΣΑΓΩΓΗ ΣΤΑ ΤΥΧΑΙΑ ΓΡΑΦΗΜΑΤΑ: Δίκτυα Erdös-Rényi (κατανομή βαθμών, μέσος βαθμός, η γιγάντια συνιστώσα, μέση απόσταση, δείκτης συσταδοποίησης, μεταβατικότητα), Εισαγωγή στα δίκτυα small world και scale free, Εισαγωγή στα Πραγματικά Δίκτυα, Δείκτες Κεντρικότητας (Βαθμική, Ιδιοκεντρικότητα, Διαμεσότητα, Εγγύτητας), Παραδείγματα με χρήση της γλώσσα R (Δίκτυα συνεργασίας, κοινωνικά, οικονομικά, on line κλπ.)
Λέξεις Κλειδιά
Συνδυαστική Απαρίθμηση, Γράφημα, Γράφος, Τυχαία Γραφήματα
Τύποι Εκπαιδευτικού Υλικού
- Σημειώσεις
- Διαφάνειες
- Βιντεοδιαλέξεις
- Πολυμεσικό υλικό
- Βιβλίο
Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών
Χρήση Τ.Π.Ε.
- Χρήση Τ.Π.Ε. στη Διδασκαλία
- Χρήση Τ.Π.Ε. στην Επικοινωνία με τους φοιτητές
- Χρήση Τ.Π.Ε. στην Αξιολόγηση των Φοιτητών
Περιγραφή
Χρήση του PowerPoint στις διαλέξεις και στην εξ αποστάσεως διδασκαλία.
Βιντεοσκοπημένες διαλέξεις στο elearning
Οργάνωση Μαθήματος
| Δραστηριότητες | Φόρτος Εργασίας | ECTS | Ατομικά | Ομαδικά | Erasmus |
|---|---|---|---|---|---|
| Διαλέξεις | 39 | 1,3 | ✓ | ||
| Μελέτη και ανάλυση βιβλίων και άρθρων | 108 | 3,6 | ✓ | ||
| Εξετάσεις | 3 | 0,1 | ✓ | ||
| Σύνολο | 150 | 5 |
Αξιολόγηση Φοιτητών
Περιγραφή
Κουίζ ερωτήσεων πολλαπλής επιλογής κατά τη διάρκεια του εξεαμήνου
Κουίζ ερωτήσεων πολλαπλής επιλογής στην τελική εξέταση
Γραπτή τελική εξέταση
Μέθοδοι Αξιολόγησης Φοιτητών
- Γραπτή Εξέταση με Ερωτήσεις Πολλαπλής Επιλογής (Διαμορφωτική, Συμπερασματική)
- Γραπτή Εξέταση με Ερωτήσεις Σύντομης Απάντησης (Διαμορφωτική, Συμπερασματική)
- Γραπτή Εξέταση με Ερωτήσεις Εκτεταμένης Απάντησης (Διαμορφωτική, Συμπερασματική)
Βιβλιογραφία
Βιβλιογραφία μαθήματος (Εύδοξος)
1)Μωυσιάδη Πολ.(2001): Εφαρμοσμένη Συνδυαστική. Η τέχνη να μετράμε χωρίς μέτρημα, Εκδ. ΖΗΤΗ, Θεσσαλονίκη.
2)Χαραλαμπίδη, Χ (1990). Συνδυαστική τεύχη 1 και 2, Πανεπιστήμιο Αθήνας
Επιπρόσθετη βιβλιογραφία για μελέτη
1)Béla Bollobás (2002). Modern Graph Theory. Springer.
2)West B.D. (2002). Introduction to Graph Theory.
3)Bondy J.A., Murty U.S.R. (2008). Graph Theory. Springer
4)Diestel R. (2005). Graph Theory. Springer, NY.
5)Maarten van Steen (2010). Graph Theory and Complex Networks An Introduction. Maarten van Steen
Τελευταία Επικαιροποίηση
29-05-2021
