ΕΦΑΡΜΟΣΜΕΝΗ ΣΥΝΔΥΑΣΤΙΚΗ 2022-2023

Η σελιδα του μαθήματος για το ακαδημαϊκό έτος 2023-2024 είναι η
https://gunet2.cs.unipi.gr/courses/TMB136/

Περιγραφή:

Η συνδυαστική είναι η επιστήμη της αναζήτησης, κατασκευής και απαρίθμησης διακριτών αντικειμένων και εμπίπτει στην τομή των Διακριτών Μαθηματικών και της Θεωρητικής Πληροφορικής. Μεγάλο μέρος της επιστήμης των υπολογιστών αφορά την επίλυση προβλημάτων όπου οι δομές είναι διακριτές, όπως για παράδειγμα τα προβλήματα γραφημάτων/δικτύων (μονοπάτια, ταιριάσματα, συνεκτικότητα, κλίκες, κ.α.), τα προβλήματα διακριτών πιθανοτήτων (απαρίθμηση των περιπτώσεων), η ανάλυση αλγορίθμων (πολυπλοκότητα, τυχαιότητα), η εξαντλητική αναζήτηση λύσεων σε προβλήματα βελτιστοποίησης (κατασκευές διατάξεων, συνδυασμών, διαμερίσεων κ.α.), η κατασκευή κωδίκων ανίχνευσης και διόρθωσης σφαλμάτων (δικτυωτά, μερικώς διατεταγμένα σύνολα), κατανόηση μεγάλων διακριτών δομών (διαδίκτυο, DNA, δευτεροταγείς δομές, ανθρώπινος εγκέφαλος).

Μάθημα επιλογής 4ου εξαμήνου

Ώρες διαλέξεων: Τετάρτη 15.15 - 18.00, Αίθουσα ΓΛ104 (Γρ. Λαμπράκη & Διστόμου).

Ώρες γραφείου: Κατόπιν συνεννοήσεως με τον διδάσκοντα.

Διδάσκων: Κων/νος Μανές, kmanes@unipi.gr, τηλ. γραφείου 210-4142313.

Τρόπος εξέτασης και αξιολόγησης:
Θα δοθούν απαλλακτικές προγραμματιστικές εργασίες (ατομικές ή ομαδικές).

Ύλη:

Συνδυαστικές κατασκευές

Αλγόριθμοι κατασκευής μεταθέσεων, διατάξεων, συνδυασμών, διαμερίσεων ακεραίων, διαμερίσεων συνόλων, δένδρων, μονοπατιών.

Backtracking, Κώδικες Gray, Ranking - Unranking, Τυχαία επιλογή

Μονοπάτια και δένδρα σε γραφήματα και δικτυωτά

Εφαρμογές του λήμματος Gessel - Viennot, Εφαρμογές της μεθόδου transfer-matrix, Δένδρα ζεύξης

Young tableaux

Αλγόριθμος RSK, Hook-length τύποι

Συνδυαστική απαρίθμηση

Συνδυαστικές απεικονίσεις, Γεννήτριες συναρτήσεις

Συγγράμματα μαθήματος:

1) Συνδυαστική Ανάλυση & Εφαρμογές 2, Ευάγγελος Φούντας, 2013
2) Συνδυαστική Ανάλυση & Εφαρμογές 1, Ευάγγελος Φούντας, 2013
3) Συνδυαστική απαρίθμηση, Χρόνης Μωϋσιάδης, 2002.

Προτεινόμενη Βιβλιογραφία:

1) D.L. Kreher, D.R. Stinson, Combinatorial Algorithms: Generation, Enumeration and Search, CRC press LTC, Florida (1998)

2) D. E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Addison-Wesley (2011)

3) F. Ruskey, Combinatorial generation (2003), available online at https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.93.5967.

4) A. Tucker, Applied Combinatorics, Wiley, 6th edition (2012)

5) T. Keller, T. Trotter, Applied Combinatorics, CreateSpace Independent Publishing Platform (2017)

6) E. A. Bender, S. G. Williamson, Foundations of Combinatorics with Applications, Dover Publications (2013)