Διακριτά Μαθηματικά
Ακ. Έτος 2015
-2016

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Γενικές Πληροφορίες
Διδάσκων: Τσίχλας Κωνσταντίνος
Email - URL - Τηλ.: tsichlas@delab.csd.auth.gr - http://delab.csd.auth.gr/~tsichlas/ - 2310991934
Ώρες Διαλέξεων: Τρίτη 9-11 Αίθουσα Δ22 και Πέμπτη 14-16 Αίθουσα Δ11
Βοηθός Μαθήματος: Σοφία Αντωνίου (email: antosofi@csd.auth.gr)
Σελίδα μαθήματος 2013-2014 (Εδώ μπορείτε να βρείτε τα θέματα Ιανουαρίου και Σεπτεμβρίου λυμένα)

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Περιγραφή

Τα διακριτά μαθηματικά είναι η μελέτη μαθηματικών δομών που είναι εκ φύσεως διακριτές και δεν υπάρχει η έννοια της συνέχειας. Τα αντικείμενα που θα μελετήσουμε σε αυτό το μάθημα είναι κυρίως αριθμήσιμα σύνολα (π.χ. ακέραιοι), γραφήματα και γλώσσες. Στην επιστήμη των Υπολογιστών τα διακριτά αντικείμενα αναπαριστώνται πολύ πιο εύκολα, και συνήθως οι αλγόριθμοι που κατασκευάζουμε αφορούν τη διαχείριση διακριτών οντοτήτων (δομών δεδομένων, ακεραίων αριθμών, αριθμών πεπερασμένης ακρίβειας, κ.λπ). Για το λόγο αυτό το μάθημα των Διακριτών Μαθηματικών αποτελεί τη βάση για όλα σχεδόν τα μαθήματα θεωρητικής κατεύθυνσης του τμήματος, με εφαρμογές που αρχίζουν από την σχεδίαση δικτύων μέχρι τις βάσεις δεδομένων.

Ειδικότερα, θα εξετάσουμε βασικά στοιχεία λογικής, αριθμητικά συστήματα, βασικά στοιχεία θεωρίας αριθμών, σύνολα, συναρτήσεις - σχέσεις, τη μέθοδο της επαγωγής, αναδρομικές σχέσεις, αθροίσματα και ασυμπτωτικές εκτιμήσεις, συνδυασμούς και μεταθέσεις αντικειμένων, πιθανότητες, γραφήματα και δέντρα.

Αξιολόγηση Μαθήματος

Εξέταση Φεβρουαρίου (και Σεπτεμβρίου): 65% τελικού βαθμού. Επιτρέπεται κάθε φοιτητής να φέρει μαζί του ΜΙΑ μόνο κόλλα Α4 με ό,τι σημειώσεις θέλει.

Ασκήσεις: 25% τελικού βαθμού (ΥΠΟΧΡΕΩΤΙΚΕΣ ΓΙΑ ΟΛΟΥΣ). Προσοχή: δεν θα βαθμολογούνται εργασίες που έχουν γίνει χειρόγραφα (και έπειτα με ηλεκτρονικά μέσα αποστέλλονται). Επίσης, σε περίπτωση αντιγραφής ΟΛΕΣ οι εργασίες που είναι ίδιες θα μηδενίζονται ενώ θα μηδενίζονται επίσης οι προηγούμενες και οι επόμενες εργασίες. Σε περίπτωση που έχετε κάποιο παράπονο για την βαθμολόγηση θα επικοινωνείτε με τον διδάσκοντα.

Πρόοδος: 20% τελικού βαθμού (ΥΠΟΧΡΕΩΤΙΚΗ ΓΙΑ ΟΛΟΥΣ). Η πρόοδος θα γίνει περίπου στις αρχές Δεκεμβρίου.

 Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Ανακοινώσεις

1. (30/10/2015) Εδώ θα βρείτε την 1η υποχρεωτική άσκηση.

2. (11/11/2015) Προσοχή: Στην άσκηση που στέλνετε (όπως και σε όλες τις ασκήσεις) να αναγράφετε το όνομά σας και το ΑΕΜ.

3. (23/11/2015) Εδώ θα βρείτε τους βαθμούς της 1ης άσκησης. Επίσης, εδώ θα βρείτε τις ενδεικτικές λύσεις της 1ης άσκησης.

4. (27/11/2015) Εδώ θα βρείτε την εκφώνηση της 2ης άσκησης.

