Επαναληπτικές ασκήσεις ΑΕΠΠ (I)

1) Ένας τετραγωνικός δισδιάστατος πίνακας S[ν,ν], όπου ν “τέλειο τετράγωνο” (δηλαδή η τετραγωνική του ρίζα είναι φυσικός αριθμός), είναι “πίνακας sudoku” όταν:

– Κάθε στοιχείο του S ανήκει στο σύνολο T={1,2,3,…,v}
– Κάθε γραμμή του S περιέχει κάθε στοιχείο του T.
– Κάθε στήλη του S περιέχει κάθε στοιχείο του T.

– Κάθε τετραγωνικός “υποπίνακας” με  γραμμές και στήλες του S, έτσι όπως οριοθετείται από τις έντονες διαχωριστικές γραμμές στο παρακάτω σχήμα/παράδειγμα για ν=9, περιέχει κάθε στοιχείο του Τ (σε κάθε πίνακα sudoku ν γραμμών και στηλών υπάρχουν ν τέτοιοι υποπίνακες).

                                                                                          
Πίνακας sudoku για ν=9, με εννέα τετραγωνικούς υποπίνακες τριών γραμμών και τριών στηλών

Κατασκευάστε μία συνάρτηση σε “Γλώσσα” η οποία να δέχεται ως παράμετρο έναν δισδιάστατο πίνακα 100 γραμμών και 100 στηλών, και να επιστρέφει Αληθής αν ο πίνακας είναι sudoku, αλλιώς Ψευδής. Μπορείτε να κατασκευάσετε και να χρησιμοποιήσετε όσες επιπλέον συναρτήσεις θέλετε.

2) Ορίζουμε “γειτονιά Moore ακτίνας 1” (στο εξής γειτονιά Moore) ενός στοιχείου ενός δισδιάστατου πίνακα, έναν δισδιάστατο πίνακα 9 στοιχείων, ο οποίος περιέχει τα αμέσως γειτονικά στοιχεία βόρεια, βορειοδυτικά, δυτικά, νοτιοδυτικά, νότια, νοτιοανατολικά, ανατολικά και βορειοανατολικά του αρχικού στοιχείου (του δισδιάστατου πίνακα), καθώς και το ίδιο το αρχικό στοιχείο.

                                                                      
Γειτονιά Moore του C: συνίσταται στα κόκκινα κελιά, καθώς και το ίδιο το κελί C (Πηγή: Wikipedia)

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

Κατασκευάστε μια διαδικασία η οποία δέχεται ως παράμετρο τον πίνακα λογικού τύπου Προηγούμενος[100,100] και επιστρέφει τον πίνακα λογικού τύπου Επόμενος[100,100], ο οποίος διαμορφώνεται με βάση τον ακόλουθο κανόνα:

Το τυχαίο στοιχείο του πίνακα Επόμενος, Επόμενος[i,j], ισούται με Αληθής, όταν το πλήθος των στοιχείων της γειτονιάς Moore του στοιχείου Προηγούμενος[i,j], από την οποία εξαιρούμε το στοιχείο Προηγούμενος[i,j], τα οποία έχουν την τιμή Αληθής είναι περιττός αριθμός.. Σε διαφορετική περίπτωση (αν είναι άρτιος αριθμός) ισούται με Ψευδής. Για τα στοιχεία εκείνα κάποιας γειτονιάς Moore, τα οποία υπερβαίνουν τα όρια του πίνακα, θεωρείστε τιμή ίση με Ψευδής.

3) Ένα χρώμα στον Η/Υ κωδικοποιείται συνήθως με μια τριάδα φυσικών αριθμών (r, g, b), όπου οι φυσικοί αριθμοί r(ed), g(reen), b(lue) ανήκουν συνήθως στο σύνολο {0, 1, 2, 3,…, 255} και ονομάζονται “συνιστώσες” του χρώματος. Για παράδειγμα η τριάδα (0, 0, 0) κωδικοποιεί το μαύρο χρώμα, η (255, 255, 255) το λευκό, η (255, 0, 0) το κόκκινο, κλπ. Μια ψηφιακή εικόνα κωδικοποιείται ως ένας δισδιάστατος πίνακας του οποίου κάθε στοιχείο είναι μια τριάδα (r, g, b) και αντιστοιχεί σε ένα στοιχειώδες τετραγωνίδιο της εικόνας (και της οθόνης του Η/Υ) γνωστό ως pixel (PICTureELement). Οι διαστάσεις αυτού του πίνακα ονομάζονται συνήθως “ανάλυση” της εικόνας (πχ 1024 ✕ 768). Ένας τρόπος για να αναπαρασταθεί στην “Γλώσσα” της ΑΕΠΠ  ένας δισδιάστατος πίνακας από τριάδες ακέραιων είναι ένας…τρισδιάστατος πίνακας ακέραιων. Για παράδειγμα για μια εικόνα με ανάλυση 1024 ✕ 768 μπορεί να χρησιμοποιηθεί ένας πίνακας Image[1024, 768, 3], όπου, για παράδειγμα, η συνιστώσα r του pixel στην 15η γραμμή και 25η στήλη του πίνακα δίνεται από το στοιχείο Image[15, 25, 1], η συνιστώσα g δίνεται από το Image[15, 25, 2], ενώ η συνιστώσα b από το Image[15, 25, 3].

Προκειμένου να μετατραπεί μια έγχρωμη εικόνα σε ασπρόμαυρη υπάρχουν διάφορες τεχνικές, από τις οποίες η πιο απλή (όχι όμως και η βέλτιστη) είναι η παρακάτω:

Σε κάθε pixel, κάθε συνιστώσα τίθεται ίση με το ακέραιο μέρος του μέσου όρου των συνιστωσών.

Κατασκευάστε μια διαδικασία η οποία δέχεται ως παράμετρο έναν τρισδιάστατο πίνακα διαστάσεων 1024,  768, 3 ο οποίος κωδικοποιεί μια έγχρωμη εικόνα και επιστρέφει έναν άλλον τρισδιάστατο πίνακα των ίδιων διαστάσεων ο οποίος κωδικοποιεί την μετατροπή της προηγούμενης σε ασπρόμαυρη.

4) Δίνεται το παρακάτω τμήμα προγράμματος, όπου η μεταβλητή κ είναι ακέραιου τύπου και στο σημείο έναρξης της δομής επανάληψης ΟΣΟ έχει τιμή μεγαλύτερη από 1:

Άραγε, το παραπάνω τμήμα προγράμματος πληρεί το κριτήριο της “περατότητας” αλγορίθμου για κάθε τιμή μεγαλύτερη του 1 της ακέραιας μεταβλητής κ αμέσως πριν την έναρξη της δομής επανάληψης; Με άλλα λόγια η δομή επανάληψης κατά την εκτέλεσή της τερματίζει μετά από πεπερασμένο πλήθος βημάτων, για κάθε αρχική τιμή του κ μεγαλύτερη από 1; Ο γνωστός μαθηματικός Erdos έχει δηλώσει σχετικά με το προηγούμενο ερώτημα ότι “τα μαθηματικά δεν είναι έτοιμα ακόμα για τέτοια προβλήματα”. Το πρόβλημα αυτό είναι γνωστό ως “εικασία του Collatz” (η εικασία είναι ότι η δομή επανάληψης τερματίζει για κάθε κ>1) και παραμένει άλυτο μέχρι και σήμερα.

Θεωρείστε τον παρακάτω αλγόριθμο σε φυσική γλώσσα με βήματα:

1. Αν το παραπάνω τμήμα προγράμματος πληρεί το κριτήριο της περατότητας για κάθε αρχική τιμή της μεταβλητής κ, πήγαινε στο βήμα 4.

2. Γράψε “ΟΧΙ”.

3. Πήγαινε στο βήμα 5.

4. Γράψε “ΝΑΙ”

5. Τέλος αλγορίθμου.

Ποιο/ποια από τα παρακάτω χαρακτηριστικά του αλγορίθμου παραβιάζει ο προηγούμενος αλγόριθμος (τουλάχιστον την δεδομένη χρονική στιγμή, όπου η εικασία του Collatz δεν έχει αποδειχτεί, ούτε καταρριφθεί) και γιατί;

– Αποτελεσματικότητα

– Περατότητα

– Καθοριστικότητα

Γιώργος Μπουγιούκας