Μαθήματα του ΑΛΜΑ που θα γίνουν κατά το Χειμερινό Εξάμηνο του Ακαδ. Έτους 2019-2020 στις αίθουσες του Τμήματος Μαθηματικών του ΕΚΠΑ
========================================================================
Μαθηματική Λογική
Δημήτριος Μ. Θηλυκός & Λευτέρης Κυρούσης
Ώρες και ημέρες διδασκαλίας: Δευτέρα 13:00-15:00 και Τετάρτη 13:00-15:00
Πρώτο μάθημα: 30/09 13:00-15:00, Αίθουσα Α31
- Σύντομη ανασκόπηση Προτασιακής Λογικής.
- Πρωτοτάξια Λογική. Αλήθεια και μοντέλα. Τυπικές αποδείξεις (συναγωγές). Θεώρημα αξιοπιστίας και πληρότητας.
- Ερμηνείες (στοιχειώδης θεωρία μοντέλων).
- Μησυμβατική ανάλυση.
- Μη διαγνωσιμότητα και μη πληρότητα. Αναδρομικές συναρτήσεις. Αριθμητικοποίηση σύνταξης. Θεωρία αριθμών. Πρώτο και δεύτερο θεώρημα μη πληρότητας.
Βιβλιογραφία
- H. B. Enderton,Μία Μαθηματική Εισαγωγή στη Λογική, Πανεπιστημιακές Εκδόσεις Κρήτης, 2013
========================================================================
Θεωρία Αναδρομής
Δημήτρης Ζώρος
Ώρες και ημέρες διδασκαλίας: Τρίτη 09:00-11:00 και Τετάρτη 09:00-11:00
Πρώτο μάθημα: 08/10 09:00-11:00, Αίθουσα Α11
- Σχέσεις, συναρτήσεις, γλώσσες, προβλήματα, επαγωγή, αποδεικτικές τεχνικές.- Μηχανές Turing.- Turing απαριθμήσιμες γλώσσες.
- Παραλλαγές/επεκτάσεις μηχανών Turing.- Γενικές γραμματικές.
- Πρωτογενώς αναδρομικές συναρτήσεις.
- Καθολικές μηχανές Turing.
- Αυτοαναφορά, το θεώρημα της αναδρομής.
- Βαθμοί μη-αποφανσιμότητας.
Βιβλιογραφία
- M. Sipser, Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης, 2015.
- H. R. Lewis, Χ. Παπαδημητρίου, Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική, 2005.
- J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation(1st edition), Addison-Wesley, 1979.
- D. C. Kozen: Automata and Computability, Springer, 1997.
- Γ. Ν. Μοσχοβάκης: Αναδρομή και Υπολογισιμότητα, 2011.
- T. Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science(3rd Edition),Pearson, 2006.
========================================================================
Θεωρία Γραφημάτων
Δημήτριος Μ. Θηλυκός
Ώρες και ημέρες διδασκαλίας: Δευτέρα 11:00-13:00 και Τετάρτη 15:00-17:00.
Πρώτο μάθημα: Έναρξη: 07/10 11:00-13:00, Αίθουσα Α21
- Ισομορφισμοί, αυτομορφισμοί, ομάδες αυτομορφισμών.
- Μετασχηματισμοί και σχέσεις σε γραφήματα.
- Βαθμοί, πυκνότητα, ελαχιστομέγιστο θεώρημα εκφυλισμού.
- Μονοπάτια, κύκλοι, διάμετρος, ακτίνα, κέντρο, απόκεντρο, περιφέρεια, περίμετρος.
- Συνεκτικότητα, δισυνεκτικά γραφήματα, το θεώρημα του Menger, το θεώρημα του Tutte για την 3-συνεκτικότητα.
- Δάση και δέντρα, δεντροπαράγοντες.
- Επίπεδα γραφήματα, τοπολογικός ισομορφισμός, δυικά γραφήματα, πυκνότητα και επιπεδότητα, το θεώρημα του Kuratowski.
- Χρωματισμοί γραφημάτων, χρωματικότητα και εκφυλισμός, το θεώρημα του Heawood, το θεώρημα του Erdös για την περιφέρεια και τον χρωματικό αριθμό.
- Η εικασία του Hadwiger.
- Κλίκες, ανεξάρτητα σύνολα, αριθμοί Ramsey.
- Καλύμματα, ταιριάσματα, τέλεια γραφήματα. Το θεώρημα του Lovászγια τα τέλεια γραφήματα, το θεώρημα του Dilworth.
- Μονοπάτια Euler και Hamilton.
- Η πιθανοτική τεχνική, τυχαία γραφήματα.
- Ακραία γραφοθεωρία, τοπολογική θεωρία γραφημάτων.
- Η θεωρία των ελασσόνων γραφημάτων.
Βιβλιογραφία
- R. Diestel,Graph Theory, 4th edition, Springer, 2012.
- J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, 2008.
- Δ. Θηλυκός, Σημειώσεις στη Θεωρία Γραφημάτων, Τμήμα Μαθηματικών, ΕΚΠΑ
========================================================================
Επιχειρησιακή Έρευνα
Διδάσκων: Απόστολος Μπουρνέτας
Ώρες και ημέρες διδασκαλίας: Δευτέρα 09:00-11:00 και Πέμπτη 11:00-13:00
Πρώτο μάθημα: Δευτέρα 30/09 09:00-11:00, Αίθουσα Α32
- Εισαγωγή στο Γραμμικό Προγραμματισμό -Μοντελοποιήσεις: ροές σε δίκτυα, κριτήρια minimax, το πρόβλημα προγραμματισμού στόχων, Γεωμετρία του Γραμμικού Προγραμματισμού –Δυϊκότητα.- Εισαγωγή στον Ακέραιο Προγραμματισμό -Μοντελοποιήσεις.
- Εισαγωγή στο μη-Γραμμικό Προγραμματισμό -Προβλήματα χωρίς περιορισμούς -Προβλήματα με περιορισμούς -Συνθήκες Karush-Kuhn-Tucker -Μέθοδοι φράγματος-Μέθοδοι εσωτερικού σημείου.
Βιβλιογραφία
- Hillier, F.S. and Lieberman, G.J. (1995) Introduction to Operations Research, 6th edition. McGraw-Hill.
- Taha, H.A. (1992) Operations Research, an Introduction, 5th edition. Macmillan
========================================================================
Ειδικά θέματα αλγορίθμων: Μη Γραμμικός Προγραμματισμός
Διδάσκων: Αντώνιος Οικονόμου
Ώρες και ημέρες διδασκαλίας: Δευτέρα 11:00-13:00 Πέμπτη 09:00-11:00
Πρώτο μάθημα: Δευτέρα 30/09 11:00-13:00, Αίθουσα Α32
- Εισαγωγή στον μη-γραμμικό προγραμματισμό.
- Κυρτά σύνολα.
- Κυρτές συναρτήσεις και επεκτάσεις.
- Συνθήκες βελτιστοποίησης.
- Δυϊκότητα.
- Αλγόριθμοι επίλυσης προβλημάτων μη-γραμμικού προγραμματισμού.
Βιβλιογραφία
- Bazaraa, M.S., Sherali, H.D. and Shetty, C.M. (2006) Nonlinear Programming: Theory and Algorithms, 3rd edition, Wiley.
- Beck, A. (2014) Introduction to Nonlinear Optimization: Theory, Algorithms and Applications with MATLAB. MOS-SIAM Series in Optimization.
- Bertsekas, D.P. (1999) Nonlinear Programming, Athena Scientific.- Bertsekas, D.P. (2003) Convex Analysis and Optimization, Athena Scientific.
- Boyd, S. and Vandenberghe, L. (2004) Convex Optimization, Cambridge University Press.
- Luenberger, D.G. (1984) Linear and Nonlinear Programming, Addison-Wesley.
========================================================================