5. (27/11/2015) Η υποχρεωτική πρόοδος θα γίνει την Τετάρτη 9/12/2015, και ώρα 17-18:30 στο κεντρικό Αμφιθέατρο Εμπείρίκος. Μπορείτε να έχετε κοντά σας ΜΙΑ ΜΟΝΟ κόλλα Α4 γραμμένη μπρος και πίσω χωρίς περιορισμούς στο περιεχόμενο. Η ύλη της προόδου είναι ό,τι έχει γίνει μέχρι τις 26/11 μαζί με την μαθηματική επαγωγή που θα συζητηθεί στις 1/12.

6. (14/12/2015) Εδώ θα βρείτε τους βαθμούς της 2ης άσκησης. Εδώ θα βρείτε τις λύσεις της 2ης άσκησης.

7. (14/12/2015) Εδώ θα βρείτε τους βαθμούς της προόδου.

8. (21/12/2015) Εδώ θα βρείτε την εκφώνηση της 3ης άσκησης.

9. (21/12/2015) Εδώ θα βρείτε τις λύσεις της προόδου.

10. (16/1/2016) ΠΡΟΣΟΧΗ: Το τελευταία μάθημα θα γίνει την Τρίτη 9-11 στην ΑΙΘΟΥΣΑ Β (όχι στην Δ22)

11. Εδώ θα βρείτε την 4η άσκηση.

12. Εδώ θα βρείτε τους βαθμούς της 3ης άσκησης. Εδώ επίσης θα βρείτε τις λύσεις.

13. Εδώ θα βρείτε τους βαθμούς (4η άσκηση, εξέταση και τελικός βαθμός). Εδώ θα βρείτε τις λύσεις της 4ης άσκησης και εδώ θα βρείτε τα θέματα και τις λύσεις της εξέτασης Ιανουαρίου. Η βάση για τον υπολογισμό του τελικού βαθμού όσον αφορά την εξέταση Φεβρουαρίου είναι το 3,5. Μπορείτε να δείτε το γραπτό σας την Παρασκευή 12/2 και ώρα 11:30-13:00 στο γραφείο 29, στην Καλαμαριά, Εθνικής Αντιστάσεως 16, στον 2ο όροφο (Παράρτημα τμήματος Πληροφορικής).

14. (17/6/2016): Εδώ θα βρείτε τους βαθμούς εξέτασης του Ιουνίου. Αν έχετε κάποια απορία παρακαλώ επικοινωνήστε με τον διδάσκοντα μέσω email.

15. (20/9/2016) ΝΕΟ!!!: Εδώ θα βρείτε τους βαθμούς εξέτασης του Σεπτεμβρίου. Εδώ θα βρείτε τα θέματα με τις λύσεις τους. Αν θέλετε να δείτε το γραπτό σας παρακαλώ περάστε την Παρασκευή 23/9 και ώρα 11-12 στο γραφείο 29, Παράρτημα Καλαμαριάς (Εθνικής Αντιστάσεως 16, γραφείο 29).


Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Ημερολόγιο Μαθήματος
Διάλεξη Ημερομηνία Ύλη Εβδομάδας Υλικό
1η 1/10/2015 Εισαγωγή στα Αριθμητικά Συστήματα  
2η 6/10/2015 Πράξεις και Μετατροπές μεταξύ Αριθμητικών Συστημάτων (Rosen 228-234) Διαφάνειες
3η 8/10/2015 (Έγινε μόνο η 2η ώρα λόγω της εκδήλωσης υποδοχής πρωτοετών) Εισαγωγή στον Προτασιακό Λογισμό - Οι Λογικές Πράξεις ΚΑΙ, Η, XOR, ΟΧΙ (Rosen σελ. 9-13)  
13/10/2015 Συνεπαγωγή, Ισοδυναμία, Μετατροπή από Φυσική Γλώσσα (Rosen 13-19,23-26) Διαφάνειες
5η 15/10/2015 Προτασιακές Ισοδυναμίες, Κανόνες Συνεπαγωγής, Μέθοδοι Απόδειξης (Rosen 30-35, 68-72, 78-81)  
6η 20/10/2015 Μέθοδοι και Στρατηγικές Απόδειξης (Rosen 81-93) Ασκήσεις
22/10/2015 Κατηγορήματα και Ποσοτικοί Δείκτες (Rosen 40-53) Διαφάνειες
  27/10/2015 Δεν θα γίνει μάθημα λόγω προγραμματισμένης απουσίας του διδάσκοντα.
