ΕΠΑΝΑΛΗΠΤΙΚΕΣ ΑΣΚΗΣΕΙΣ ΑΕΠΠ 2017 (Ι)

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 δεν έχει αποδειχτεί, ούτε καταρριφθεί) και γιατί;

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

– Περατότητα

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

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

Ταληράκια

Γράψτε ένα πρόγραμμα σε Γλώσσα το οποίο να επιλύει το ακόλουθο πρόβλημα:

Θεωρείστε δύο (ίσως φανταστικούς) τύπους κερμάτων αξίας α1 και α2 λεπτών, όπου α1 και α2 είναι οποιοιδήποτε θετικοί ακέραιοι με τον περιορισμό α1α2. Θεωρείστε ακόμη έναν μη-αρνητικό ακέραιο c. Υπάρχει τρόπος επιλέγοντας κάποια ποσότητα (ίσως 0) από το ένα κέρμα και κάποια ποσότητα (ίσως 0) από το άλλο, το άθροισμα των αξιών αυτών των κερμάτων να είναι ίσο με c;

(υποθέστε ότι υπάρχει διαθέσιμο πλήθος κερμάτων κάθε τύπου όσο χρειαστεί)

Παράδειγμα:

Για αξίες κερμάτων 5 και 7 υπάρχει τρόπος να σχηματιστεί το ποσό 17, αλλά δεν υπάρχει τρόπος να σχηματιστεί το ποσό 23.

Λύση

psila

Η απόδειξη ορθότητας παραλείπεται ως άσκηση.

Ιστορικό σημείωμα

Το παραπάνω πρόβλημα στην γενική του μορφή, δηλαδή όχι μόνο για δύο τύπους κερμάτων, αλλά για οποιοδήποτε πεπερασμένο (θετικό ακέραιο) πλήθος κερμάτων (ανά δύο με άνισες αξίες) είναι γνωστό ως εκδοχή εφικτότητας του προβλήματος “κάνω ψιλά” (Change Making Problem – CMP). Ο καλύτερος αλγόριθμος ο οποίος έχει βρεθεί μέχρι τώρα για το τελευταίο αυτό πρόβλημα είναι πολύ αργός για την ανθρώπινη κλίμακα χρόνου για είναι χρήσιμος. Αν καταφέρνατε να βρείτε έναν «γρήγορο» αλγόριθμο γι’ αυτό το πρόβλημα, θα κερδίζατε το βραβείο του ενός εκατομμυρίου δολαρίων του Ινστιτούτου Μαθηματικών Clay, καθώς θα είχατε λύσει το μεγαλύτερο (ίσως) πρόβλημα πληροφορικής/μαθηματικών της εποχής μας και (ίσως) όλων των εποχών: το πρόβλημα “P versus NP”.

Άσκηση για εμβάθυνση

Θεωρείστε το παραπάνω πρόβλημα με τρεις (αντί για δύο) τύπους κερμάτων (με αξίες ανά δύο άνισες). Γράψτε ένα πρόγραμμα σε Γλώσσα για την επίλυση αυτού του προβλήματος.

Το κόσκινο του Ερατοσθένη

Τελευταία ενημέρωση: 5/10/2016

Πρόβλημα

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

1. Αν n<2 τερμάτισε – δεν υπάρχει πρώτος αριθμός μικρότερος του 2.

2. Γράψε κατά αύξουσα σειρά διάταξης όλους τους φυσικούς αριθμούς οι οποίοι είναι μεγαλύτεροι ή ίσοι του 2 και μικρότεροι ή ίσοι του n.

3. Διάγραψε όλα τα πολλαπλάσια του 2 (πχ επισημαίνοντάς τα με μια διαγώνια μολυβιά) τα οποία είναι μεγαλύτερα από το 2.

4.Βρες τον πρώτο (όσο αφορά την διάταξη) αριθμό που είναι μεγαλύτερος του 2 και δεν έχει διαγραφτεί – αν δεν υπάρχει τέτοιος αριθμός πήγαινε στο βήμα 5. Πήγαινε στο βήμα 3 και εκτέλεσέ το, αυτό και το επόμενο (το 4, δηλαδή το τρέχον), θεωρώντας αντί για τον αριθμό 2, τον αριθμό που βρήκες στην αρχή αυτού του βήματος.

5. Οι πρώτοι αριθμοί οι οποίοι είναι μικρότεροι ή ίσοι από τον n είναι οι αριθμοί που δεν είναι διαγραμμένοι.

Γράψτε ένα πρόγραμμα σε Γλώσσα το οποίο με εφαρμογή του παραπάνω αλγόριθμου εμφανίζει στην οθόνη όλους τους πρώτους αριθμούς οι οποίοι είναι μικρότεροι ή ίσοι από κάποιον φυσικό αριθμό n ≥ 2.

Λύση

eratosth

Η απόδειξη ορθότητας παραλείπεται ως άσκηση.

Ασκήσεις για εμβάθυνση

1) Γιατί θεωρείτε ότι ο παραπάνω αλγόριθμος ονομάζεται «κόσκινο»;

2) Τροποποιείστε το παραπάνω πρόγραμμα θεωρώντας ως δεδομένο ότι στο βήμα 3 του αλγόριθμου ο οποίος αναφέρεται στην διατύπωση του προβλήματος αρκεί να διαγραφτούν τα πολλαπλάσια του τρέχοντος αριθμού τα οποία είναι μεγαλύτερα ή ίσα από το τετράγωνο του τρέχοντος αριθμού, διότι τα υπόλοιπα έχουν ήδη διαγραφτεί πριν ο αλγόριθμος φτάσει σ’ αυτό το σημείο. Αν το τετράγωνο του τρέχοντος αριθμού είναι μεγαλύτερο από τον αριθμό n, ο αλγόριθμος πρέπει να μεταβαίνει στο βήμα 5.

Βίντεο