Σημειώσεις θεωρίας ΑΕΠΠ

ΚΕΦΑΛΑΙΟ 1  Πρόβλημα - Ανάλυση προβλήματος

1.  H έννοια πρόβλημα:

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

2.  Δεδομένο - Επεξεργασία δεδομένων- Πληροφορία

Δεδομένο:

Είναι οποιοδήποτε στοιχείο που μπορεί να γίνει αντιληπτό από έναν τουλάχιστον παρατηρητή με μία από τις πέντε αισθήσεις του.

Επεξεργασία δεδομένων:

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

Πληροφορία:

Είναι το αποτέλεσμα της σωστής επεξεργασίας δεδομένων.

3.  Δομήενός προβλήματος:

Με τον όρο «δομή προβλήματος», εννοούμε τα συστατικά μέρη του προβλήματος, τα επιμέρους τμήματα που το αποτελούν (υποπροβλήματα) καθώς επίσης και τον τρόπο που αυτά τα μέρη συνδέονται μεταξύ τους.

4.  Ποιά είναι τα στάδια αντιμετώπισης ενός προβλήματος;
α. Κατανόηση:

Σωστή και πλήρης αποσαφήνιση των δεδομένων και των ζητουμένων του προβλήματος. Η κατανόηση του προβλήματος προϋποθέτει:

?    σωστή διατύπωση του προβλήματος εκ? μέρους του δημιουργού του

?    σωστή ερμηνεία εκ΄ μέρους εκείνου που καλείται να το λύσει

   β. Ανάλυση:

Το αρχικό πρόβλημα διασπάται σε άλλα επί μέρους απλούστερα προβλήματα.

   γ. Επίλυση:

      Υλοποίηση της λύσης, μέσω της επίλυσης των επιμέρους προβλημάτων.

5.  Κατηγοριοποίηση προβλημάτων:

     Μία πρώτη κατηγοριοποίηση γίνεται ως προς τη δυνατότητα επίλυσης. ΄Ετσι

       κάθε πρόβλημα ανήκει σε μία απ? τις 3 παρακάτω κατηγορίες:

?    Επιλύσιμο(μπορεί να λυθεί, πχ: εξίσωση β' βαθμού)

?    Ανοικτό(δεν έχει ακόμα βρεθεί η λύση, αλλά δεν έχει αποδειχτεί ότι δεν

επιδέχεται λύση, πχ: υπάρχουν εξωγήινοι;)

?    Άλυτο(έχει αποδειχτεί ότι δεν λύνεται, πχ: τετραγωνισμός του κύκλου)

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

α) Ως προς τον βαθμό δόμησης του προβλήματος:

?    Δομημένα(όσων η επίλυση προέρχεται από μία αυτοματοποιημένη διαδικασία πχ: ρίζες τριωνύμου)

?    Ημιδομημένα(όσων η λύση επιδιώκεται στα πλαίσια ενός εύρους πιθανών λύσεων, αφήνοντας στον άνθρωπο περιθώρια επιλογής της πχ.: συμπλήρωση μηχανογραφικού)

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

β) Ως προς το είδος της λύσης του προβλήματος:

?    απόφασης(πχ. επιλογή επαγγέλματος)

?    υπολογιστικά(απαιτείται η διενέργεια υπολογισμών για να λυθεί το πρόβλημα)

?    βελτιστοποίησης(Το πρόβλημα επιζητά όχι απλώς λύση, αλλά βέλτιστο αποτέλεσμα για κάποια συγκεκριμένα δεδομένα)

ΚΕΦΑΛΑΙΟ 1 ? Πρόβλημα και Υπολογιστής

1.   Βασικές λειτουργίες Η/Υ:

Οι Υπολογιστές είναι μηχανές, που μπορούν να λύνουν προβλήματα αξιοποιώντας τις 3 βασικές λειτουργίες τους:

?    Πρόσθεση  (κατά συνέπεια και τις άλλες αριθμητικές πράξεις)

?    Σύγκριση  (βασική λειτουργία για την εκτέλεση λογικών πράξεων)

Όσον αφορά στις αριθμητικές πράξεις που χρησιμοποιούνται στους αλγορίθμους και

στα προγράμματα:

- Οι πράξεις ορίζονται από τελεστές και τελεστέους.

- Υπάρχουν τρείς κατηγορίες τελεστών:

?     Αριθμητικοί (+, -, *, /, ^, div, mod)

Ο τελεστής ^ χρησιμοποιείται για ύψωση σε δύναμη (π.χ. 10^2 = 10 * 10)

