Στην παρούσα εργασία προσεγγίζονται τα Sudoku puzzles χρησιμοποιώντας
μαθηματικές έννοιες κυρίως από την θεωρία γραφημάτων, την άλγεβρα, τη θεωρία
πινάκων αλλά και την κρυπτογραφία και τη θεωρία ανάπτυξης αλγορίθμων, oυσιαστικά
χρησιμοποιούνται διάφορες οπτικές γωνίες προκειμένου να απεικονιστεί η μελέτη
αυτών των puzzles μέσω των μαθηματικών.
Η εργασία χωρίζεται σε έξι βασικά κεφάλαια:
Το πρώτο κεφάλαιο περιέχει βασικές έννοιες της άλγεβρας και της θεωρίας
γραφημάτων, όπως ο ορισμός της ομάδας, του συνεκτικού γραφήματος, ο βαθμός
κορυφής και άλλα, οι οποίες χρησιμοποιούνται επανειλημμένα στην εργασία, έτσι ώστε
να μπορεί να γίνει κατανοητή χωρίς να απαιτείται η χρήση άλλων επιστημονικών
πηγών. Χωρίζεται σε τέσσερεις βασικές ενότητες οι οποίες παρουσιάζονται με την
ακόλουθη σειρά. Η πρώτη ενότητα είναι οι Βασικές Έννοιες Γραφημάτων, η οποία
ουσιαστικά αναφέρεται στην βασική ορολογία των γραφημάτων. Η δεύτερη ενότητα
είναι τα Βασικά Είδη Γραφημάτων και περιέχει γραφήματα με συγκεκριμένα
χαρακτηριστικά και ιδιότητες, οι οποίες είναι απαραίτητες για την ανάλυση της παρούσας εργασίας. Στη συνέχεια η τρίτη ενότητα είναι οι Βασικές Έννοιες Γραμμικής
Άλγεβρας, η οποία περιέχει συγκεκριμένους ορισμούς κυρίως των ομάδων και των
συμμετριών που χρησιμοποιούνται για την απαρίθμηση των Sudoku. Τέλος η τελευταία
ενότητα είναι οι Αλγεβρικές Ιδιότητες Γραφημάτων, η οποία περιέχει ορισμούς και
αλγεβρικές αλληλεπιδράσεις πάνω στα γραφήματα. Για περισσότερες λεπτομέρειες
σχετικά με την άλγεβρα και τη θεωρία γραφημάτων, παραπέμπουμε στα [6], [7] και [29].
Το δεύτερο κεφάλαιο περιέχει τους ορισμούς του Sudoku puzzle και των
λατινικών τετραγώνων, τα οποία είναι μια γενίκευση των Sudoku puzzles, όπως θα
αναφερθεί παρακάτω. Για εκτενέστερη έρευνα πάνω στα λατινικά τετράγωνα
παραπέμπουμε στα [3], [10], [11], [12],[13], [15], [16], [17], [18] και [29].
Στο τρίτο κεφάλαιο απαριθμούνται οι κλάσεις ισοδυναμίας των λατινικών
τετραγώνων αρχικά και στη συνέχεια γίνεται απαρίθμηση τριών ειδών Sudoku puzzles,
τα οποία είναι τα junior Sudoku puzzles τάξης 44, τα Sudoku puzzles τάξης 9x9 και
τα 2-Quasi-μαγικά Sudoku, τα οποία έχουν έναν παραπάνω περιορισμό σε σχέση με τα
συνήθη Sudoku. Τέλος, απαριθμούνται οι συμμετρίες των Sudoku puzzles τάξης 9x9 και
γίνεται μια σύντομη ανάλυση των μητρώων μετάθεσής τους. Περαιτέρω πληροφορίες
βρίσκονται στα [1], [2], [4], [5], [9], [14], [19], [20], [21], [22], και [26].
Στο τέταρτο κεφάλαιο αλλάζει η αυστηρά αλγεβρική προσέγγιση που υπάρχει
στις παραπάνω ενότητες. Εδώ παρουσιάζεται το Sudoku puzzle με μια ισοδύναμη
μορφή γραφήματος και γίνεται μια σύντομη παρουσίαση βασικών εννοιών της
κρυπτογραφίας, καθώς και μια θεωρητική προσέγγιση της κρυπτογράφησης του
Sudoku puzzle, με τη βοήθεια του πρωτοκόλλου της μηδενικής γνώσης. Περαιτέρω
πληροφορίες βρίσκονται στα [8], [23] και [24].
Στο πέμπτο κεφάλαιο αλλάζει πάλι ο επιστημονικός κλάδος, μέσω του οποίου
εξετάζουμε τα Sudoku puzzles και επικεντρώνεται στην απεικόνιση ενός στιγμιοτύπου
του puzzle Sudoku σε ένα στιγμιότυπο του προβλήματος SAT. Όλοι οι περιορισμοί του
Sudoku θα μπορέσουν να διατηρηθούν μέσω των κανονικών συζευκτικών προτάσεων
του προβλήματος SAT, οι οποίες έχουν χωριστεί σε πέντε ενότητες. Η καταμέτρηση των
κανονικών συζευκτικών προτάσεων του προβλήματος SAT μέσω αναδρομικών τύπων,
αποτελεί το πρωτότυπο τμήμα της διπλωματικής καθώς και η ανάλυση των τύπων
αυτών, την οποία περιέχει το επισυναπτόμενο CD. Για πιο θεωρητική προσέγγιση
προτείνονται τα [25], [26], [27], [30].
Το έκτο κεφάλαιο της εργασίας περιέχει μια διασκεδαστική εφαρμογή
κρυπτογράφησης οποιουδήποτε Sudoku puzzle τάξης 99 . Η εφαρμογή υλοποιείται με
τραπουλόχαρτα, έτσι ώστε ο αναγνώστης να είναι σε θέση να κρυπτογραφήσει
οποιοδήποτε λύση puzzle Sudoku, χωρίς να είναι υποχρεωμένος να παρουσιάσει τη
λύση του στον αντίπαλο, χρησιμοποιώντας μόνο τρείς τράπουλες. Ο στόχος του τελευταίου κεφαλαίου είναι να κάνει τον επίλογο της εργασίας πιο ευχάριστο και πιο
ανάλαφρο ακόμα και για νέους επιστήμονες στο χώρο της κρυπτογραφίας, της θεωρίας
γραφημάτων και της άλγεβρας. / The essay is about the complexity of the Sudoku puzzles and how you can numarated them.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/6500 |
| Date | 06 December 2013 |
| Creators | Ζώττου, Δήμητρα Νεφέλη |
| Contributors | Αλεβίζος, Παναγιώτης, Zottou, Dimitra Nefeli, Καββαδίας, Δημήτρης, Βραχάτης, Μηχάλης, Αλεβίζος, Παναγιώτης |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.003 seconds