Διακριτά Μαθηματικά
Topic outline
- General
General
Διδάσκοντες
- Δημήτρης Φωτάκης (fotakis@cs.ntua.gr)
γρ. 1.1.10 τηλ: 210-772-4302 - Δώρα Σούλιου (dsouliou@mail.ntua.gr)
γρ. 1.1.30 τηλ: 210-772-1644
Βοηθοί Φροντιστηρίου και Γραπτών Ασκήσεων
- Έλλη Αναστασιάδη
- Ευαγγελία Γεργατσούλη
- Νίκος Ζαρίφης
- Λουκάς Κάβουρας
- Παναγιώτης Κωστοπαναγιώτης
- Αγγελική Μαθιουδάκη
- Ανδρέας Ματζόρι
- Κατερίνα Νικολιδάκη
- Μάριος Παπαχρήστου
Πρόγραμμα Διαλέξεων
- κάθε Δευτέρα 12:45-14:30 (Αμφιθέατρο 5, νέο κτήριο Ηλεκτρολόγων)
- κάθε Παρασκευή 10:45-12:30 (Αμφιθέατρο 2, νέο κτήριο Ηλεκτρολόγων)
Ώρες Γραφείου
- κάθε Τρίτη 14:00-16:00 στο γραφείο 1.1.30 (παλαιό CoReLab) του παλαιού κτηρίου Ηλεκτρολόγων.
- Δημήτρης Φωτάκης (fotakis@cs.ntua.gr)
- Διαλέξεις
Διαλέξεις
Παρασκευή 23/2/2018- Διαδικαστικά θέματα, εισαγωγή.
- Σύνολα και Πράξεις συνόλων.
- Λογαριασμός στο Gradiance.
Δευτέρα 26/2/2018- Στοιχεία Προτασιακής Λογικής.
- Προτασιακός Λογισμός.
Παρασκευή 2/3/2018- Προτασιακός Λογισμός
- Στοιχεία Κατηγορηματικής Λογικής.
Δευτέρα 5/3/2018
Παρασκευή 9/3/2018- Στοιχεία Κατηγορηματικής Λογικής.
- Αριθμήσιμα και μη Αριθμήσιμα σύνολα.
Παρασκευή 16/3/2018
- Μη υπολογισιμότητα. Το παράδοξο του Russel.
Δευτέρα 19/3/2018
- Διμελείς Σχέσεις: Βασικοί ορισμοί και ιδιότητες, σχεσιακό μοντέλο Βάσεων Δεδομένων.
- Κλειστότητες, μεταβατική κλειστότητα.
Παρασκευή 23/3/2018- Κλειστότητες: αλγόριθμος Warshall.
- Σχέσεις Ισοδυναμίας.
Δευτέρα 26/3/2018Παρασκευή 30/3/2018
Δευτέρα 16/4/2018
Παρασκευή 20/4/2018
- Βασικές έννοιες θεωρίας γραφημάτων: βαθμός κορυφής, διμερή γραφήματα, υπογραφήματα, μονοπάτια και συνεκτικότητα, αριθμοί Ramsey, συνεκτικότητα
Δευτέρα 23/4/2018
- Γραφήματα: Κύκλος Euler
- Γραφήματα: κύκλος Hamilton
Παρασκευή 27/4/2018Δευτέρα 30/4/2018
- Επίπεδα γραφήματα
- Χρωματικός αριθμός γραφημάτων
Παρασκευή 4/5/2018
- Χρωματικός Αριθμός, Κάλυμμα κορυφών, Ταίριασμα
- Δέντρα: Συνδετικό δέντρο, Ελάχιστα Συνδετικό Δέντρο.
Δευτέρα 7/5/2018
- Αρχή Εγκλεισμού-Αποκλεισμού
- Συνδυαστική Απαρίθμηση: κανόνες γινομένου αθροίσματος, διατάξεις.
Παρασκευή 11/5/2018
- Συνδυαστική Απαρίθμηση: συνδυασμοί.
Δευτέρα 14/5/2018
- Συνδυαστική Απαρίθμηση: παραδείγματα, ασκήσεις
- Χρήση συνδυαστικής για τον υπολογισμό πιθανοτήτων σε διακριτούς δειγματοχώρους.
- Βασικές ιδιότητες δυωνυμικών συντελεστών.
Παρασκευή 18/5/2018
- Γεννήτριες Συναρτήσεις: ορισμός και βασικές ιδιότητες
- Γεννήτριες Συναρτήσεις: εφαρμογές στην απαρίθμηση συνδυασμών
Δευτέρα 21/5/2018
- Γεννήτριες Συναρτήσεις: εφαρμογές στην απαρίθμηση συνδυασμών
- Εκθετικές Γεννήτριες Συναρτήσεις και απαρίθμηση διατάξεων
Τετάρτη 23/5/2018
- Συνδυαστική-Γεννήτριες: Παραδείγματα,ασκήσεις
Παρασκευή 25/5/2018
- Διατύπωση αναδρομικών σχέσεων
- Επίλυση αναδρομικών σχέσεων
Παρασκευή 1/6/2018
- Φροντιστηριακές Διαλέξεις
Φροντιστηριακές Διαλέξεις
Φροντιστήριο 28/3/2018
- Σύνολα, Σχέσεις, Προτασιακή και Κατηγορηματική Λογική.
Φροντιστήριο 25/4/2018
- Λύσεις 1ης Γραπτής Σειράς Ασκήσεων.
Φροντιστήριο 9/5/2018
- Ασκήσεις στη Θεωρία Γραφημάτων.
- Βιβλιογραφία
Βιβλιογραφία
Σύνολα και πράξεις συνόλων.
Αριθμήσιμα και μη αριθμήσιμα σύνολα, αρχή της διαγωνιοποίησης, μη υπολογισιμότητα, παράδοξο του Russell.
Σχέσεις και συναρτήσεις. Διμελείς σχέσεις, ιδιότητες διμελών σχέσεων, σχέσεις ισοδυναμίας, σχέσεις μερικής και ολικής διάταξης, κλειστότητες σχέσεων.
Στοιχεία προτασιακής και κατηγορηματικής λογικής.
Αποδεικτικές διαδικασίες, μαθηματική επαγωγή, αρχή του περιστερώνα.
Στοιχεία Θεωρίας Γραφημάτων. Είδη γραφημάτων, βαθμός κορυφής, υπογραφήματα, ισομορφισμός γραφημάτων, κλίκες και ανεξάρτητα σύνολα, χρωματικός αριθμός.
Διαδρομή, μονοκονδυλιά, μονοπάτι, απόσταση, συντομότερες διαδρομές, κυκλώματα και ίχνη Euler, χαρακτηρισμός γραφημάτων με κύκλωμα Euler, κύκλοι και μονοπάτια Hamilton, ικανές και αναγκαίες συνθήκες, θεώρημα Dirac.
Δέντρα χαρακτηρισμός δέντρων, συνδετικά δέντρα και ιδιότητες, εφαρμογές.
Επίπεδα γραφήματα, τύπος του Euler, θεώρημα Kuratowski.
Συνδεσιμότητα γραφημάτων, γέφυρες και σύνολα κοπής, σημεία κοπής και διαχωριστές, θεώρημα Menger, δίκτυα και ροές.
Αρχή εγκλεισμού-αποκλεισμού.
Συνδυαστική απαρίθμηση. Κανόνες γινομένου και αθροίσματος, εφαρμογές αρχής εγκλεισμού-αποκλεισμού, μεταθέσεις και διατάξεις, συνδυασμοί, δυωνυμικοί συντελεστές, τρίγωνο του Pascal, διανομή διακεκριμένων και μη-διακεκριμένων αντικειμένων σε υποδοχές, κατασκευή μεταθέσεων και συνδυασμών, στοιχεία διακριτής πιθανότητας, στοιχεία θεωρίας πληροφορίας.
Γεννήτριες Συναρτήσεις. Βασικές ιδιότητες, εφαρμογή στον υπολογισμό αθροισμάτων, εφαρμογή στην επίλυση συνδυαστικών προβλημάτων, εκθετικές Γεννήτριες Συναρτήσεις.
Επίλυση γραμμικών αναδρομικών εξισώσεων με σταθερούς συντελεστές. Χαρακτηριστική εξίσωση, ομογενής λύση, ειδική λύση, επίλυση με τη μέθοδο των Γεννητριών Συναρτήσεων.
Στοιχεία Θεωρίας Αριθμών. Διαιρετότητα και πρώτοι αριθμοί, αλγόριθμος Ευκλείδη, αριθμητική modulo, γραμμικές ισοτιμίες, Κινέζικο θεώρημα υπολοίπων.
Ασυμπτωτικός συμβολισμός και ασυμπτωτική εκτίμηση.
- Συμπληρωματικό Υλικό Σημειώσεις
Συμπληρωματικό Υλικό Σημειώσεις
Κάποιες σημειώσεις για τεχνικές επίλυσης αναδρομικών σχέσεων (Δ. Φωτάκης).
Κάποιες σημειώσεις στις βασικές ιδιότητες των Γεννητριών Συναρτήσεων (Δ. Φωτάκης) και στις εφαρμογές τους.
Κάποιες σημειώσεις στις βασικές έννοιες της συνδυαστικής (Δ. Φωτάκης), μια χρήσιμη σύνοψη σε μορφή διαγράμματος, και η ίδια σύνοψη ενημερωμένη με τις αντίστοιχες Γεννήτριες Συναρτήσεις).
Κάποιες σημειώσεις στις βασικές έννοιες της Θεωρίας Γραφημάτων (Δ. Φωτάκης). Δείτε ακόμη εδώ για αντίστοιχο υλικό.
Σημειώσεις σχετικά με σύνολα και πράξεις συνόλων.
Μια χρήσιμη σύνοψη των περισσότερων βασικών εννοιών των Διακριτών Μαθηματικών (αναφέρεται και σε πολλές έννοιες που δεν θα συναντήσουμε στο μάθημα).
Κάποιες σημειώσεις σχετικά με το συντακτικό και την σημασιολογία της Πρωτοβάθμιας Λογικής (Δ. Φωτάκης).
Σημειώσεις για την αποδεικτική τεχνική της Μαθηματικής Επαγωγής (Δ. Φωτάκης).
- Προτεινόμενες Ασκήσεις
Προτεινόμενες Ασκήσεις
Οι προτεινόμενες ασκήσεις στοχεύουν στην (περαιτέρω) εξάσκηση των φοιτητών στο αντικείμενο του μαθήματος. Συνίσταται να τις λύνετε, αλλά δεν έχετε υποχρέωση να παραδώσετε τις λύσεις τους και οι λύσεις τους δεν βαθμολογούνται. Κάποιες από τις προτεινόμενες ασκήσεις θα συζητούνται στο φροντιστήριο. Ενδεικτικές λύσεις τους θα αναρτώνται δύο εβδομάδες περίπου μετά την ανακοίνωσή τους (ανάλογα και με την πρόοδο των διαλέξεων).
- 1η Σειρά: Σύνολα. Προτασιακή και Κατηγορηματική Λογική. Σχέδιο Λύσεων.
- 2η Σειρά: Κατηγορηματική Λογική. Μαθηματική Επαγωγή. Αρχή του Περιστερώνα. Σχέδιο Λύσεων.
- 3η Σειρά: Κατηγορηματική Λογική. Αλυσίδες και Αντιαλυσίδες. Γραφήματα. Σχέδιο Λύσεων.
- 4η Σειρά: Αρχή Εγκλεισμού-Αποκλεισμού. Συνδυαστική. Σχέδιο Λύσεων.
- 5η Σειρά: Γεννήτριες Συναρτήσεις και Εφαρμογές τους στη Συνδυαστική. Σχέδιο Λύσεων.
- Γραπτές Εργασίες
- Παλαιότερα έτη