Ο τελεστής divχρησιμοποιείται για ακέραια διαίρεση (π.χ. 9 div 2 = 4), ενώ ο modεπιστρέφει το υπόλοιπο ακέραιας διαίρεσης (π.χ. 9 mod 2 = 1)

?     Συγκριτικοί (>, <, <>, >=, <=, =)

?     Λογικοί (Ή, ΚΑΙ, ΟΧΙ)

- Ανάλογα με την κατηγορία του τελεστή χρησιμοποιούμε και αντίστοιχους τελεστέους:

?     Οι αριθμητικές πράξεις γίνονται με αριθμούς ή/και μεταβλητές (που συμβολίζουν αριθμούς).

?     Οι συγκρίσεις γίνονται μεταξύ αριθμών ή μεταξύ αλφαριθμητικών (ή/και μεταξύ αντίστοιχων μεταβλητών.)

2.  Λόγοι ανάθεσης επίλυσης προβλημάτων στον Η/Υ:

Οι λόγοι που αναθέτουμε την επίλυση προβλημάτων σε υπολογιστές σχετίζονται με:

?    την πολυπλοκότητα των υπολογισμών

?    την επαναληπτικότητα των διαδικασιών

?    την ταχύτητα εκτέλεσης των πράξεων

?    το μεγάλο πλήθος των δεδομένων

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

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

ΚΕΦΑΛΑΙΟ 2 ? Βασικές έννοιες αλγορίθμων

1.  Ορισμός αλγορίθμου

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

2.  Χαρακτηριστικά  αλγορίθμων

?    Είσοδος: Να έχει καμία, μία ή περισσότερες  εισόδους (τα δεδομένα του αλγορίθμου).

?    Εξοδος: Να έχει τουλάχιστον μία έξοδο (αποτέλεσμα/-σματα).

?    Καθοριστικότητα: για κάθε εντολή πρέπει να είναι σαφής ο τρόπος εκτέλεσής της.

?    Περατότητα: Ο αλγόριθμος πρέπει να τελειώνει σε πεπερασμένο χρόνο.

?    Αποτελεσματικότητα: Κάθε εντολή να είναι απλή και εκτελέσιμη.

3.  Τρόποι αναπαράστασης αλγορίθμων

?    Ελεύθερο κείμενο: Σαν μια έκθεση

?    Δαγραμματικές τεχνικές: Γραφικός τρόπο παρουσίασης ενός αλγορίθμου. Οι εντολές παριστάνονται με ειδικά σύμβολα, που το καθένα έχει τη σημασία του.

?    Φυσική γλώσσα κατά βήματα: Χρησιμοποιούμε απλή ελληνική γλώσσα με αριθμημένες παραγράφους. Αποτελεί μια πιο δομημένη μορφή από το ελεύθερο κείμενο. Υπάρχει ο κίνδυνοςνα παραβιαστεί το κριτήριο της καθοριστικότητας.

?    Κωδικοποίηση: Χρησιμοποιούμε μιααλγοριθμική γλώσσα, η οποία έχει αυστηρά καθορισμένο λεξιλόγιο, γραμματική και συντακτικό.

Στις σημειώσεις αυτές - όπως και στο σχολικό βιβλίο - θα χρησιμοποιούμε την Κωδικοποίηση και τις Διαγραμματικές τεχνικές (ή λογικά διαγράμματα).

4.  Συστατικά στοιχεία αλγορίθμων

Οι αλγόριθμοι χρησιμοποιούνται για να λύνουν όχι ένα συγκεκριμένο πρόβλημα (π.χ. τον υπολογισμό του εμβαδού ενός κύκλου με ακτίνα 1,45 m) αλλά πολλά ίδια προβλήματα (π.χ. τον υπολογισμό του εμβαδού οποιουδήποτε κύκλου). Για τον λόγο αυτό χρησιμοποιούμε ΜΕΤΑΒΛΗΤΕΣ, οι τιμές των οποίων διαβάζονται κατά την εκτέλεση ? και όχι κατά το δημιουργία ? του αλγορίθμου.

 Ο Υπολογιστής ? όπως είδαμε στο Κεφ.1, μπορεί να κάνει 3 πράγματα:

• Να μεταφέρει δεδομένα
• Να εκτελεί αριθμητικές πράξεις
• Να κάνει συγκρίσεις και λογικές Πράξεις

Κατά τη σύνταξη ενός αλγορίθμου χρησιμοποιούμε αντίστοιχες εντολές για τις παραπάνω λειτουργίες:

• Για την μεταφορά δεδομένων απ? το πληκτρολόγιο χρησιμοποιείται η εντολή ΔΙΑΒΑΣΕ (εισαγωγή δεδομένων δηλ. είσοδος αλγορίθμου), ακολουθούμενη από μία μεταβλητή.
• Για την μεταφορά δεδομένων απ? την κεντρική μονάδα του Η/Υ προς την οθόνη χρησιμοποιείται η εντολή ΕΚΤΥΠΩΣΕ (εξαγωγή αποτελεσμάτων δηλ. έξοδος αλγορίθμου), ακολουθούμενη από ένα μήνυμα και/ή μία μεταβλητή.
• Για την εκτέλεση αριθμητικών πράξεων χρησιμοποιείται η εκχώρηση τιμής.
• Για την εκτέλεση συγκρίσεων χρησιμοποιείται η εντολή ΑΝ ακολουθούμενη (πάντα!) από μια σύγκριση ? απλή ή σύνθετη ?. Στη συνέχεια μπαίνει η λέξη ΤΟΤΕ ακολουθούμενη από άλλες εντολές (μία ή και περισσότερες?). Η εντολή ΑΝ κλείνει/τελειώνει πάντα με την εντολή ΤΕΛΟΣ_ΑΝ.

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

 Εκτός των εντολών, κάθε αλγόριθμος μπορεί να περιέχει:

• Μεταβλητές. Κάθε μεταβλητή παριστάνει ένα δεδομένο ή ένα ενδιάμεσο αποτέλεσμα ή ένα τελικό αποτέλεσμα. Η τιμή μιας μεταβλητής μπορεί να αλλάξει μέσα στον αλγόριθμο. Το όνομα κάθε μεταβλητής το ορίζει αυτός που γράφει τον αλγόριθμο. Είναι ένα όνομα (χωρίς κενά ή σύμβολα) και δεν αλλάζει ως το τέλος του αλγορίθμου. Κάθε αλγόριθμος περιέχει τόσες μεταβλητές, όσα είναι τα:

δεδομένα + τα ενδιάμεσα αποτελέσματα + τα τελικά αποτελέσματα.

• Σταθερές. Κάποιο δεδομένο που δεν αλλάζει τιμή, καταχωρείται σε μια σταθερά (π.χ. Π=3,14).
• Εκφράσεις (με τις οποίες πραγματοποιείται η απόδοση τιμής σε μεταβλητές)

Αν θέλουμε να δώσουμε/αλλάξουμε τιμή σε μια μεταβλητή χρησιμοποιούμε έναν τύπο υπολογισμού. Για παράδειγμα Ε=βάση*ύψος/2. Θα συνηθίσουμε όμως αντί του συμβόλου = να χρησιμοποιούμε σαν σύμβολο «εκχώρησης τιμής», το ? δηλ. Ε?βάση*ύψος/2. Το μέρος δεξιά του ??? ονομάζεται έκφραση. Μια έκφραση μπορεί να είναι μια σταθερά ή μια μεταβλητή ή ένας αριθμητικός υπολογισμός που θα χρησιμοποιεί τελεστές (+, -, *, /,^, div, mod) και τελεστέους (σταθερές ή/και μεταβλητές).Αριστερά του ??? υπάρχει ΠΑΝΤΑ μια μεταβλητή.

5.  Ας δούμε τα παραπάνω στην πράξη ? Παραδείγματα αλγορίθμων

Παράδειγμα _1  ?  Δομή ακολουθίας

Παράδειγμα _2  ?  Δομή επιλογής

Το Παράδειγμα _2  με διαγραμματική αναπαράσταση

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

Αντίθετα στο Παράδειγμα _2  η εντολή  x?x*(-1) θα εκτελεστεί μόνο αν ισχύει η συνθήκη x<0 (δομή επιλογής).

Παράδειγμα _3  ?  Δομή επιλογής

ΑΛΓΟΡΙΘΜΟΣ Βαθμοί

ΔΙΑΒΑΣΕ  α, β, γ

ΜΟ=(α+β)/2

ΜΟ=(ΜΟ+γ)/2

ΑΝ ΜΟ<9,5  ΤΟΤΕ

     ΓΡΑΨΕ ?Απορρίπτεται?

ΑΛΛΙΩΣ

     ΓΡΑΨΕ ?Προάγεται?

ΤΕΛΟΣ Βαθμοί

Παράδειγμα _4  ?  Δομή επιλογής

ΑΛΓΟΡΙΘΜΟΣ τριώνυμο

ΔΙΑΒΑΣΕ  α, β, γ

Δ=β*β-4*α*γ

ΑΝ Δ<0 ΤΟΤΕ

     ΓΡΑΨΕ ?Δεν έχει ρίζες?