Θα βγει ανακοίνωση για την αναπλήρωση της διάλεξης.
8η 29/10/2015 Φωλιασμένοι Ποσοδείκτες, Κανόνες Συνεπαγωγής για Ποσοτικοποιημένες Προτάσεις
(
Rosen 57-63, 73-75)
Ασκήσεις
9η 3/11/2015 Μέθοδοι Αποδείξεων (Rosen 93-104)  
10η 5/11/2015 Σύνολα και πράξεις σε σύνολα (Rosen 112-117, 122-123) Διαφάνειες
11η 10/11/2015 Δυναμοσύνολα, Καρτεσιανό Γινόμενο, Ταυτότητες Συνόλων (Rosen 117-120, 124-128) Ασκήσεις
12η 12/11/2015 Σχέσεις και Ιδιότητές τους, Αναπαράσταση Σχέσεων (Rosen 523-528, 540-541) Διαφάνειες
  17/11/2015 Αργία
19/11/2015 Δεν θα γίνει μάθημα λόγω προβλήματος υγείας του διδάσκοντα.
13η 24/11/2015 Σύνθεση Σχέσεων, Συναρτήσεις, Σχέσεις Ισοδυναμίας (Rosen 131-139, 529-530, 557-563)
Διαιρετότητα Ακεραίων (Rosen 221-223)
Ασκήσεις
14η 26/11/2015 Βαθμιδωτή Αριθμητική, Μέγιστος Κοινός Διαιρέτης, Ο Αλγόριθμος του Ευκλείδη για ΜΚΔ, Πρώτοι Αριθμοί (Rosen 224-226, 238-251) Διαφάνειες
15η 1/12/2015 Απλή και Ισχυρή Επαγωγή (Rosen 287-312)  
16η 3/12/2015 Αθροίσματα - Κάποια Προβλήματα (Rosen σελ. 153-156) Σημειώσεις Διαφάνειες
17η 8/12/2015 Ιδιότητες Αθροισμάτων - Η μέθοδος της Ολοκλήρωσης - Η Μέθοδος Εξίσωσης Αθροίσματος (δες σημειώσεις από 3/12) Ασκήσεις
18η 10/12/2015 Παραγώγιση και Ολοκλήρωση Μεταβλητών, Πρόβλεψη και Επαγωγή (δες σημειώσεις από 3/12)
Εισαγωγή στη Συνδυαστική, Αρχή της Αντιστοιχίας, Αρχή των Περιστερώνων (
Rosen 368-374)
Διαφάνειες
19η 15/12/2015 Κανόνας Γινομένου, Κανόνας Αθροίσματος, Εγκλεισμός - Αποκλεισμός (Rosen 355-365, 506-516) Ασκήσεις
20η 17/12/2015 Μεταθέσεις, Συνδυασμοί, Δυωνυμικοί Συντελεστές, Γενικευμένες Μεταθέσεις και Συνδυασμοί (Rosen 375-381, 382-387, 389-393)  
21η 22/12/2015 Ασκήσεις, Το πρόβλημα των σφαιρών σε κουτιά (Rosen 393-396)  
22η 12/1/2016 Εισαγωγή στα Γραφήματα, Αναπαράσταση Γραφημάτων, Συγκεκριμένοι Τύποι Γραφημάτων (Rosen 589-598, 600-601, 603-606, 611-613,616-620) Διαφάνειες
23η 14/1/2016 Συνδετότητα, Θεώρημα Χειραψιών, Μονοπάτια Euler και Hamilton (Rosen 601-603, 628-634,642-648) Ασκήσεις
24η 19/1/2016 Βασικά Στοιχεία Δένδρων, Ισομορφισμός Γραφημάτων, Επίπεδα Γραφήματα (Rosen 693-696,700,702, 620-623,667-674) Διαφάνειες Ασκήσεις

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Χρήσιμο Υλικό

Τα βασικά εγχειρίδια του μαθήματος είναι:

  1. Ε.Σ. Αγγελής και Γ.Λ. Μπλέρης. Διακριτά Μαθηματικά. Εκδόσεις Τζιόλα. 2003.

  2. K.H. Rosen. Διακριτά Μαθηματικά και Εφαρμογές τους. 7η Έκδοση, Εκδόσεις Τζιόλα, 2015.

  3. Σημειώσεις του διδάσκοντα που θα αναρτώνται στο Ημερολόγιο του Μαθήματος.

Τα ακόλουθα βιβλία και ιστότοποι είναι αρκετά χρήσιμοι για το μάθημα.

  1. D.E. Ensley και J.W. Crawley. Discrete Mathematics: Mathematical Reasoning and Proof with Puzzles, Patterns and Games. Wiley, 2006.

  2. R.L. Graham, D.E. Knuth και O. Patashnik. Concrete Mathematics. Addison-Wesley, 1988.

  3. Εδώ θα βρείτε πολύ καλό υλικό που έχει αναρτηθεί από το MIT σχετικά με διάφορα θέματα που διαπραγματευόμαστε στο μάθημα.

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό