Θεωρία γραφημάτων και πρακτικές εφαρμογές της
EDG701 Θεωρία γραφημάτων και πρακτικές εφαρμογές της
Γράφημα είναι ένας τρόπος αναπαράστασης των σχέσεων μεταξύ οντοτήτων. Οι οντότητες σε ένα γράφημα αναπαρίστανται με τελείες και αντιστοιχούν π.χ., σε άτομα, κράτη, γεωγραφικά σημεία, δομικά μέρη κτλ. Οντότητες που σχετίζονται συνδέονται με μια γραμμή που καλείται ακμή, π.χ., υπάρχει ακμή μεταξύ ατόμων που είναι φίλοι, συμμαχικών κρατών, πόλεων που συνδέονται με οδική αρτηρία, γειτονικών χώρων σε μια ανασκαφή, κοκ.
Η θεωρία γραφημάτων αποτελεί κλάδο των μαθηματικών που ασχολείται με τη συστηματική μελέτη των σχέσεων μεταξύ οντοτήτων. Η θεωρία γραφημάτων αποτελεί εξαιρετικό εργαλείο για τη διατύπωση προβλημάτων με ακρίβεια και για τον καθορισμό θεμελιωδών αλληλεπιδράσεων και βρίσκει ευρεία εφαρμογή σε διάφορα επιστημονικά πεδία επειδή μπορεί να συνεισφέρει στη γρήγορη εξοικείωση επιστημόνων, ακόμα και χωρίς ισχυρό σχετικό υπόβαθρο, με φλέγοντα ερευνητικά ζητήματα.
Στο πλαίσιο του μαθήματος εξετάζουμε βασικές κατηγορίες γραφημάτων και ιδιότητές τους και μελετάμε βασικά γραφοθεωρητικά προβλήματα (π.χ., χρωματισμός, εύρεση ανεξάρτητων συνόλων, κάλυψη συνόλων, εύρεση ελάχιστων μονοπατιών, κτλ) με ευρείες πρακτικές εφαρμογές και ιδιαίτερο ενδιαφέρον για μελέτη ζητημάτων στην περιοχή της ιστορίας-αρχαιολογίας.
Το μάθημα συνεισφέρει στην εξοικείωση με τον «υπολογιστικό τρόπο σκέψης» (computational thinking) και στη δημιουργία του αναγκαίου υποβάθρου για αξιοποίηση μεθόδων, τεχνικών και εργαλείων από την περιοχή της επιστήμης και τεχνολογίας υπολογιστών στη μελέτη ζητημάτων στο πεδίο της σύγχρονης ιστορίας-αρχαιολογίας.
Προτεινόμενα συγγράμματα