ΑΛΛΙΩΣ_ΑΝ  Δ=0 ΤΟΤΕ

     χ=-β/2*α

     ΓΡΑΨΕ χ

ΑΛΛΙΩΣ

     χ1=-β+Τ_Ρ(Δ)/(2*α)

     χ1=-β-Τ_Ρ(Δ)/(2*α)

     ΓΡΑΨΕ χ1,χ2

ΤΕΛΟΣ_ΑΝ

ΤΕΛΟΣ τριώνυμο

6. Πολλαπλασιασμός αλά Ρωσικά - Ολίσθηση

Ο υπολογιστής δεν χρησιμοποιεί για την πράξη του πολλαπλασιασμού τη μέθοδο που χρησιμοποιούμε εμείς, αλλά τη λεγόμενη  «πολλαπλασιασμός αλά Ρωσικά». Η μέθοδος αυτή λειτουργεί χειρωνακτικά ως εξής:

 Έστω, πως θέλουμε να πολλαπλασιάσουμε τους αριθμούς (θετικούς, ακέραιους) Α=32 & Β=18.

Γράφουμε τους αριθμούς δίπλα-δίπλα (σε δυό στήλες) 

     Α                  Β

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

Ελέγχουμε αν ο Β είναι περιττός και αν ναι, μεταφέρουμε τον αριθμό Α στην τρίτη στήλη.

1. Δημιουργούμε επόμενη σειρά αριθμών υποδιπλασιάζοντας τον Β (ακέραια διαίρεση με το 2, δηλ. ο Β γίνεται Β div 2) και διπλασιάζοντας τον Α.
2. Επαναλαμβάνουμε τα βήματα 1. & 2. μέχρις ότου ο αριθμός Β να γίνει 1 (μονάδα).
3. Το άθροισμα των αριθμών της τρίτης στήλης είναι το γινόμενο των αριθμών Α & Β.

      Α                 Β

Η μέθοδος αυτή χρησιμοποιείται στους υπολογιστές, γιατί υλοποιείται ευκολότερα. Οι υπολογιστές μπορούν πολύ εύκολα να υποδιπλασιάσουν και να διπλασιάσουν έναν αριθμό.  Στη μνήμη του υπολογιστή οι αριθμοί (όπως και τα δεδομένα γενικότερα), αποθηκεύονται με δυαδική μορφή. Π.χ. ο αριθμός 13 αποθηκεύεται ως εξής:

 Αν ο δυαδικός αριθμός (1101) μετακινηθεί μια θέση δεξιά προκύπτει ο αριθμός 6 (13 div 2):

ενώ αν ο ίδιος αριθμός (1101) μετακινηθεί μια θέση αριστερά προκύπτει ο αριθμός 26 (το διπλάσιό του):

Αυτές οι μετακινήσεις (δεξιά ή αριστερά) ενός αριθμού στη μνήμη του υπολογιστή, ονομάζονται ολίσθηση. Άρα:

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

ΚΕΦΑΛΑΙΟ 3 & 9 ? Δομές δεδομένων / ΠΙΝΑΚΕΣ

1.  Δεδομένο - Επεξεργασία δεδομένων- Πληροφορία

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

?    Οι Αλγόριθμοι είναι το μέσο για την επεξεργασία των δεδομένων, με σκοπό την παραγωγή πληροφοριών.

?    Ένας ιδιαίτερος κλάδος της πληροφορικής, η «θεωρία των πληροφοριών» (informationtheory), ασχολείται με τη μελέτη της μέτρησης, της κωδικοποίησης και της μετάδοσης της πληροφορίας.

 2.  Δομές δεδομένων

Μια δομή δεδομένων είναι ένα σύνολο αποθηκευμένων δεδομένων, που υφίστανται επεξεργασία από ένα σύνολο λειτουργιών.

?    Τα δεδομένα ενός προβλήματος αποθηκεύονται στον υπολογιστή, είτε στην κύρια μνήμη του είτε στην δευτερεύουσα.

?    Η αποθήκευση δεν γίνεται κατά ένα τυχαίο τρόπο αλλά συστηματικά, δηλαδή χρησιμοποιώντας μία δομή.

?    Κάθε μορφή δομής δεδομένων αποτελείται από ένα σύνολο κόμβων.

?    Οι βασικές λειτουργίες επί των δομών δεδομένων είναι οι εξής:

• Προσπέλαση
• Εισαγωγή
• Διαγραφή
• Αναζήτηση
• Ταξινόμηση
• Αντιγραφή
• Συγχώνευση
• Διαχωρισμός
• Οι δομές αυτές δεν έχουν σταθερό μέγεθος, αλλά ο αριθμός των κόμβων τους μεγαλώνει καθώς εισάγονται νέα δεδομένα και μικραίνει καθώς διαγράφονται.
• Δεν αποθηκεύονται σε συνεχόμενες θέσεις μνήμης, αλλά στηρίζονται στην τεχνική της δυναμικής παραχώρησης μνήμης.
• Όλες οι σύγχρονες γλώσσες προγραμματισμού τις υποστηρίζουν.
  
  • Το ακριβές μέγεθός τους καθορίζεται κατά την στιγμή του προγραμματισμού και όχι κατά την στιγμή της εκτέλεσης του προγράμματος.
  • Οι κόμβοι τους αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.
  • Στην πράξη οι στατικές δομές υλοποιούνται με πίνακες.
  • Στους πίνακες σαν κόμβοι θεωρούνται οι θέσεις του πίνακα
    • Ώθηση (push) ενός στοιχείου στην κορυφή της στοίβας.
    • Απώθηση (pop) ενός στοιχείου από την κορυφή της στοίβας.
    • Μπορεί να υλοποιηθεί με την βοήθεια ενός μονοδιάστατου πίνακα καθώς και μίας βοηθητικής μεταβλητής (δείκτης) με το όνομα top , η οποία δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στην κορυφή της στοίβας.
    • Για την ώθηση ενός νέου στοιχείου στην στοίβα πρώτα αυξάνεται η μεταβλητή top κατά ένα και μετά στην θέση αυτή αποθηκεύεται το στοιχείο. Η διαδικασία της ώθησης πρέπει οπωσδήποτε να ελέγχει αν η στοίβα είναι γεμάτη αλλιώς λέγεται ότι συμβαίνει υπερχείλιση ().
    • Για την απώθηση ενός στοιχείου από την στοίβα απωθείται πρώτα το στοιχείο από την θέση top και μετά μειώνεται η top κατά ένα. Η διαδικασία της απώθησης πρέπει οπωσδήποτε να ελέγχει αν υπάρχει τουλάχιστον ένα στοιχείο στην στοίβα αλλιώς λέγεται ότι συμβαίνει υποχείλιση (underflow).
    • Εισαγωγή ενός στοιχείου στο πίσω άκρο της ουράς.
    • Εξαγωγή ενός στοιχείου από το εμπρός άκρο της ουράς.
    • Μπορεί να υλοποιηθεί με την βοήθεια ενός μονοδιάστατου πίνακα και με δύο μεταβλητές (δείκτες) με τα ονόματα rear και front. Ο δείκτης front δείχνει την θέση του στοιχείου που σε πρώτη ευκαιρία θα εξαχθεί. Ο δείκτης rear δείχνει την θέση του τελευταίου στοιχείου της ουράς.
    • Για την εισαγωγή ενός νέου στοιχείου στην ουρά πρώτα αυξάνεται ο δείκτης rear κατά ένα και μετά στην θέση αυτή αποθηκεύεται το στοιχείο.
    • Για την εξαγωγή ενός στοιχείου από την ουρά εξέρχεται πρώτα το στοιχείο από την θέση front και μετά μειώνεται η front κατά ένα.
      • Επιστημονικής κατεύθυνσης (π.χ. Fortan)
      • Εμπορικής κατεύθυνσης (π.χ. Cobol)
        • να εισάγουν δεδομένα
        • να εκτελέσουν υπολογισμούς
        • να μεταβάλλουν τις τιμές των μεταβλητών
        • να τυπώσουν αποτελέσματα
        • Πραγματικές παράμετροι ονομάζονται οι μεταβλητές που χρησιμοποιούνται κατά την κλήση του υποπρογράμματος.
        • Τυπικές παράμετροι ονομάζονται οι μεταβλητές του υποπρογράμματος που δέχονται τιμές.
        • Ο αριθμός των πραγματικών και των τυπικών παραμέτρων πρέπει να είναι ίδιος.
        • Κάθε πραγματική παράμετρος αντιστοιχεί στην τυπική παράμετρο που βρίσκεται στην αντίστοιχη θέση.
        • Η τυπική παράμετρος και η αντίστοιχη της πραγματική παράμετρος πρέπει να είναι του ίδιου τύπου.

Στην πράξη σπάνια χρησιμοποιούνται και οι 8 λειτουργίες για κάποια δομή.

?    Οι αλγόριθμοι και τα δεδομένα είναι μια αδιάσπαστη ενότητα:

Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα

            
3.  Κατηγορίες δομών δεδομένων

?    Δυναμικές δομές

?    Στατικές δομές

4.  Ορισμός Πίνακα

     Πίνακας είναι ένα σύνολο αντικειμένων (ή στοιχείων) του ιδίου τύπου, τα οποία  

     αναφέρονται με ένα κοινό όνομα.

?     Τα στοιχεία κάθε πίνακα είναι αριθμημένα (1 μέχρι μήκος πίνακα).

?     Δεν αναφερόμαστε ποτέ στον πίνακα συνολικά, αλλά σε συγκεκριμένο στοιχείο του. Η αναφορά γίνεται χρησιμοποιώντας το όνομα του πίνακα, ακολουθούμενο από αγκύλες, που περιέχουν τον δείκτη του στοιχείου.

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

5.  Είναι χρήσιμοι οι πίνακες;

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

6.  Μειονεκτήματα της χρήσης των πινάκων

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

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

7.  Τυπικές επεξεργασίες πινάκων

?    Ο υπολογισμός αθροισμάτων στοιχείων του πίνακα και ο υπολογισμός μέσων όρων.

?    Η εύρεση του μεγίστου ή του ελαχίστου στοιχείου του πίνακα.

?    Η ταξινόμηση των στοιχείων του πίνακα.

?    Η αναζήτηση ενός στοιχείου του πίνακα.

8.  Παραδείγματα / Εργασίες σε μονοδιάστατους πίνακες

ΕΙΣΑΓΩΓΗ ΣΤΟΙΧΕΙΩΝ ΣΕ ΠΙΝΑΚΑ Ν ΣΤΟΙΧΕΙΩΝ (Διάβασμα από το πληκτρολόγιο)

ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ Ν

ΔΙΑΒΑΣΕ Α[Ι]

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΕΜΦΑΝΙΣΗ ΣΤΟΙΧΕΙΩΝ ΠΙΝΑΚΑ Ν ΣΤΟΙΧΕΙΩΝ (Εμφάνιση στην οθόνη)

ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ Ν

ΓΡΑΨΕ Α[Ι]

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΥΠΟΛΟΓΙΣΜΟΣ ΜΕΣΟΥ ΟΡΟΥ ΣΤΟΙΧΕΙΩΝ ΠΙΝΑΚΑ Ν ΣΤΟΙΧΕΙΩΝ

SUM=0

ΓΙΑ I ΑΠΟ 1 ΜΕΧΡΙ Ν

        SUM=SUM + Α[Ι]

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

MO=SUM/N

ΕΥΡΕΣΗ ΜΕΓΙΣΤΟΥ ΚΑΙ ΘΕΣΗΣ ΤΟΥ (Αριθμός δείκτη)

MAX=A[1]

ΘΕΣΗ?1

ΓΙΑ Ι ΑΠΟ 2  ΜΕΧΡΙ Ν

      ΑΝ Α[Ι]>ΜΑΧ ΤΟΤΕ

           ΜΑΧ=Α[Ι]

           ΘΕΣΗ=Ι

     ΤΕΛΟΣ_ΑΝ

ΤΕΛΟΣ ΕΠΑΝΑΛΗΨΗΣ

Σημ.: Το «κράτημα» της θέσης είναι απαραίτητο, αν πρέπει να ανατρέξουμε σε ? άλλο ? παράλληλο πίνακα. Η εύρεση του ελάχιστου γίνεται με τον ίδιο τρόπο.

ΤΑΞΙΝΟΜΗΣΗ ΣΕ ΑΥΞΟΥΣΑ ΣΕΙΡΑ ΠΙΝΑΚΑ Ν ΣΤΟΙΧΕΙΩΝ

ΓΙΑ I ΑΠΟ 2 ΜΕΧΡΙ Ν

     ΓΙΑ J ΑΠΟ Ν ΜΕΧΡΙ Ι ΜΕ ΒΗΜΑ -1

           ΑΝ Α[J]<Α[J-1] ΤΟΤΕ

                TEMP=Α[J-1]

                Α[J-1]=Α[J]

                Α[J]=TEMP

           ΤΕΛΟΣ_ΑΝ

     ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Σημ.: Κατά την ταξινόμηση δεν πρέπει να μας ενδιαφέρει ο τύπος του πίνακα (αριθμ./ αλφαριθμ.), αλλά μόνον το «αν θα ταξινομήσουμε σε αύξουσα ή φθίνουσα σειρά». Αν πρέπει να ταξινομήσουμε δισδιάστατο πίνακα, θα πρέπει να μας δώσουν την στήλη βάσει της οποίας θα γίνει η ταξινόμηση. Σ? αυτήν την περίπτωση, θα πρέπει σε κάθε αντιμετάθεση να αντιμετατίθεται  ολόκληρη η γραμμή του πίνακα (τόσες «αντιμετάθεσε», όσες και οι στήλες του πίνακα). Το ίδιο πρέπει να κάνουμε, όταν έχουμε παράλληλους πίνακες (μονοδιάστατους με αντιστοιχία στοιχείων. π.χ. Ονόματα και βαθμούς μαθητών)

8.  Άλλες δομές δεδομένων ? Στοίβα / Ουρά

Στοίβα

?    Μοιάζει με μία στοίβα από πιάτα.

?    Τα δεδομένα που βρίσκονται στην κορυφή της στοίβας λαμβάνονται πρώτα, ενώ αυτά που βρίσκονται στο βάθος λαμβάνονται τελευταία.

?    Μέθοδος επεξεργασίας: Τελευταίο μέσα ? πρώτο έξω. Last In ? First Out (LIFO)

?    Κύριες λειτουργίες:

?    Υλοποίηση:

Ουρά

?    Μοιάζει με την ουρά μιας τράπεζας όπου περιμένουν να εξυπηρετηθούν οι πελάτες.

?    Τα δεδομένα που βρίσκονται πρώτα στην ουρά λαμβάνονται πρώτα ενώ αυτά που βρίσκονται τελευταία στην ουρά λαμβάνονται τελευταία.

?    Μέθοδος επεξεργασίας : Πρώτο μέσα ? πρώτο έξω. First In ? First Out (FIFO )

?    Κύριες λειτουργίες:

?    Υλοποίηση:

ΚΕΦΑΛΑΙΟ 6 ? Εισαγωγή στον Προγραμματισμό

 1. Η έννοια του Προγράμματος

?    Πρόγραμμα είναι ένα σύνολο εντολών γραμμένων σε μια γλώσσα προγραμματισμού.

?    Η διαδικασία μετατροπής ενός αλγορίθμου σε πρόγραμμα, ονομάζεται προγραμματισμός.

?    Ένα πρόγραμμα μπορεί να εκτελεστεί από τον υπολογιστή, εφ? όσον μεταγλωττιστεί (δηλ. μεταφραστεί).

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

?    Πηγαίο λέγεται ένα πρόγραμμα γραμμένο από έναν προγραμματιστή σε μια γλώσσα προγραμματισμού.

?    Εκτελέσιμο λέγεται ένα πρόγραμμα που είναι κατανοητό από τον υπολογιστή (και προήλθε φυσικά - με την διαδικασία της μεταγλώττισης - από το αντίστοιχο πηγαίο πρόγραμμα). Το εκτελέσιμο πρόγραμμα είναι  μια σειρά δυαδικών ψηφίων (11010110011011011?).

 2. Ιστορική αναδρομή ? εξέλιξη γλωσσών Προγραμματισμού

?    Ο υπολογιστής μπορεί να εκτελέσει εντολές, που αποτελούνται από σειρές δυαδικών ψηφίων. Αυτή ήταν και η  «γλώσσα προγραμματισμού» των πρώτων υπολογιστών. Oνομάστηκε γλώσσα μηχανής, γιατί ακριβώς είναι κατανοητή από μηχανές (υπολογιστές).

?    Αργότερα δημιουργήθηκαν γλώσσες πιο κατανοητές στον άνθρωπο, οι λεγόμενες συμβολικές γλώσσες, στις οποίες χρησιμοποιείται ένα σύνολο συμβόλων (π.χ. για την πρόσθεση: ADD). Ένα ειδικό πρόγραμμα, ο συμβολομεταφραστής (assembler), αναλαμβάνει να μετατρέψει τα σύμβολα αυτά σε γλώσσα μηχανής. Οι γλώσσες αυτές χρησιμοποιούνται ακόμη και σήμερα, ωστόσο παραμένουν στενά συνδεδεμένες με την αρχιτεκτονική του κάθε υπολογιστή.

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

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

3. Κατηγορίες γλωσσών υψηλού επιπέδου με βάση την περιοχή χρήσης τους

?    Γενικής χρήσης. Θεωρητικά κάθε γλώσσα γενικής χρήσης μπορεί να χρησιμοποιηθεί για την επίλυση οποιουδήποτε προβλήματος. Στην πράξη όμως διακρίνονται σε δύο κατηγορίες.

         Η Basic και η Pascal, είναι επίσης γλώσσες γενικής χρήσης και τα  

         καταφέρνουν εξίσου καλά στους δύο προηγούμενους τομείς.

?    Προγραμματισμού συστημάτων (π.χ. C)

?    Τεχνητής νοημοσύνης (π.χ. Lisp, Prolog)

