Κεφάλαιο 3 - Δομές δεδομένων και αλγόριθμοι

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

Διδακτικοί στόχοι
Στόχοι του κεφαλαίου αυτού είναι οι μαθητές:

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

Ενότητες
3.1 Δεδομένα
3.2 Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα
3.3 Πίνακες
3.4 Στοίβα
3.5 Ουρά
3.6 Αναζήτηση
3.7 Ταξινόμηση

Κεφάλαιο 2 - Βασικές έννοιες αλγορίθμων

Εισαγωγικά
Αρχικά εξηγείται ο όρος αλγόριθμος και παραθέτονται τα σπουδαιότερα κριτήρια που πρέπει να πληρεί κάθε αλγόριθμος. Στη συνέχεια, η σπουδαιότητα των αλγορίθμων συνδυάζεται με την εξέλιξη της επιστήμης της Πληροφορικής. Η περιγραφή και η αναπαράσταση των αλγορίθμων δίνεται αναλυτικά με χρήση των μεθόδων αναπαράστασης ελεύθερου κειμένου, διαγραμμάτων ροής, φυσικής γλώσσας και κωδικοποίησης με πρόγραμμα. Τα προγράμματα παρουσιάζονται με τη μορφή ψευδογλώσσας, που ορίζεται και τυποποιείται σε ένα σύνολο εντολών και προγραμματιστικών ακολουθιακών ενοτήτων. Στη συνέχεια, δίνονται παραδείγματα όπου εξετάζονται οι διάφορες συνιστώσες ενός αλγορίθμου, δηλαδή οι απαραίτητες εντολές που στηρίζουν το 'χτίσιμο' ενός αλγορίθμου. Συγκεκριμένα, παρουσιάζονται η δομή ακολουθίας, η δομή επιλογής και η δομή επανάληψης. Για κάθε τύπο συνιστώσας δίνονται αναλυτικά παραδείγματα σε φυσική γλώσσα, σε ακολουθία διαδοχικών βημάτων και σε μορφή διαγραμμάτων ροής. Στο τέλος, παρουσιάζεται η ανάπτυξη και η αλγοριθμική προσέγγιση για την επίλυση ενός συνθετότερου προβλήματος, του προβλήματος του 'πολλαπλασιασμού αλά ρώσικα', όπου γίνεται χρήση και συνδυασμός αλγοριθμικών συνιστωσών.

Διδακτικοί στόχοι

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

Ενότητες
2.1 Τι είναι αλγόριθμος
2.2 Σπουδαιότητα αλγορίθμων
2.3 Περιγραφή και αναπαράσταση αλγορίθμων
2.4 Βασικές συνιστώσες/εντολές ενός αλγορίθμου
2.4.1 Δομή ακολουθίας
2.4.2 Δομή επιλογής
2.4.3 Διαδικασίες πολλαπλών επιλογών
2.4.4 Εμφωλευμένες Διαδικασίες
2.4.5 Δομή επανάληψης

Κεφάλαιο 1 - Ανάλυση προβλήματος

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

Διδακτικοί στόχοι

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

Ενότητες
1.1 Η έννοια πρόβλημα
1.2 Κατανόηση προβλήματος
1.3 Δομή προβλήματος
1.4 Καθορισμός απαιτήσεων
1.5 Κατηγορίες προβλημάτων
1.6 Πρόβλημα και υπολογιστής

Λίγα λόγια για το μάθημα...

Το μάθημα “Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον” έχει σαν γενικό σκοπό οι μαθητές να αναπτύξουν αναλυτική και συνθετική σκέψη, να αποκτήσουν ικανότητες μεθοδολογικού χαρακτήρα και να μπορούν να επιλύουν απλά σχετικά προβλήματα.

Το σχολικό βιβλίο καλύπτει όλη τη θεωρητική πλευρά του μαθήματος. Περιλαμβάνει 14 κεφάλαια, που μπορούν να χωριστούν σε δύο μέρη. Το πρώτο μέρος (κεφάλαια 1-5) αναφέρεται στις ενότητες Ανάλυση Προβλήματος και Σχεδίαση Αλγορίθμου, όπου η έμφαση δίνεται στην ανάπτυξη δεξιοτήτων αλγοριθμικής προσέγγισης των προβλημάτων. Το δεύτερο μέρος (κεφάλαια 6-14) αφιερώνεται στην υλοποίηση προγραμμάτων τόσο σε περιβάλλον γλωσσών προγραμματισμού υψηλού επιπέδου όσο και σε αντικειμενοστραφές. Τα δύο αυτά μέρη του βιβλίου δεν είναι ανεξάρτητα μεταξύ τους. Συνήθως ο σκοπός της δημιουργίας ενός αλγορίθμου είναι στη υνέχεια η κατασκευή ενός προγράμματος. Σε επόμενη ανάρτηση του παρόντος ιστολογίου, υπάρχει αναλυτικά η ύλη εξετάσεων για την φετινή σχολική χρονιά.

Το μάθημα προσφέρει στο μαθητή όλες τις γνώσεις και πληροφορίες που είναι απαραίτητες, ώστε αυτός να κατανοήσει με ευκολία, ακρίβεια και σαφήνεια τις βασικές έννοιες αλγοριθμικής και προγραμματισμού. Η προσέγγιση των εννοιών γίνεται μέσα από πολλά παραδείγματα σε συσχέτιση με άλλα μαθήματα και γνωστικά αντικείμενα. Κατά το μάθημα δεν θα αναλυθούν τεχνικές ή άλλες λεπτομέρειες συγκεκριμένου λογισμικού (γλωσσών προγραμματισμού). Ωστόσο δεν θα αποφευχθούν κάποιες αναφορές σε γνωστά προγραμματιστικά περιβάλλοντα, που γίνονται για λόγους πληρότητας. Η ανάπτυξη των προγραμμάτων που αναφέρονται ως παραδείγματα, γίνεται σε μια υποθετική γλώσσα προγραμματισμού, η οποία βέβαια ακολουθεί τις γενικές αρχές των σύγχρονων πραγματικών γλωσσών προγραμματισμού. Η υποθετική αυτή γλώσσα αποκαλείται ΓΛΩΣΣΑ και όπως θα γίνει αμέσως φανερό, η μετατροπή ενός προγράμματος από τη ΓΛΩΣΣΑ σε μια πραγματική γλώσσα προγραμματισμού είναι απλή υπόθεση.

Η έννοια του αλγορίθμου

Η θεωρία των αλγορίθμων έχει μεγάλη παράδοση και η ηλικία μερικών αλγορίθμων αριθμεί χιλιάδες χρόνια, όπως για παράδειγμα ο αλγόριθμος του Ευκλείδη για την εύρεση του μέγιστου κοινού διαιρέτη δύο αριθμών ή το λεγόμενο κόσκινο του Ερατοσθένη για την εύρεση των πρώτων αριθμών από 1 ως n. Σήμερα το πεδίο της Θεωρίας Αλγορίθμων είναι ένα ιδιαίτερα ευρύ και πλούσιο πεδίο. Πληθώρα συγγραμμάτων έχει εμφανισθεί στη βιβλιογραφία, ενώ συνεχίζεται η περαιτέρω εμβάθυνση σε νέα σύγχρονα προβλήματα. Οι περισσότεροι από τους αλγορίθμους που συνήθως εξετάζονται στα σχετικά βιβλία έχουν προταθεί τα τελευταία 25 χρόνια, όση περίπου είναι και η ηλικία της Πληροφορικής ως μίας νέας αυθύπαρκτης επιστήμης.

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

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

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

• να συγκεντρώσουμε τα υλικά,
• να προετοιμάσουμε τα σκεύη μαγειρικής,
• να παρασκευάσουμε το φαγητό,
• να ετοιμάσουμε τη σαλάτα,
• να στρώσουμε το τραπέζι,
• να γευματίσουμε,
• να καθαρίσουμε το τραπέζι, και
• να πλύνουμε τα πιάτα και τα κουζινικά.

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

Η έννοια του προγράμματος

Η επίλυση ενός προβλήματος με τον υπολογιστή περιλαμβάνει τρία εξίσου σημαντικά στάδια:

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

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

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

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

Ύλη εξετάσεων για Ενιαία Λύκεια

Σύμφωνα με την εγκύκλιο 99964/Γ2/29-9-2006, από το βιβλίο "Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον" των Α. Βακάλη, Η. Γιαννόπουλου, Ν. Ιωαννίδη, Χ. Κοίλια, Κ. Μάλαμα, Ι. Μανωλόπουλου, Π. Πολίτη, έκδοση Ο.Ε.Δ.Β. 2006, η ύλη για το σχολικό έτος 2009 - 2010 είναι:

1. Ανάλυση προβλήματος
1.1 Η έννοια πρόβλημα
1.2 Κατανόηση προβλήματος
1.3 Δομή προβλήματος
1.4 Καθορισμός απαιτήσεων
1.5 Κατηγορίες προβλημάτων
1.6 Πρόβλημα και υπολογιστής

2. Βασικές Έννοιες Αλγορίθμων
2.1 Τι είναι αλγόριθμος
2.2 Σπουδαιότητα αλγορίθμων
2.3 Περιγραφή και αναπαράσταση αλγορίθμων
2.4 Βασικές συνιστώσες/εντολές ενός αλγορίθμου
2.4.1 Δομή ακολουθίας
2.4.2 Δομή επιλογής
2.4.3 Διαδικασίες πολλαπλών επιλογών
2.4.4 Εμφωλευμένες Διαδικασίες
2.4.5 Δομή επανάληψης

3. Δομές Δεδομένων και Αλγόριθμοι
3.1 Δεδομένα
3.2 Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα
3.3 Πίνακες
3.4 Στοίβα
3.5 Ουρά
3.6 Αναζήτηση
3.7 Ταξινόμηση

6. Εισαγωγή στον προγραμματισμό
6.1 Η έννοια του προγράμματος
6.2 Ιστορική αναδρομή
6.2.1 Γλώσσες Μηχανής
6.2.2 Συμβολικές γλώσσες ή γλώσσες χαμηλού
επιπέδου
6.2.3 Γλώσσες υψηλού επιπέδου
6.2.4 Γλώσσες 4ης γενιάς
6.3 Φυσικές και τεχνητές γλώσσες
6.4 Τεχνικές σχεδίασης προγραμμάτων
6.4.1 Ιεραρχική σχεδίαση προγράμματος
6.4.2 Τμηματικός προγραμματισμός
6.4.3 Δομημένος προγραμματισμός
6.7 Προγραμματιστικά περιβάλλοντα

7. Βασικά στοιχεία προγραμματισμού
7.1 Το αλφάβητο της ΓΛΩΣΣΑΣ
7.2 Τύποι Δεδομένων
7.3 Σταθερές
7.4 Μεταβλητές
7.5 Αριθμητικοί τελεστές
7.6 Συναρτήσεις
7.7 Αριθμητικές εκφράσεις
7.8 Εντολή εκχώρησης
7.9 Εντολές εισόδου-εξόδου
7.10 Δομή προγράμματος

8. Επιλογή και επανάληψη
8.1 Εντολές επιλογής
8.1.1 Εντολή ΑΝ
8.1.2 Εντολή ΕΠΙΛΕΞΕ
8.2 Εντολές επανάληψης
8.2.1 Εντολή ΟΣΟ...ΕΠΑΝΑΛΑΒΕ
8.2.2 Εντολή ΜΕΧΡΙΣ_ΟΤΟΥ
8.2.3 Εντολή ΓΙΑ...ΑΠΟ...ΜΕΧΡΙ

9. Πίνακες
9.1 Μονοδιάστατοι πίνακες
9.2 Πότε πρέπει να χρησιμοποιούνται πίνακες
9.3 Πολυδιάστατοι πίνακες
9.4 Τυπικές επεξεργασίες πινάκων

10. Υποπρογράμματα
10.1 Τμηματικός προγραμματισμός
10.2 Χαρακτηριστικά των υποπρογραμμάτων
10.3 Πλεονεκτήματα του τμηματικού προγραμματισμού
10.4 Παράμετροι
10.5 Διαδικασίες και συναρτήσεις
10.5.1 Ορισμός και κλήση συναρτήσεων
10.5.2 Ορισμός και κλήση διαδικασιών
10.5.3 Πραγματικές και τυπικές παράμετροι


Οι ενότητες 3.4, 3.5 εξετάζονται μόνο ως θεωρία.
ΣΗΜΕΙΩΣΗ: Οι μαθητές θα μπορούν να διατυπώνουν τις λύσεις των ασκήσεων των εξετάσεων είτε σε οποιαδήποτε μορφή παράστασης αλγορίθμου είτε σε "ΓΛΩΣΣΑ" όπως αυτή ορίζεται και χρησιμοποιείται στο διδακτικό εγχειρίδιο.