Γιατί υπάρχουν πολλές γλώσσες Προγραμματισμού;

?     Κάθε γλώσσα είναι προσανατολισμένη στην επίλυση μιας ομάδας προβλημάτων.

?     Κάθε εταιρία προσφέρει και μια δική της γλώσσα ή μια παραλλαγή (Διάλεκτο) μιας υπάρχουσας, για λόγους ανταγωνισμού.

4. Ποιά γλώσσα προγραμματισμού είναι η καλύτερη;

?    Δεν μπορεί να πει κανείς ποια είναι η «καλύτερη γλώσσα». Αν υπήρχε καλύτερη, γιατί να χρησιμοποιήσουμε οποιαδήποτε άλλη;

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

 5. Διαδικασία μεταγλώττισης πηγαίου προγράμματος.

Σχεδόν κάθε γλώσσα προγραμματισμού διαθέτει ένα υποπρόγραμμα, τον συντάκτη (ένα είδος επεξεργαστή κειμένου), ο οποίος μας δίνει τη δυνατότητα να συντάξουμε ή να τροποποιήσουμε ένα πηγαίο πρόγραμμα.

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

Το εκτελέσιμο πρόγραμμα (συνήθως ένα αρχείο με επέκταση .exe), μπορούμε να το μεταφέρουμε και να το εκτελέσουμε σε οποιονδήποτε υπολογιστή.

6. Διαδικασία διερμήνευσης πηγαίου προγράμματος.

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

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

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

?     Συντακτικά είναι τα λάθη, που έχουν να κάνουν με λανθασμένη σύνταξη εντολών και χρήση μεταβλητών με μη αποδεκτό όνομα. Τέτοια διαπιστώνονται και μας επισημαίνονται απ? τον μεταγλωττιστή/διερμηνευτή στο στάδιο της μεταγλώττισης (οπότε τα διορθώνουμε και επαναλαμβάνουμε τη μεταγλώττιση).

ΚΕΦΑΛΑΙΟ 10 ? Τμηματικός προγραμματισμός / Υποπρογράμματα

 Τμηματικός προγραμματισμός ονομάζεται η τεχνική σχεδίασης και ανά­πτυξης των προγραμμάτων ως ένα σύνολο από μικρότερα και απλούστερα τμήματα προγραμμάτων.

1. Διαδικασίες / Συναρτήσεις

Ο τμηματικός προγραμματισμός υλοποιείται με τη χρήση 2 ειδών υποπρογραμμάτων

?    Διαδικασίες

Μπορούν να εκτελέσουν οποιαδήποτε λειτουργία από αυτές που μπορεί να εκτελέσει ένα πρόγραμμα.

Κάθε διαδικασία εκτελείται με την χρήση της εντολή ΚΑΛΕΣΕ και το όνομα της διαδικασίας.

?    Συναρτήσεις

Υπολογίζουν μία τιμή (οποιουδήποτε τύπου δεδομένων) και την  επιστρέφουν σε μια αντίστοιχη μεταβλητή.

 2  Λίστες παραμέτρων

Σε κάθε υποπρόγραμμα μεταβιβάζονται κάποια δεδομένα (τιμές μεταβλητών) που είναι απαραίτητα για να «λειτουργήσει» το υποπρόγραμμα. Η μεταβίβαση αυτή πραγματοποιείται μέσω της λίστας παραμέτρων:

Κανόνες για τις λίστες παραμέτρων:

 3.  Ιδιότητες  υποπρογραμμάτων

Ιδιότητες που πρέπει να διακρίνουν τα υποπρογράμματα:

?    Κάθε υποπρόγραμμα έχει μόνο μία είσοδο και μία έξοδο. Κάθε υποπρόγραμμα ενεργοποιείται με την είσοδο σε αυτό, εκτελεί ορισμένες ενέργειες, και απενεργοποιείται με την έξοδο από αυτό.

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

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

 4.  Πλεονεκτήματα τμηματικού προγραμματισμού:

?    Διευκολύνει την ανάπτυξη του αλγορίθμου και του αντιστοίχου προγράμματος.

?    Διευκολύνει την κατανόηση και διόρθωση του προγράμματος.

?    Απαιτεί λιγότερο χρόνο και προσπάθεια στη συγγραφή του προγράμματος.

?    Επεκτείνει τις δυνατότητες των γλωσσών προγραμματισμού.

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

Ασκήσεις  (Βασίλης Λυκοστράτης)

Επιλεγμένα θέματα Πανελληνίων Εξετάσεων

Πηγή: Λύκειο Αμπελώνα

• ΑΕΠΠ