Β ́ Λυκείου Εισαγωγή στις Αρχές της Επιστήμης των Η/Υ

ΥΠΟΥΡΓΕΙΟ ΠΑΙΔΕΙΑΣ ΚΑΙ ΘΡΗΣΚΕΥΜΑΤΩΝ ΙΝΣΤΙΤΟΥΤΟ ΕΚΠΑΙΔΕΥΤΙΚΗΣ ΠΟΛΙΤΙΚΗΣ B΄ ΛΥΚΕΙΟΥΙΝΣΤΙΤΟΥΤΟ ΤΕΧΝΟΛΟΓΙΑΣ ΥΠΟΛΟΓΙΣΤΩΝ ΚΑΙ ΕΚΔΟΣΕΩN «ΔΙΟΦΑΝΤΟΣ»

ΥΠΟΥΡΓΕΙΟ ΠΑΙΔΕΙΑΣ ΚΑΙ ΘΡΗΣΚΕΥΜΑΤΩΝ ΙΝΣΤΙΤΟΥΤΟ ΕΚΠΑΙΔΕΥΤΙΚΗΣ ΠΟΛΙΤΙΚΗΣ Εισαγωγή στις Αρχές της Επιστήμης των Η/Υ Β΄ ΛΥΚΕΙΟΥ Aθήνα 2014ΙΝΣΤΙΤΟΥΤΟ ΤΕΧΝΟΛΟΓΙΑΣ ΥΠΟΛΟΓΙΣΤΩΝ ΚΑΙ ΕΚΔΟΣΕΩΝ «ΔΙΟΦΑΝΤΟΣ»

ΙΝΣΤΙΤΟΥΤΟ ΕΚΠΑΙΔΕΥΤΙΚΗΣ ΠΟΛΙΤΙΚΗΣΠρόεδρος: Σωτήριος ΓκλαβάςΓΡΑΦΕΙΟ ΕΡΕΥΝΑΣ ΣΧΕΔΙΑΣΜΟΥ ΚΑΙ ΕΦΑΡΜΟΓΩΝ Β΄Προϊστάμενος: Παύλος Φ. ΜάραντοςΣΥΓΓΡΑΦΕΙΣ:Δρ. Σπυρίδων Δουκάκης, Πληροφορικός, Μαθηματικός, PIERCE-Αμερικανικό Κολλέγιο ΕλλάδοςΧρήστος Δουληγέρης, Καθηγητής Τμήματος Πληροφορικής Πανεπιστημίου ΠειραιώςΔρ. Θεόδωρος Καρβουνίδης, Εκπαιδευτικός ΠΕ19Χρήστος Κοίλιας, Καθηγητής Τμήματος Μηχανικών Πληροφορικής Τ.Ε. ΤΕΙ ΑθήναςΔρ. Αθανάσιος Πέρδος, Πληροφορικός, Φυσικός, Ελληνογαλλική Σχολή ΚαλαμαρίΣΥΝΤΟΝΙΣΤΗΣ: Χρήστος ΚοίλιαςΣΥΛΛΟΓΗ - ΕΠΕΞΕΡΓΑΣΙΑ ΥΛΙΚΟΥ:Δημήτριος Κοτσιφάκος, Εκπαιδευτικός, ΠΕ 1708ΚΡΙΤΕΣ-ΑΞΙΟΛΟΓΗΤΕΣ:Παναγιώτης Βαρζάκας, Μέλος ΔΕΠ (συντονιστής)Σοφία Τζελέπη, Σχολική Σύμβουλος, ΠΕ19Πέτρος Ματζάκος, Εκπαιδευτικός, ΠΕ19ΦΙΛΟΛΟΓΙΚΗ ΕΠΙΜΕΛΕΙΑ: Μαρία ΚοίλιαΕΞΩΦΥΛΛΟ: Γιώργος ΣκούφοςΣΕΛΙΔΟΠΟΙΗΣΗ: Γιώργος ΣκούφοςΑΝΑΔΟΧΟΣ: ΕΚΔΟΣΕΙΣ ΝΕΩΝ ΤΕΧΝΟΛΟΓΙΩΝ Στουρνάρη 49Α, 106 82, Αθήνα Τηλ. 210-38.45.594 - Fax: 210-38.08.009 Ε-mail: [email protected] URL: www.newtech-pub.com«ΔΗΜΙΟΥΡΓΙΑ ΕΚΠΑΙΔΕΥΤΙΚΟΥ ΥΛΙΚΟΥ ΓΙΑ ΤΑ ΝΕΑ ΜΑΘΗΜΑΤΑ ΤΟΥ ΓΕΝΙΚΟΥ ΛΥΚΕΙΟΥ»της Πράξης «ΝΕΟ ΣΧΟΛΕΙΟ (ΣΧΟΛΕΙΟ 21oυ αιώνα) - ΝΕΟ ΠΡΟΓΡΑΜΜΑ ΣΠΟΥΔΩΝ»ΜΕ ΚΩΔ. ΟΠΣ 295450, των Αξόνων Προτεραιότητας 1, 2 και 3 - ΟΡΙΖΟΝΤΙΑ ΠΡΑΞΗ τουΕΠΙΧΕΙΡΗΣΙΑΚΟΥ ΠΡΟΓΡΑΜΜΑΤΟΣ «ΕΚΠΑΙΔΕΥΣΗ ΚΑΙ ΔΙΑ ΒΙΟΥ ΜΑΘΗΣΗ», πουσυγχρηματοδοτείται από την Ευρωπαϊκή Ένωση - Ευρωπαϊκό Κοινωνικό Ταμείο και από ΕθνικούςΠόρους (ΕΣΠΑ 2007 - 2013). 2

ΠεριεχόμεναΠρόλογος........................................................................................................................................... 7ΕΝΟΤΗΤΑ 1. ΒΑΣΙΚΕΣ ΕΝΝΟΙΕΣΚεφάλαιο 1.1. Επιστήμη των Υπολογιστών .................................................................................. 91.1.1. Εισαγωγή ................................................................................................................................. 91.1.2. Θεωρητική Επιστήμη των Υπολογιστών ................................................................................. 91.1.3. Εφαρμοσμένη Επιστήμη των Υπολογιστών .......................................................................... 10ΕΝΟΤΗΤΑ 2. ΘΕΜΑΤΑ ΘΕΩΡΗΤΙΚΗΣ ΕΠΙΣΤΗΜΗΣ ΤΩΝ ΥΠΟΛΟΓΙΣΤΩΝΚεφάλαιο 2.1. Πρόβλημα .............................................................................................................. 132.1.1. Η έννοια του προβλήματος .................................................................................................... 132.1.2. Κατηγορίες προβλημάτων ..................................................................................................... 142.1.3. Υπολογιστικά προβλήματα .................................................................................................... 152.1.4. Διαδικασίες επίλυσης (υπολογιστικού) προβλήματος ........................................................... 16Κεφάλαιο 2.2. Αλγόριθμοι ............................................................................................................. 192.2.1. Ορισμός αλγορίθμου ............................................................................................................. 192.2.2. Χαρακτηριστικά αλγορίθμου ................................................................................................ 222.2.3. Ανάλυση Αλγορίθμων, Θεωρία Υπολογισμού, Πολυπλοκότητα Αλγορίθμων, Υπολογισιμότητα Αλγορίθμων .............................................................................................. 232.2.4. Βασικοί τύποι αλγορίθμων .................................................................................................... 252.2.5. Αναπαράσταση αλγορίθμου ................................................................................................... 272.2.6. Δεδομένα και αναπαράστασή τους ........................................................................................ 292.2.7. Εντολές και δομές αλγορίθμου .............................................................................................. 31 2.2.7.1. Εκχώρηση, Είσοδος και Έξοδος τιμών ..................................................................... 32 2.2.7.2. Δομή ακολουθίας ...................................................................................................... 33 2.2.7.3. Δομή επιλογής ........................................................................................................... 34 2.2.7.4. Δομή επανάληψης ..................................................................................................... 38 2.2.7.5. Κλήση αλγόριθμου από αλγόριθμο ............................................................................ 41 2.2.7.6. Αναδρομή .................................................................................................................. 432.2.8. Βασικές αλγοριθμικές λειτουργίες σε δομές δεδομένων ...................................................... 432.2.9. Εκσφαλμάτωση σε λογικά λάθη ............................................................................................ 482.2.10. Τεκμηρίωση ......................................................................................................................... 50Κεφάλαιο 2.3. Προγραμματισμός ................................................................................................. 552.3.1. Αναφορά σε γλώσσες προγραμματισμού και «Προγραμματιστικά Υποδείγματα» .............. 55 2.3.1.1. Πρόγραμμα και Γλώσσες Προγραμματισμού ............................................................. 55 2.3.1.2. Προγραμματιστικά Υποδείγματα ................................................................................ 58 2.3.1.3. Δομημένος Προγραμματισμός ................................................................................... 592.3.2. Σχεδίαση και συγγραφή κώδικα ............................................................................................ 622.3.3. Κύκλος ζωής εφαρμογής λογισμικού .................................................................................... 70 3

ΠεριεχόμεναΕΝΟΤΗΤΑ 3. ΘΕΜΑΤΑ ΕΦΑΡΜΟΣΜΕΝΗΣ ΕΠΙΣΤΗΜΗΣ ΤΩΝ ΥΠΟΛΟΓΙΣΤΩΝΚεφάλαιο 3.1. Λειτουργικά Συστήματα ...................................................................................... 773.1.1. Λογισμικό και Υπολογιστικό Σύστημα ................................................................................. 773.1.2. Το Λειτουργικό Σύστημα και οι Αρμοδιότητές του ............................................................... 773.1.3. Η Δομή και η Ιεραρχία ενός Λειτουργικού Συστήματος ....................................................... 783.1.4. Βασικές Εργασίες του Λ.Σ. ................................................................................................... 78 3.1.4.1. Διαχείριση της ΚΜΕ .................................................................................................. 78 3.1.4.2. Διαχείριση της Μνήμης ............................................................................................. 79 3.1.4.3. Διαχείριση του Συστήματος Αρχείων ......................................................................... 79 3.1.4.4. Διαχείριση Λειτουργιών Εισόδου/Εξόδου .................................................................. 803.1.5. Γνωστά Λειτουργικά Συστήματα .......................................................................................... 80Κεφάλαιο 3.2. Πληροφοριακά Συστήματα .................................................................................. 833.2.1. Τι είναι τα Πληροφοριακά Συστήματα .................................................................................. 833.2.2. Αρχιτεκτονικές Αποθήκευσης ............................................................................................... 843.2.3. Βάσεις Δεδομένων ................................................................................................................. 853.2.4. Γλώσσες Ερωτοαποκρίσεων (SQL, XML) ........................................................................... 86Κεφάλαιο 3.3. Δίκτυα .................................................................................................................... 873.3.1. Τι είναι ένα Δίκτυο Υπολογιστών .......................................................................................... 873.3.2. Στοιχεία δικτύων .................................................................................................................... 883.3.3. Κατηγορίες δικτύων .............................................................................................................. 88 3.3.3.1. Είδη δικτύων ανάλογα με την τεχνολογία μετάδοσης ................................................ 88 3.3.3.2. Είδη δικτύων ανάλογα με την τεχνολογία προώθησης της πληροφορίας ................... 88 3.3.3.3. Είδη δικτύων βάσει περιοχής που καλύπτουν ............................................................ 893.3.4. Τοπολογίες Δικτύων .............................................................................................................. 893.3.5. Σύγχρονες υπηρεσίες δικτύων ............................................................................................... 90Κεφάλαιο 3.4. Τεχνητή Νοημοσύνη ............................................................................................. 933.4.1. Τι είναι η Τεχνητή Νοημοσύνη .............................................................................................. 933.4.2. Εξέλιξη της Τεχνητής Νοημοσύνης ....................................................................................... 943.4.3. Τομείς εφαρμογών της Τεχνητής Νοημοσύνης ..................................................................... 953.4.4. Γλώσσες προγραμματισμού που χρησιμοποιούνται στην Τ.Ν. ............................................. 96Βιβλιογραφία .................................................................................................................................. 97Γλωσσάριο ...................................................................................................................................... 99 4

ΠρόλογοςΤο παρόν σύγγραμμα έρχεται να υπηρετήσει τη διδασκαλία του μαθήματος «Εισαγωγή στις Αρχέςτης Επιστήμης των Η/Υ», προσεγγίζοντας θέματα τόσο της Θεωρητικής όσο και της ΕφαρμοσμένηςΕπιστήμης των Η/Υ. Το πρώτο μέρος καλύπτει θέματα της Θεωρητικής Επιστήμης των Υπολογιστών–από το Πρόβλημα στον Αλγόριθμο και από εκεί στον Προγραμματισμό και τις Εφαρμογές του–μέσω του οποίου επιδιώκεται η ανάπτυξη της αναλυτικής και συνθετικής σκέψης των μαθητών καιτων μαθητριών. Στο δεύτερο μέρος, το βιβλίο πραγματεύεται ζητήματα των βασικών τομέων τηςΕφαρμοσμένης Επιστήμης των Υπολογιστών, ώστε να βοηθήσει τους μαθητές και τις μαθήτριες ναείναι σε θέση να κατονομάζουν και να εξηγούν επιστημονικές περιοχές της Πληροφορικής.Αναλυτικότερα, στην πρώτη ενότητα, στο Κεφάλαιο 1.1 επιχειρείται η διάκριση της Επιστήμηςτων Η/Υ σε Θεωρητική και Εφαρμοσμένη. Η παραπάνω διάκριση διαχωρίζει το σύγγραμμα σεδύο ακόμα ενότητες. Στη δεύτερη ενότητα και στο Κεφάλαιο 2.1 επαναπροσεγγίζεται η έννοια τουπροβλήματος και οι φάσεις επίλυσής του και αναδεικνύονται τα υπολογιστικά προβλήματα. Στησυνέχεια, στο Κεφάλαιο 2.2 περιγράφεται η έννοια του αλγορίθμου και των χαρακτηριστικών του,προσδιορίζονται οι διάφορες μορφές αναπαράστασής του και επεξηγούνται οι βασικές έννοιες στηνΑνάλυση Αλγορίθμων. Ακολούθως, αναφέρονται οι βασικοί τύποι και οι δομές δεδομένων καθώςκαι οι βασικές εντολές και δομές που χρησιμοποιούνται σε έναν αλγόριθμο. Τέλος, στο κεφάλαιοαυτό, προσδιορίζεται ο τρόπος εντοπισμού και διόρθωσης λογικών λαθών σε έναν αλγόριθμο. Όλατα παραπάνω βήματα, αποτελούν τα στάδια προετοιμασίας των μαθητών και μαθητριών, ώστεστο Κεφάλαιο 2.3 να προχωρήσουν στη δημιουργία ενός γνωσιακού και νοητικού σχήματος πουνα περιλαμβάνει τα είδη και τις τεχνικές προγραμματισμού και συγχρόνως να είναι σε θέση νασυνδυάζουν τις αλγοριθμικές δομές, τα δεδομένα και τις δομές δεδομένων για να δημιουργήσουνπρογράμματα. Τέλος, στην ενότητα αυτή αναδεικνύεται ότι οι σημερινές εφαρμογές είναι αρκετάπολύπλοκες και η δημιουργία τους ακολουθεί συγκεκριμένα μοντέλα ανάπτυξης εφαρμογώνλογισμικού που εξελίσσονται σε φάσεις.Η τρίτη ενότητα ασχολείται με θέματα της Εφαρμοσμένης Επιστήμης των Υπολογιστών, η οποίαεστιάζειτόσοστην επίλυση προβλημάτων, όσο καιστηβελτίωσηυπαρχουσών λύσεων στον πραγματικόκόσμο. Σε όλους τους τομείς της καθημερινότητας υπάρχει ένας τεράστιος όγκος διαθέσιμηςπληροφορίας και γνώσεων, η διαχείριση του οποίου προϋποθέτει τις κατάλληλες υπολογιστικέςυποδομές για την αποθήκευση της πληροφορίας καθώς και το σχεδιασμό, την ανάπτυξη και τησυντήρηση λογισμικού μέσω κατάλληλων γλωσσών προγραμματισμού και συστημάτων λογισμικού,τα οποία συνεργάζονται με την υπολογιστική υποδομή. Τέλος, προϋποθέτει την υποδομή μέσω τωνοποίων οι πληροφορίες διακινούνται με ασφάλεια. Από τους βασικούς τομείς της ΕφαρμοσμένηςΕπιστήμης των Υπολογιστών που έχουν σκοπό τη διερεύνηση και την κάλυψη των προαναφερθεισώναναγκών, έχουν επιλεγεί τέσσερις. Στο Κεφάλαιο 3.1 περιγράφονται τα Λειτουργικά Συστήματα,δηλαδή το λογισμικό που συντονίζει το υλικό και επικοινωνεί με το χρήστη. Στη συνέχεια, στοΚεφάλαιο 3.2 επεξηγούνται τα Πληροφοριακά Συστήματα, μέσω των οποίων επιτελείται συλλογή,ανάκτηση, επεξεργασία και αποθήκευση πληροφοριών. Ακολούθως, στο Κεφάλαιο 3.3 επιχειρείταιεπισκόπηση των Δικτύων Υπολογιστών για τη λήψη και την προώθηση πληροφοριών και, τέλος,στο Κεφάλαιο 3.4 περιγράφεται η Τεχνητή Νοημοσύνη, η οποία ερευνά τρόπους ανάπτυξηςυπολογιστικών μοντέλων ανθρώπινης γνώσης. 5

ΠρόλογοςΚαταβλήθηκε προσπάθεια, ώστε το υλικό του συγγράμματος να στηρίζεται στις γνώσεις και τιςεμπειρίες που έχουν ήδη αποκομίσει οι μαθητές και οι μαθήτριες από την προηγούμενη σχολική τουςεκπαίδευση. Με αυτόν τον τρόπο η μελέτη τους θα είναι μία ευχάριστη και δημιουργική διαδικασίαοικοδόμησης της γνώσης, που πραγματοποιείται πάνω σε τεχνικές «γνωστικής σκαλωσιάς». Τοβιβλίο συνοδεύεται από Παράρτημα, στο οποίο υπάρχει ένα εκτεταμένο γλωσσάρι-λεξικό όρων τηςΕπιστήμης των Υπολογιστών.Για την υποβοήθηση της αναγνωσιμότητας εκτός από σχήματα, πίνακες και διάφορα πλαίσια,έχουν χρησιμοποιηθεί και αρκετά εικονίδια, τα οποία χαρακτηρίζουν το μέρος του κειμένου πουσυνοδεύουν. Αυτά είναι: Προερωτήσεις Ορισμός Ιστορικό σημείωμα Συμβουλή ΠροσοχήΧρήσιμη πληροφορία Σημείωση Ανακεφαλαίωση Λέξεις-κλειδιάΘα θέλαμε να ευχαριστήσουμε όλους όσους μας στήριξαν στην προσπάθεια συγγραφής αυτού τουβιβλίου και ιδιαιτέρως, την κυρία Αγγελική Γερούση για τη βοήθειά της στην ανάγνωση μέρους τουυλικού και τις εύστοχες παρατηρήσεις της.Παραμένουμε στη διάθεση των εκπαιδευτικών και των μαθητών για οποιεσδήποτε παρατηρήσειςή σχόλια, ώστε να ενισχυθεί περαιτέρω το παρόν σύγγραμμα με απώτερο στόχο να υποστηρίζει τηδιδασκαλία του μαθήματος. Αθήνα, Ιούλιος 2014 Οι συγγραφείς6

ΕΝΟΤΗΤΑ 1ηBασικές ΈννοιεςΚΕΦΑΛΑΙΟ1.1. Επιστήμη των Υπολογιστών

1η ΕΝΟΤΗΤΑBασικές Έννοιες 8

ΚΕΦΑΛΑΙΟ 1.1Επιστήμη των ΥπολογιστώνΣτόχοι του κεφαλαίου είναι οι μαθητές Προερωτήσεις να περιγράφουν τους βασικούς τομείς της Επιστήμης των Υπολογι- • Τι ερευνά η Επιστήμη των στών και Υπολογιστών; Ποιες επιστη- μονικές περιοχές προσπαθεί να μπορούν να αναφερθούν στα πεδία τόσο της Θεωρητικής όσο να εξελίξει; και σε αυτά της Εφαρμοσμένης Επιστήμης των Υπολογιστών. • Πώς συνδέεται το Θεωρη- τικό της μέρος με το Εφαρ- 1.1 Η Επιστήμη των Υπολογιστών μοσμένο; • Πώς συνδέεται η εφαρμο-Η Επιστήμη των Υπολογιστών μελετά τα θεωρητικά θεμέλια και τη γή της με την επίλυση προ-φύση των πληροφοριών, των αλγορίθμων και των υπολογισμών, κα- βλημάτων του πραγματικούθώς και τις τεχνολογικές εφαρμογές τους σε αυτοματοποιημένα υπολο- κόσμου;γιστικά συστήματα, από τις σκοπιές σχεδίασης, ανάπτυξης, υλοποίη-σης, διερεύνησης και ανάλυσης. Η Επιστήμη των Υπολογιστών διακρί- Η Επιστήμη των Υπολογι-νεται σε δύο μεγάλες ενότητες: τη Θεωρητική και την Εφαρμοσμένη. στών ως διακριτή επιστήμη προέκυψε κατά τη δεκαετία 1.2 Θεωρητική Επιστήμη των Υπολογιστών του 1940 χάρη στην εύρεση των μαθηματικών ιδιοτήτωνΗ Θεωρητική Επιστήμη των Υπολογιστών (Theoretical Computer Sci- του υπολογισμού και την κα-ence) ερευνά κυρίως το σχεδιασμό των αλγορίθμων και των υπολογι- τασκευή ηλεκτρονικών υπο-στικών μεθόδων που χρησιμοποιούνται για την άντληση, την επεξερ- λογιστικών μηχανών.γασία, την ανάλυση και την αποθήκευση πληροφοριών. Βασικές έννοι-ες της Θεωρητικής Επιστήμης των Υπολογιστών, είναι η Ανάλυση Αλ- Η Ανάλυση Αλγορίθμωνγορίθμων, η Θεωρία Υπολογισιμότητας και η Θεωρία Πολυπλοκότη- ασχολείται με τον σχεδιασμότας. Υπάρχει μία διαρκής αλληλεπίδραση μεταξύ της Θεωρητικής και και την ανάλυση της πολυ-της Εφαρμοσμένης Επιστήμης των Υπολογιστών. Για παράδειγμα, η πλοκότητας των αλγορίθμων.Θεωρία Γλωσσών Προγραμματισμού, η οποία μελετά προσεγγίσειςγια την περιγραφή των υπολογισμών, οδηγεί στην ανάπτυξη γλωσσών Η Θεωρία Υπολογισιμότη-προγραμματισμού και το σχεδιασμό λογισμικού και εφαρμογών. τας ερευνά αν και πόσο απο- δοτικά κάποια προβλήματα 1.3 Εφαρμοσμένη Επιστήμη των Υπολογιστών μπορούν να επιλυθούν με συ- γκεκριμένα υπολογιστικά μο-H Εφαρμοσμένη Επιστήμη των Υπολογιστών (Applied Computer Sci- ντέλα.ence) μελετά τρόπους εφαρμογής της Θεωρίας των Υπολογιστών γιατην επίλυση προβλημάτων στον πραγματικό κόσμο. Βασικά επιστημο- Η Θεωρία Πολυπλοκότηταςνικά πεδία που εντάσσονται στην Εφαρμοσμένη Επιστήμη των Υπολο- μελετά τους πόρους που απαι-γιστών είναι: τούνται για την επίλυση ενός προβλήματος βάσει ενός συ- γκεκριμένου αλγορίθμου. 9

1η •• Ο σχεδιασμός υλικού για την κατασκευή των υπολογιστών, όπως o σκληρός δίσκος, η κεντρική μονάδα επεξεργασίας κτλ.Bασικές Έννοιες •• Ο σχεδιασμός, η ανάπτυξη και η συντήρηση λογισμικού, όπως τωνΞεκινήστε την αναζήτησή λειτουργικών συστημάτων τα οποία συνεργάζονται με το υλικό,σας από την κατηγοριοποίη- καθώς και των ποικίλων προγραμμάτων που αναπτύσσονται με τηση του οργανισμού ACM. βοήθεια των γλωσσών προγραμματισμού.Χρήσιμοι Υπερσύνδεσμοι •• Ο σχεδιασμός πληροφοριακών συστημάτων για τη συλλογή, ανά-http://www.acm.org κτηση, επεξεργασία και αποθήκευση πληροφοριών.Association for ComputingMachinery •• Η τεχνητή νοημοσύνη, η οποία ερευνά τρόπους ανάπτυξης υπολο-http://www.computer.org/ γιστικών μοντέλων ανθρώπινης γνώσης.portal/web/guest/homeIEEE-Computer Society •• Ο σχεδιασμός δικτύων υπολογιστών για την παραγωγή, τη λήψηhttp://aisnet.org και την προώθηση πληροφοριών.AIS: Association forInformation Systems •• Ο σχεδιασμός βάσεων δεδομένων και συστημάτων διαχείρισης βά- σεων δεδομένων για την υποστήριξη πληροφοριακών συστημάτων.Λέξεις κλειδιάΘεωρητική Επιστήμη των •• Η ασφάλεια των υπολογιστών, δηλαδή το σύνολο των μεθόδων πουΥπολογιστών, Εφαρμοσμέ- χρησιμοποιούνται για την προστασία πληροφοριών ή υπηρεσιώννη Επιστήμη των Υπολογι- από φθορά, αλλοίωση ή μη εξουσιοδοτημένη χρήση.στών. Στην συνέχεια του βιβλίου θα μελετηθούν θέματα τόσο της Θεωρητικής (αλγόριθμοι και προγραμματισμός) όσο και της Εφαρμοσμένης Επιστή- μης Υπολογιστών (όπως τα Λειτουργικά Συστήματα, τα Πληροφοριακά Συστήματα, τα Δίκτυα Υπολογιστών και η Τεχνητή Νοημοσύνη). Ανακεφαλαίωση Η Επιστήμη Υπολογιστών πραγματεύεται δύο μεγάλες θεματικές ενό- τητες - τη Θεωρητική και την Εφαρμοσμένη - οι οποίες περιλαμβάνουν πολλούς επί μέρους κλάδους με έμφαση τόσο στην διαχείριση πληρο- φοριών όσο και στην επίλυση προβλημάτων στον πραγματικό κόσμο. Ερωτήσεις - Θέματα προς συζήτηση - Δραστηριότητες 1. Πώς αντιλαμβάνεστε την Επιστήμη των Υπολογιστών; 2. Να αναφέρετε τουλάχιστον τρία επιστημονικά πεδία που εντάσσο- νται στην Εφαρμοσμένη Επιστήμη των Υπολογιστών, αναζητώντας σχετικές πληροφορίες στο διαδίκτυο. 3. Να αναφέρετε τρεις τομείς της Θεωρητικής Πληροφορικής οι οποί- οι έχουν άμεση εφαρμογή σε προβλήματα που αντιμετωπίζει η Εφαρμοσμένη Πληροφορική. 4. Να αναζητήσετε στο Διαδίκτυο, εργαζόμενοι σε ομάδες, όρους που σχετίζονται με την Επιστήμη των Υπολογιστών, τους τομείς της, τα πεδία εφαρμογής καθεμιάς και να συσχετίσετε τις έννοιες μεταξύ τους. Με βάση την αναζήτηση αυτή, να γίνει απαρίθμηση των πλέ- ον γνωστών τομέων και ο διαχωρισμός τους σε θεωρητικούς και εφαρμοσμένους.10

ΕΝΟΤΗΤΑ 2ηΘέματα Θεωρητικής Επιστήμηςτων ΥπολογιστώνΚΕΦΑΛΑΙΑ2.1. Πρόβλημα2.2. Αλγόριθμοι2.3. Προγραμματισμός

2η ΕΝΟΤΗΤΑΘέματα ΘεωρητικήςΕπιστήμης των Υπολογιστών 12

ΚΕΦΑΛΑΙΟ 2.1ΠρόβλημαΣτόχοι του κεφαλαίου αυτού είναι να μπορούν οι μαθητές: Προερωτήσεις να περιγράφουν την έννοια του προβλήματος να κατατάσσουν ένα πρόβλημα στην κατηγορία που ανήκει • Συζητήστε με τους συμμα- να διακρίνουν την ύπαρξη υπολογιστικών και μη προβλημάτων θητές σας και καταγράψτε να αναφέρουν τις φάσεις επίλυσης ενός υπολογιστικού προβλήματος. δύο προβλήματα. • Ποια είναι τα βασικότερα2.1.1 Η έννοια του προβλήματος προβλήματα της ανθρωπό- τητας;Οι άνθρωποι, από την πρώτη στιγμή της ύπαρξής τους, ήρθαν αντιμέτω- • Ρωτήστε το συμμαθητή σαςποι με ποικίλα προβλήματα, τόσο στις καθημερινές τους δραστηριότη- ποιο θεωρεί το σημαντικότε-τες όσο και σε διάφορους επιστημονικούς τομείς. Κάνοντας μια αναδρο- ρο πρόβλημα της ανθρωπό-μή στην ιστορία είναι δυνατό να εντοπιστούν πληθώρα προβλημάτων. τητας και ποιο θεωρεί το ση- μαντικότερο πρόβλημα που •• Ο Όμηρος στην Οδύσσεια περιγράφει τα προβλήματα που αντι- χρήζει αντιμετώπισης στο μετώπιζε ο Οδυσσέας για να φτάσει στην Ιθάκη. σχολείο. •• Το πρόβλημα που κλήθηκε να επιλύσει ο Αρχιμήδης με τη βασιλική Τα προβλήματα δεν είναι κορώνα που οδήγησε στη γνωστή φράση του «Εύρηκα-Εύρηκα». απαραίτητα μαθηματικές κα- ταστάσεις που απαιτούν αντι- •• Το πρόβλημα μέτρησης του χρόνου, το οποίο αντιμετωπίστηκε μετώπιση. με τη χρήση της κλεψύδρας και του εκκρεμούς. Εικόνα 2.1. Ο κύβος του •• Τα προβλήματα επιδημιών στην ανθρωπότητα και η αντιμετώπι- Ρούμπικ (Rubik) σή τους με εμβόλια. 13 •• Το πρόβλημα του «ιού του 2000» και η αντιμετώπισή του, ώστε τα υπολογιστικά συστήματα να λειτουργήσουν σωστά την 1/1/2000.Όπως φαίνεται, η ύπαρξη προβλημάτων είναι ένα διαχρονικό φαινόμενο.Στην εποχή μας, οι άνθρωποι έρχονται αντιμέτωποι με προβλήματα στονπροσωπικό, στον επαγγελματικό και στον κοινωνικό χώρο γενικότερα. Όλοιοι άνθρωποι δεν αντιμετωπίζουν τα ίδια προβλήματα και επιπλέον δίνουν δι-αφορετική σημασία και βαρύτητα σε αυτά. Ωστόσο υπάρχουν προβλήματαπου αναγνωρίζονται από τους περισσότερους ως πολύ σημαντικά.Τα προβλήματα εκτός από δυσάρεστες ή πιεστικές καταστάσεις πουαπαιτούν λύση (περιβαλλοντικά προβλήματα, κοινωνικά προβλήμα-τα, προσωπικά προβλήματα κ.ά.) μπορούν να είναι είτε ενδιαφέρου-σες προκλήσεις (π.χ. η επίλυση ενός γρίφου ή η νίκη σε ένα παιχνί-δι σκάκι), είτε ευκαιρίες για να προκύψει κάτι ωφέλιμο για την κοινω-νία μέσω της επίλυσής τους (π.χ. νέα ασφαλέστερα υλικά για την κατα-σκευή αυτοκινήτων, τρισδιάστατες εκτυπώσεις κ.ά.).

2η Όλα τα προβλήματα δεν μπορούν να αντιμετωπιστούν με έναν ενιαίο και μο- ναδικό τρόπο. Επιπλέον, κάθε ξεχωριστό πρόβλημα μπορεί να αντιμετωπί-Θέματα Θεωρητικής ζεται και να επιλύεται με ποικίλους τρόπους, ενώ συγχρόνως μπορεί να έχειΕπιστήμης των Υπολογιστών πολλές λύσεις (το πρόβλημα οργάνωσης μιας εκπαιδευτικής επίσκεψης). «Η ζωή είναι επίλυση προ- Με τον όρο Πρόβλημα προσδιορίζεται μια κατάσταση η οποίαβλημάτων», (Καρλ Πόππερ, χρήζει αντιμετώπισης, απαιτεί λύση, η δε λύση της δεν είναι γνωστή, ούτε προφανής. Karl Popper, 1994) Η διατύπωση ενός προβλήματος και η αντιμετώπισή του, αποτελούν ζητήματα που απαιτούν ικανότητες ορθολογικής, αναλυτικής και συν- θετικής σκέψης, αλλά και σωστό χειρισμό της φυσικής γλώσσας. Επι- πλέον, οι δεξιότητες που αποκτούνται από την ενασχόληση με τα προ- βλήματα (διατύπωση και αντιμετώπισή τους), αποτελούν χρήσιμα εφό- δια για κάθε ανθρώπινη δραστηριότητα. 2.1.2 Κατηγορίες Προβλημάτων Τα προβλήματα ανάλογα με τη δυνατότητα επίλυσης διακρίνονται σε τρεις κατηγορίες. Επιλύσιμα είναι εκείνα τα προβλήματα για τα οποία η λύση έχει βρεθεί και έχει διατυπωθεί. Ùò ðñïò ôç Παραδείγματα επιλύσιμων προβλημάτων είναι η αποψίλωση μιας äõíáôüôçôá åðßëõóçò έκτασης γης (ο καθαρισμός δηλαδή ενός χωραφιού από κάθε είδους βλάστηση), η επίλυση της δευτεροβάθμιας εξίσωσης κ.ά.. Åðéëýóéìá Μη επιλύσιμα χαρακτηρίζονται εκείνα τα προβλήματα για τα Ìç åðéëýóéìá οποία έχει αποδειχτεί, ότι δεν επιδέχονται λύση. ÁíïéêôÜ Το πρόβλημα του τετραγωνισμού του κύκλου με κανόνα και διαβήτη Εικόνα 2.2. Κατηγορίες που είχε διατυπωθεί από τους αρχαίους ελληνιστικούς χρόνους είναι ένα τέτοιο πρόβλημα. Παρότι το πρόβλημα επιδέχεται προσεγγιστική προβλημάτων λύση, δεν μπορεί να λυθεί με τη χρήση κανόνα και διαβήτη.Ένα άλλο μη επιλύσιμο πρό- Ανοικτά ονομάζονται τα προβλήματα για τα οποία η λύση τουςβλημα είναι η εύρεση ακέραι- δεν έχει ακόμα βρεθεί, ενώ ταυτόχρονα δεν έχει αποδειχτεί, ότιων λύσεων οποιασδήποτε δι- δεν επιδέχονται λύση.οφαντικής εξίσωσης (ακέραιαπολυωνυμική εξίσωση) όπως Ένα τέτοιο παράδειγμα είναι το πρόβλημα της ενοποίησης των τεσσά-της 6x + 15y = 4. Το 1970 ρων πεδίων δυνάμεων (βαρυτικού, ηλεκτρομαγνητικού, ασθενούς πυ-αποδείχτηκε ότι το πρόβλημα ρηνικού και ισχυρού πυρηνικού), το οποίο προς το παρόν, δεν έχει επι-είναι μη επιλύσιμο. λυθεί. Επίσης, η εικασία του Γκόλντμπαχ (Goldbach, κάθε άρτιος μπο- ρεί να γραφτεί ως άθροισμα δύο πρώτων αριθμών) αποτελεί ένα ανοι- 14 κτό πρόβλημα αφού δεν έχει ακόμα αποδειχθεί.

2.1.3 Υπολογιστικά Προβλήματα ΚΕΦΑΛΑΙΟ 2.1Στις αρχές του 20ου αιώνα, ο Ντέβιντ Χίλμπερτ (David Hilbert) παρου- Πρόβλημασίασε έναν κατάλογο προβλημάτων, εκ των οποίων το τελευταίο έθετε τοερώτημα «αν υπάρχει αλγόριθμος που μπορεί να αποφασίσει την αλήθεια Εικόνα 2.3. David Hilbertοποιασδήποτε λογικής πρότασης που αφορούσε τους φυσικούς αριθμούς». και Kurt GödelΜε το ερώτημα αυτό ουσιαστικά ρωτούσε «αν μπορεί να αυτοματοποιηθείη διαδικασία επίλυσης όλων των μαθηματικών προβλημάτων». Το 1931, Εικόνα 2.4. Alan Turingτο θεώρημα της μη πληρότητας του Κουρτ Γκέντελ (Kurt Gödel) έδειξε και Pierre de Fermatότι, σε οποιαδήποτε γλώσσα που έχει την ισχύ να περιγράψει τις ιδιότητεςτων φυσικών αριθμών, υπάρχουν αληθείς προτάσεις των οποίων η αλήθεια Το θεώρημα του Πιέρ ντεδεν μπορεί να βεβαιωθεί με κανέναν αλγόριθμο. Με τον τρόπο αυτό, απέ- Φερμά (Pierre de Fermat):δειξε ότι υπάρχουν μερικές συναρτήσεις οι οποίες δεν μπορούν να αναπα- «Τρεις θετικοί αριθμοί a, b,ρασταθούν από έναν αλγόριθμο, και άρα δεν μπορούν να υπολογιστούν. c δεν μπορούν να ικανοποι-Στη συνέχεια, o Άλαν Τιούρινγκ (Alan Turing) όρισε τη μηχανή Turing η ήσουν την εξίσωση an+bn=cnοποία είναι ικανή να υπολογίσει οποιαδήποτε υπολογίσιμη συνάρτηση και για κάθε ακέραιο αριθμόέδειξε επίσης ότι υπήρχαν μερικές συναρτήσεις τις οποίες καμία μηχανή n>2» διατυπώθηκε από τονTuring δεν μπορεί να υπολογίσει. ίδιο το 1637 ως σημείωση στο βιβλίο του «ΑριθμητικάΑπό τα παραπάνω φάνηκε ότι τα προβλήματα με βάση τη δυνατότητα του Διόφαντου». Η επιτυχήςεπίλυσής τους μέσω του υπολογιστή, μπορούν να διακριθούν σε υπο- απόδειξη του θεωρήματοςλογιστικά και μη υπολογιστικά. δημοσιεύθηκε το 1995. Οποιοδήποτε πρόβλημα μπορεί να λυθεί και μέσω του υπολογι- 15 στή, χαρακτηρίζεται υπολογιστικό πρόβλημα.Για να λυθεί ένα πρόβλημα με τη βοήθεια του υπολογιστή, χρειάζεταινα διατυπωθεί το αντίστοιχο υπολογιστικό πρόβλημα και στη συνέχειανα υλοποιηθεί η επίλυσή του μέσω του υπολογιστή.Παραδείγματα υπολογιστικών προβλημάτων είναι: •• Η επίλυση της δευτεροβάθμιας εξίσωσης. •• Η ταξινόμηση των μαθητών σε αλφαβητική σειρά. •• Η αναζήτηση και ο υπολογισμός της χιλιομετρικά συντομότε- ρης διαδρομής που θα κάνει ένας ταχυδρόμος για να επισκεφθεί δέκα χωριά και να επιστρέψει στο χωριό από όπου ξεκίνησε περ- νώντας μόνο μία φορά από κάθε χωριό, με βάση έναν δεδομέ- νο χάρτη των χωριών και των δρόμων που συνδέουν τα χωριά. •• Η εύρεση λέξης που να ξεκινά από ένα γράμμα και να τελειώνει σε ένα άλλο γράμμα.Από την άλλη, τα μη υπολογιστικά προβλήματα δεν μπορούν να λυ-θούν από έναν υπολογιστή ή από άλλα μηχανικά μέσα. Για παράδειγ-μα, καμία μηχανή δεν μπορεί γενικά να αποφανθεί αν ένα δεδομένοπρόγραμμα θα επιστρέψει απάντηση για μια δεδομένη είσοδο, ή αν θαεκτελείται για πάντα.

2η ΕΝΟΤΗΤΑ 2.1.4 Διαδικασίες επίλυσης (υπολογιστικού) προβλήματοςΘέματα ΘεωρητικήςΕπιστήμης των Υπολογιστών Η προσπάθεια αντιμετώπισης και επίλυσης ενός προβλήματος προϋ- ποθέτει αρχικά την πλήρη κατανόηση του προβλήματος. Η κατανόησηΓια να διατυπωθεί ένα πρό- ενός προβλήματος αποτελεί συνάρτηση δύο παραγόντων, της σωστήςβλημα μπορεί να χρησιμο- διατύπωσης εκ μέρους του δημιουργού του και της αντίστοιχα σωστήςποιηθεί οποιοδήποτε μέσο με ερμηνείας από τη μεριά εκείνου που καλείται να το αντιμετωπίσει.συνηθέστερα τον προφορικόή το γραπτό λόγο. Ο λόγος Η κατανόηση του προβλήματος είναι βασική προϋπόθεση για να ξεκι-όμως όταν χρησιμοποιείται νήσει η διαδικασία ανάλυσης του προβλήματος σε άλλα απλούστεραγια την επικοινωνία, χρειά- και ο διαχωρισμός των κύριων στοιχείων του προβλήματος σε σχέσηζεται να χαρακτηρίζεται από με τα δευτερεύοντα στοιχεία (αφαίρεση). Η ανάλυση-αφαίρεση αποτε-σαφήνεια. λεί το δεύτερο βήμα στην διαδικασία επίλυσης ενός προβλήματος. Στό- χος της ανάλυσης, είναι η διάσπαση του προβλήματος σε άλλα απλού-Η άστοχη χρήση ορολογί- στερα προβλήματα για να είναι εύκολη η αντιμετώπισή τους.ας και η λανθασμένη σύντα-ξη, μπορούν να προκαλέ- Η ανάλυση ενός προβλήματος μπορεί να πραγματοποιηθεί είτε φραστι-σουν παρερμηνείες και παρα- κά είτε διαγραμματικά, όπως φαίνεται στο παράδειγμα 2.1.πλανήσεις. Ωστόσο, παρερ-μηνείες μπορούν να υπάρ- Παράδειγμα 2.1. Ανάλυση προβλήματος: Εξυπηρέτηση πολιτών απόξουν ακόμα και σε περιπτώ- τις υπηρεσίες του δημοσίου.σεις όπου όλοι οι λεξικολογι-κοί και συντακτικοί κανόνες Φραστική ανάλυσητηρούνται. 1. Προσδιορισμός αναγκών 1.1. Ταχύτερη εξυπηρέτηση πολιτών 1.2. Περιορισμός μετακινήσεων 2. Δράση 2.1. Ανάπτυξη ηλεκτρονικών υπηρεσιών εξυπηρέτησης 2.1.1. Ποιες υπηρεσίες θα είναι διαθέσιμες; 2.1.2. Με ποια διαδικασία θα γίνονται διαθέσιμες; 2.2. Ενημέρωση πολιτών 2.3. Ενημέρωση υπαλλήλων για να συνδράμουν το έργο 3. Εφαρμογή του σχεδίου. Διαγραμματική ανάλυσηΣτη διαγραμματική αναπαρά- Εικόνα 2.5. Διαγραμματική αναπαράσταση ανάλυσης προβλήματοςσταση, το αρχικό πρόβλημααναπαρίσταται από ένα ορ- Για τη σωστή επίλυση ενός προβλήματος είναι σημαντικός ο επακριβήςθογώνιο παραλληλόγραμμο. προσδιορισμός των δεδομένων που παρέχει το πρόβλημα και η λεπτο-Κάθε ένα από τα απλούστε- μερειακή καταγραφή των ζητούμενων που αναμένονται σαν αποτελέ-ρα προβλήματα, αναπαρίστα-ται επίσης από ένα ορθογώνιοπαραλληλόγραμμο.Τα παραλληλόγραμμα πουαντιστοιχούν στα απλούστεραπροβλήματα, σχηματίζονταιένα επίπεδο χαμηλότερα. 16

σματα της επίλυσης του προβλήματος. Για να βρει κάποιος τα ζητούμε- ΚΕΦΑΛΑΙΟ 2.1να χρειάζεται να επεξεργαστεί τα δεδομένα. Πρόβλημα Επεξεργασία δεδομένων είναι η συστηματική εκτέλεση πράξεων σε δεδομένα. Δεδομένο είναι μια παρά- σταση γεγονότων, εννοιώνΑφού ολοκληρωθεί η ανάλυση του προβλήματος ακολουθεί το στάδιο ή εντολών σε τυποποιημένητης σύνθεσης. Κατά τη σύνθεση επιχειρείται η κατασκευή μιας νέας μορφή που είναι κατάλληληδομής, με την οργάνωση των επιμέρους στοιχείων του προβλήματος. για επικοινωνία, ερμηνεία ήΕπιπλέον, η κατηγοριοποίηση του προβλήματος είναι ένα εξίσου ση- επεξεργασία από τον άνθρω-μαντικό στάδιο, μέσω του οποίου το πρόβλημα κατατάσσεται σε κά- πο ή από αυτόματα μέσα.ποια κατηγορία, σε μία οικογένεια παρόμοιων προβλημάτων και έτσιδιευκολύνεται η επίλυση, αφού παρέχεται η ευκαιρία να προσδιοριστεί Με τον όρο ζητούμενο δηλώ-το ζητούμενο ανάμεσα σε παρόμοια «αντικείμενα». Τέλος, με τη γενί- νεται οτιδήποτε προκύπτει ήκευση, μπορούν να μεταφερθούν τα αποτελέσματα σε άλλες παρεμφε- τίθεται ως αντικείμενο έρευ-ρείς καταστάσεις ή προβλήματα. νας ή αναζήτησης.Παράδειγμα 2.2. Να διερευνηθεί η εξίσωση αx + β = 0 ως προς x, για Με τον όρο πληροφορία ανα-τις διάφορες τιμές του α και β. φέρεται οποιοδήποτε γνωσι- ακό στοιχείο προέρχεται απόΑπάντηση επεξεργασία δεδομένων.Υπάρχουν 2 περιπτώσεις: Αν ο συντελεστής της μεταβλητής x είναι δι-άφορος του μηδενός (α ≠ 0) ή αν ο συντελεστής της μεταβλητής x εί- Κατανόηση: Δίνονται οιναι ίσος με μηδέν (α = 0). σταθεροί όροι α, β της εξίσω- σης και ζητείται η τιμή τηςΠερίπτωση 1: Αν α ≠ 0, τότε η εξίσωση έχει μεταβλητής x για τις διάφο- ρες τιμές των α και β. μοναδική λύση την x = - β . α Ανάλυση: Το πρόβλημα δι- Περίπτωση 2: Αν α = 0 τότε υπάρχουν δύο υποπεριπτώσεις: Αν ο στα- ασπάται αρχικά σε δύο υπο- προβλήματα. Στο πρώτο ο θερός όρος β είναι διάφορος του μηδενός (β ≠ 0) ή αν εί- συντελεστής α της μεταβλη- τής x είναι διάφορος του μη- ναι ίσος με μηδέν (β = 0). δενός. Στο δεύτερο ο συντε- λεστής είναι μηδέν. Το δεύ- Περίπτωση 2.1. Αν β ≠ 0, η εξίσωση είναι αδύνατη. τερο υποπρόβλημα διασπά- ται σε δύο υποπροβλήματα: Περίπτωση 2.2. Αν β = 0, η εξίσωση είναι αόριστη. Ο σταθερός όρος β είναι ίσος με μηδέν ή είναι διάφοροςΠαράδειγμα 2.3. Δίνεται ο ακόλουθος χάρτης διαδρομών (εικόνα 2.6) του μηδενός.που συνδέει ορισμένες πόλεις. Ο χάρτης δείχνει το χρόνο που απαιτεί- Σύνθεση: Η εξίσωση είτεται για τη μετακίνηση από πόλη σε πόλη. έχει μοναδική λύση, είτε είναι αδύνατη, είτε είναι αόριστη. Εικόνα 2.6. Χάρτης διαδρομών Κατηγοριοποίηση και γενί- κευση: όλες οι πρωτοβάθμι- ες εξισώσεις αντιμετωπίζο- νται με αυτή την προσέγγιση. Το παράδειγμα 2.3 εντάσσε- ται σε µία γενικότερη κατη- γορία προβλημάτων εύρεσης συντομότερης διαδρομής. 17

2η ΕΝΟΤΗΤΑ 1. Ποια διαδρομή είναι η συντομότερη από την πόλη Α στην πόλη Β; 2. Σε ποια πόλη θα συναντηθούν τρεις φίλοι ώστε κανένας να μην κινη-Θέματα ΘεωρητικήςΕπιστήμης των Υπολογιστών θεί περισσότερο από δεκαπέντε λεπτά αν βρίσκονται στις πόλεις Γ, Δ και Ε αντίστοιχα και τα τρένα τους ξεκινούν όλα στις 19:00; Εικόνα 2.7. Στάδια επίλυσης προβλήματος. Απάντηση 1. Όπως φαίνεται στο χάρτη, υπάρχουν πολλές διαδρομές για να μετα-Το 1976 το θεώρημα των 4χρωμάτων αποδείχθηκε. Για βεί κάποιος από την πόλη Α στην πόλη Β. Από αυτές τις διαδρομέςτην απόδειξη χρησιμοποιή- χρειάζεται να υπολογιστεί η συντομότερη με βάση το χρόνο πουθηκε ένας υπολογιστής για απαιτείται για τη μετακίνηση από πόλη σε πόλη. Για το σκοπό αυτό,1200 ώρες. μετριούνται οι αποστάσεις μεταξύ των πόλεων, από όπου προκύ- πτει ότι η συντομότερη με βάση το χρόνο διαδρομή είναι 20 λεπτά.Λέξεις κλειδιά 2. Με παρόμοιο τρόπο, μετριούνται οι σχετικές αποστάσεις. Η συνά-Πρόβλημα, Επιλύσιμα, ντηση θα γίνει στην πόλη Θ, αφού ο άνθρωπος από την πόλη Γ θαΑνοικτά, Υπολογιστικά, κάνει 15 λεπτά, ο άνθρωπος από την πόλη Δ θα κάνει 14 λεπτά καιΕπίλυση προβλήματος, ο άνθρωπος από την πόλη Ε θα κάνει 12 λεπτά.Κατανόηση, Ανάλυση,Αφαίρεση, Σύνθεση, ΑνακεφαλαίωσηΚατηγοριοποίηση,Γενίκευση Στο κεφάλαιο αυτό παρουσιάστηκε η διαχρονικότητα του προβλήματος και επιχειρήθηκε να γίνει σαφής η ανεξαρτησία της λύσης του από τον υπολογιστή. Κατηγοριοποιήθηκαν τα προβλήματα ως προς τη δυνατότη- τα επίλυσης και επιπλέον ως προς τη δυνατότητα επίλυσης με τον υπο- λογιστή. Επισημάνθηκαν βασικά στοιχεία στη διαδικασία επίλυσης ενός προβλήματος (κατανόηση, καθορισμός δεδομένων και ζητουμένων, ανά- λυση-αφαίρεση, σύνθεση, κατηγοριοποίηση και γενίκευση). Ερωτήσεις - Θέματα προς συζήτηση - Δραστηριότητες 1. Να αναφέρετε τις κατηγορίες προβλημάτων ως προς τη δυνατότητα επί- λυσης και να δώσετε παραδείγματα προβλημάτων από κάθε κατηγορία. 2. Εργαστείτε σε ομάδες. Κάθε ομάδα θα θέτει ένα πρόβλημα στην άλλη ομά­δα, η οποία καλείται να ανακαλύψει την κατηγορ­ ία στην οποία ανήκει το πρόβ­ λημα. 3. Να διερευνήσετε την εξίσωση αx2 + βx + γ = 0 ως προς x για τις δι- άφορες τιμές των α, β και γ. 4. Μπορεί κάθε χάρτης να χρωματιστεί με τέσσερα χρώματα το πολύ, ώστε οι γειτονικές χώρες να είναι χρωματισμένες διαφορετικά; 5. Να χαρακτηρίσετε με Σωστό ή Λάθος τις παρακάτω προτάσεις: Α. Κάθε επιλύσιμο πρόβλημα είναι υπολογιστικό. Β. Η κατανόηση προηγείται της επίλυσης. Γ. Όλα τα προβλήματα μπορούν να λυθούν με τη βοήθεια του υπο- λογιστή. Δ. Η ανάλυση του προβλήματος βοηθάει στην επίλυσή του. Ε. Υπάρχουν μη υπολογιστικά μαθηματικά προβλήματα.18

ΚΕΦΑΛΑΙΟ 2.2ΑλγόριθμοιΣτόχοι του κεφαλαίου αυτού είναι να μπορούν οι μαθητές: Προερωτήσεις να περιγράφουν την έννοια του αλγορίθμου και να διακρίνουν την • Ξέρεις ότι ήδη έχεις χρησι- ύπαρξη συγκεκριμένων χαρακτηριστικών που χρειάζεται να έχει μοποιήσει πολλούς αλγορίθ- ένας αλγόριθμος μους; να αναγνωρίζουν βασικές έννοιες στην Ανάλυση Αλγορίθμων • Μπορείς να περιγράψεις να αναγνωρίζουν τις διάφορες μορφές αναπαράστασης αλγορίθμου πώς βρίσκεις το Μέγιστο να αναφέρουν τους βασικούς τύπους και δομές δεδομένων Κοινό Διαιρέτη δύο αριθ- να διακρίνουν τις βασικές εντολές και δομές που χρησιμοποιούνται μών; σε έναν αλγόριθμο • Τι κάνεις για να εντοπίσεις να προσδιορίζουν τον τρόπο λειτουργίας των δομών δεδομένων μία λέξη σε ένα λεξικό; να εκπονούν απλούς αλγορίθμους να εντοπίζουν και να διορθώνουν τα λογικά λάθη ενός αλγορίθμου Εικόνα 2.8. Ο Αλ Χουαρίζμι να εξηγούν την ανάγκη δημιουργίας της κατάλληλης τεκμηρίωσης. Η μελέτη του Αλ Χουαρίζ- μι μεταφράστηκε στα λατι-2.2.1 Ορισμός αλγορίθμου νικά και άρχιζε με τη φράση «Algoritmi dixit...» (ο αλγό-Η λέξη αλγόριθμος (algorithm) προέρχεται από μια μελέτη του Πέρση ριθμος λέει ....).μαθηματικού Μοχάμεντ Ιμπν Μουσά Αλ Χουαρίζμι (Muh.ammad ibnMūsā al-Khwārizmī), που έζησε περί το 825 μ.Χ. (Εικόνα 2.8). Παρόλα Εικόνα 2.9. Αλγόριθμοςαυτά, η ύπαρξη και η ηλικία μερικών αλγορίθμων αριθμεί χιλιάδες χρό- δεσίματος γραβάταςνια. Σήμερα, το πεδίο της μελέτης των αλγορίθμων (το οποίο καλείταιθεωρία αλγορίθμων) είναι ένα ιδιαίτερα ευρύ πεδίο έρευνας. Γενικά, Ο όρος αλγόριθμος επέζησε επί χίλια χρόνια ως σπάνιος Αλγόριθμος είναι μια πεπερασμένη σειρά ενεργειών, αυστηρά κα- όρος, που σήμαινε κάτι σαν θορισμένων και εκτελέσιμων σε πεπερασμένο χρόνο, που στοχεύ- «συστηματική διαδικασία ουν στην επίλυση ενός προβλήματος. αριθμητικών χειρισμών». Τη σημερινή του αξία απόκτη-Η έννοια του αλγορίθμου δεν συνδέεται αποκλειστικά και μόνο με προ- σε στις αρχές του 20ού αιώ-βλήματα της Πληροφορικής. Για παράδειγμα, το δέσιμο της γραβά- να με την ανάπτυξη της θεω-τας αποτελεί ένα πρόβλημα, για την επίλυση του οποίου χρειάζεται να ρίας αλγορίθμων και φυσικάεκτελεστεί μια πεπερασμένη σειρά ενεργειών (Εικόνα 2.9.). Η αλλη- με τους υπολογιστές.λουχία των ενεργειών οδηγεί στο επιθυμητό αποτέλεσμα. Η αλληλου-χία δεν είναι απαραίτητα μοναδική για την επίτευξη αυτού του, αφού, 19υπάρχουν και άλλοι τρόποι για το δέσιμο της γραβάτας.

2η Ιστορικά, ένας από τους πρώτους αλγορίθμους, είναι ο αλγόριθμος για την εύρεση του Μέγιστου Κοινού Διαιρέτη (ΜΚΔ) δύο ακεραίων αριθ-Θέματα Θεωρητικής μών x και y.Επιστήμης των Υπολογιστών Παράδειγμα 2.4. Να βρεθεί ο Μέγιστος Κοινός Διαιρέτης (ΜΚΔ) δύο«Ο ευκλείδειος αλγόριθμος θετικών ακεραίων αριθμών x και y.είναι ο παππούς όλων τωναλγορίθμων, αφού είναι ο Απάντησηπαλαιότερος μη τετριμμένοςαλγόριθμος που χρησιμοποι- Ο αλγόριθμος περιγράφεται σε ομιλούμενη γλώσσα ως εξής: Θέσε στο z τονείται ακόμα και σήμερα.» διαιρέτη. Αν z = 0, τότε ΜΚΔ είναι ο x. Αν z ≠ 0 τότε διαίρεσε το x με το y,(Ντόναλντ Κνουθ, Donald και έστω z το υπόλοιπο και επανάλαβε τη διαίρεση με τους ακέραιους y καιKnuth, 1981) z αντί για x και y μέχρι το z να γίνει 0.Στον ευκλείδειο αλγόριθμο, Για παράδειγμα προκειμένου να βρεθεί ο ΜΚΔ δύο μη μηδενικών αριθ-δεν έχει σημασία αν θα είναι μών, π.χ. των 78 και 27, σύμφωνα με τον αλγόριθμο μπορείτε να κάνετεη τιμή του y μικρότερη από τις ακόλουθες ενέργειες:την τιμή του x. Έτσι, στηναρχική εκτέλεση του αλγο- Βρείτε το υπόλοιπο της διαίρεσης του 78 με το 27. Το υπόλοιπο είναι 24.ρίθμου έχει επιλεγεί ο πρώ- Ελέγξτε αν είναι 0. Στην περίπτωση αυτή δεν είναι 0. Αφού δεν είναι 0,τος αριθμός να είναι μεγαλύ- βρείτε το υπόλοιπο της διαίρεσης του 27 με το 24. Το υπόλοιπο είναι 3.τερος του δευτέρου. Στη συ- Ελέγξτε αν είναι 0. Στην περίπτωση αυτή δεν είναι 0. Αφού δεν είναι 0,νέχεια θα εκτελεστεί ο αλγό- βρείτε το υπόλοιπο της διαίρεσης του 24 με το 3. Το υπόλοιπο είναι 0.ριθμος με τους ίδιους αριθ- Αφού το υπόλοιπο είναι 0, βρέθηκε ο ΜΚΔ. Ο ΜΚΔ είναι 3.μούς, όπου ο πρώτος αριθμόςθα είναι μικρότερος του δευ- Ο αλγόριθμος αυτός μπορεί να εκφραστεί και με κωδικοποιημένο τρό-τέρου. πο ως εξής:Απαραίτητο είναι οι τιμές 1. Αλγόριθμος Ευκλείδης Για την περιγραφή του αλγορίθμουτων δύο μεταβλητών να εί- 2. Διάβασε x, y χρησιμοποιείται μια γλώσσα στηνναι ακέραιες και μία εκ των 3. z ← y οποία το όνομα του αλγορίθμου (Ευ-δύο μεταβλητών να είναι δι- 4. Όσο z ≠ 0 επανάλαβε κλείδης) καθορίζει την αρχή και τοάφορη του μηδενός. Στην πε- 5. z ← x mod y τέλος του.ρίπτωση αρνητικών τιμών ο 6. x ← yΜΚΔ προκύπτει από τη με- 7. y ← z Οι τιμές εισόδου (x, y) δίνονται μελέτη των απολύτων τιμών 8. Τέλος_επανάληψης την εντολή Διάβασε, ενώ ο ΜΚΔ εί-των δύο αριθμών. 9. Εμφάνισε x ναι η τιμή που παίρνει τελικά η μετα- 10. Τέλος Ευκλείδης βλητή x, η οποία εμφανίζεται.Η εκτέλεση του ευκλείδειουαλγορίθμου, μπορεί να πραγ- Η εύρεση του ΜΚΔ είναι μια επαναληπτική διαδικασία που συνεχί-ματοποιηθεί από κάποιον ζεται όσο το υπόλοιπο (mod) της διαίρεσης x διά του y είναι διάφοροπου δεν χρειάζεται απαραίτη- του μηδενός. Η επαναληπτική διαδικασία έχει την έννοια «όσο ισχύει ητα να έχει κατασκευάσει τον συνθήκη (δηλαδή όσο z ≠ 0) επαναλάμβανε τη διαδικασία, αλλιώς μηναλγόριθμο. Επιπλέον, ο αλ- εκτελείς άλλο τη διαδικασία και συνέχισε στο επόμενο βήμα». Οι εντο-γόριθμος εφόσον κωδικοποι- λές του τύπου x ← y δεν έχουν την έννοια της ισότητας, αλλά της εκχώ-ηθεί σε γλώσσα προγραμμα- ρησης τιμής του δεξιού μέλους στη μεταβλητή του αριστερού μέλους.τισμού, μπορεί να εκτελεστεί Αυτό σημαίνει ότι μετά την εκτέλεση της εντολής η μεταβλητή του αρι-από τον υπολογιστή. στερού μέλους θα έχει τιμή ίση με αυτή του δεξιού μέλους.20

Με βάση τα παραπάνω, ο ευκλείδειος αλγόριθμος για τον υπολογισμό του ΚΕΦΑΛΑΙΟ 2.2ΜΚΔ δύο θετικών ακεραίων αριθμών, περιγράφεται πλήρως με ακρίβειακαι σαφήνεια. Συνεπώς, αν το ζητούμενο είναι να υπολογιστεί με τη χρήση Αλγόριθμοιτου αλγόριθμου Ευκλείδης, ο ΜΚΔτων αριθμών 27 και 78, τότε θα μπορού-σε να αξιοποιηθεί η αρίθμηση των γραμμών του αλγορίθμου και να πραγμα- Η εκτέλεση ενός αλγορίθμουτοποιηθεί εκτέλεσή του στο χαρτί. Σε κάθε επανάληψη υπολογίζονται οι τι- πραγματοποιείται αφού αριθ-μές των x, y και z, οι οποίες παρουσιάζονται στον πίνακα 2.1. Με την ολο- μηθούν οι γραμμές του αλγο-κλήρωση προκύπτει ότι ο ΜΚΔ των αριθμών 27 και 78 είναι ο αριθμός 3. ρίθμου. Για κάθε εντολή που εκτελείται, καταγράφετε τον Πίνακας 2.1. Εικονική εκτέλεση του αριθμό της γραμμής και το ευκλείδειου αλγορίθμου αποτέλεσμα της εκτέλεσης στο αντίστοιχο κελί. Αριθμός εντολής x y z z ≠ 0 Έξοδος Η αρίθμηση των γραμμών του 2 27 78 αλγορίθμου είναι απαραίτητη 3 78 μόνο για την εκτέλεσή του. 4 Αληθής Οι εντολές της γραμμής 1 και 5 27 10 είναι δηλωτικές εντολές 6 78 και δεν αποτυπώνονται στον 7 27 πίνακα 2.1. 4 Αληθής 5 24 Ο Ευκλείδης έζησε περίπου 6 27 από το 330 έως το 275 π.Χ. 7 24 και έγραψε το έργο «Τα Στοι- 4 Αληθής χεία» που αποτελείται από 53 13 βιβλία, τα οποία επιχει- 6 24 ρούν να συστηματοποιήσουν 73 τις μαθηματικές γνώσεις της 4 Αληθής εποχής του. 50 63 Ο ευκλείδειος αλγόριθμος 70 έχει πολλές θεωρητικές και 4 Ψευδής πρακτικές εφαρμογές. Μέσω 93 αυτού μπορούν να δημιουρ- γηθούν αρκετοί παραδοσια-Ο παραπάνω αλγόριθμος, μπορεί να απαντήσει όχι μόνο στη συγκε- κοί μουσικοί ρυθμοί. Χρησι-κριμένη ερώτηση, «να βρεθεί ο ΜΚΔ των 27 και 78», αλλά σε όλες τις μοποιείται στην κρυπτογρα-παρόμοιες ερωτήσεις. Λύνει, δηλαδή, ένα πρόβλημα. Κάθε μία από τις φία, στο ηλεκτρονικό εμπό-ερωτήσεις αυτές λέγεται στιγμιότυπο του προβλήματος. Έτσι, η εύρε- ριο, στην επίλυση διοφαντι-ση του ΜΚΔ των 27 και 78 είναι ένα στιγμιότυπο του προβλήματος της κών εξισώσεων κ.α.εύρεσης του ΜΚΔ δύο θετικών ακεραίων. Δηλαδή, αν εκτελεστούν ταβήματα του αλγορίθμου, θα ολοκληρωθεί η διαδικασία έχοντας πάρειτη σωστή απάντηση για οποιοδήποτε ζευγάρι θετικών ακεραίων.Ωστόσο, ένα θεωρητικό ερώτημα που προκύπτει είναι το ακόλουθο:«γιατί ο αλγόριθμος λύνει οποιοδήποτε στιγμιότυπο του προβλήμα- 21

2η ΕΝΟΤΗΤΑ τος;» Συνήθως, για να λύνει πραγματικά ο αλγόριθμος ένα πρόβλημα, χρειάζεται να μπορεί να αποδειχτεί η ορθότητά του με αυστηρό τρόπο.Θέματα Θεωρητικής Στην περίπτωση του ευκλείδειου αλγορίθμου, αποδεικνύεται από τονΕπιστήμης των Υπολογιστών ίδιο τον Ευκλείδη στο έβδομο βιβλίο των «Στοιχείων» του.Χαρακτηριστικά ενός αλγο- 2.2.2 Χαρακτηριστικά αλγορίθμουρίθμου Κάθε αλγόριθμος είναι σημαντικό να έχει ορισμένα χαρακτηριστικά1. Καθοριστικότητα προκείμενου να θεωρείται πλήρης.(Definiteness) Καθοριστικότητα: Κάθε εντολή ενός αλγορίθμου χρειάζεται να2. Περατότητα (Finiteness) καθορίζεται χωρίς καμία αμφιβολία για τον τρόπο εκτέλεσής της.3. Αποτελεσματικότητα Κατά τη διαίρεση δύο ακεραίων αριθμών, το χαρακτηριστικό της καθο-(Effectiveness) ριστικότητας ικανοποιείται αν έχει ληφθεί υπόψη και η περίπτωση που ο διαιρέτης είναι μηδέν.4. Είσοδος (Input) Περατότητα: Κάθε αλγόριθμος πρέπει να τελειώνει μετά από πεπε-5. Έξοδος (Output) ρασμένα βήματα εκτέλεσης των εντολών του. Ένας αλγόριθμος για να διαθέτει το χαρακτηριστικό της περατότητας, χρειάζεται να προσδιορίζει τη λύση ενός προβλήματος μετά από ένα συγκεκριμένο αριθμό βημάτων και να μην εκτελείται ατέρμονα (δηλα- δή χωρίς να τελειώνει). Αποτελεσματικότητα: Κάθε εντολή ενός αλγορίθμου χρειάζεται να είναι διατυπωμένη απλά και κατανοητά, ώστε να μπορεί να εκτε- λεστεί επακριβώς και σε πεπερασμένο μήκος χρόνου.Όπως θα παρουσιαστεί σε Κατά τη διαίρεση δύο ακέραιων αριθμών, ο αλγόριθμος διαθέτει τοεπόμενη παράγραφο, η είσο- χαρακτηριστικό της αποτελεσματικότητας, αφού οι ακέραιοι αναπαρί-δος σε ένα αλγόριθμο μπορεί στανται ακριβώς και υπάρχει αλγόριθμος για τη διαίρεσή τους (Ευκλεί-να επιτευχθεί με την εντο- δεια Διαίρεση) σε πεπερασμένο χρόνο. Αν όμως επιχειρείται η διαίρε-λή Διάβασε, την εντολή Δε- ση δύο πραγματικών αριθμών που ο καθένας αναπαρίσταται από άπει-δομένα και την εντολή εκχώ- ρα δεκαδικά ψηφία, τότε ο αλγόριθμος δεν διαθέτει το χαρακτηριστικόρησης. Με την εντολή εκχώ- της αποτελεσματικότητας, αφού δεν μπορεί να αναπαρασταθεί πλήρωςρησης δημιουργούνται δεδο- και να εκτελεστεί ακριβώς η συγκεκριμένη διαίρεση.μένα μέσα στον αλγόριθμο(κενό σύνολο μεταβλητών ει- Είσοδος: Κάθε αλγόριθμος χρειάζεται να δέχεται ένα σύνολο μετα-σόδου). βλητών εισόδου (που μπορεί να είναι και το κενό σύνολο), οι οποί- ες αποτελούν τα δεδομένα του αλγορίθμου. 22 Η είσοδος των μεταβλητών μπορεί να επιτευχθεί με κατάλληλες εντο- λές, οι οποίες θα παρουσιαστούν σε επόμενες παραγράφους. Στην πε- ρίπτωση του αλγόριθμου Ευκλείδης που παρουσιάστηκε στο παράδειγ- μα 2.4, αυτό επιτυγχάνεται με την εντολή Διάβασε x, y.

Έξοδος: Κάθε αλγόριθμος χρειάζεται να δημιουργεί κάποιο αποτέ- ΚΕΦΑΛΑΙΟ 2.2 λεσμα. ΑλγόριθμοιΤο αποτέλεσμα του αλγορίθμου, η έξοδός του, είναι μία ή περισσότερεςμεταβλητές ή/και σταθερές τιμές. Η έξοδος μπορεί να επιτευχθεί με κα-τάλληλες εντολές, οι οποίες θα παρουσιαστούν σε επόμενες παραγρά-φους. Στην περίπτωση του αλγόριθμου Ευκλείδης που παρουσιάστη-κε στο παράδειγμα 2.4, αυτό επιτυγχάνεται με την εντολή Εμφάνισε x.2.2.3 Ανάλυση Αλγορίθμων, Θεωρία Υπολογισμού, Η πιο συνηθισμένη ανάλυση Πολυπλοκότητα Αλγορίθμων, ενός αλγορίθμου αφορά το Υπολογισιμότητα Αλγορίθμων. χρόνο εκτέλεσης. Ο χρόνος συνήθως υπολογίζεται σανΗ ανάλυση της συμπεριφοράς ενός αλγορίθμου για συνθήκες παρόμοι- συνάρτηση του αριθμού τωνες με αυτές που εμφανίζονται στην πράξη και η ικανοποιητική απόδο- στοιχειωδών βημάτων πουσή του, παρέχει τη δυνατότητα να πραγματοποιηθεί η υλοποίηση και εκτελούνται στον αλγόριθμο.η εφαρμογή του. Αν δεν επιτυγχάνεται ικανοποιητική απόδοση τότεαπαιτείται ο σχεδιασμός ενός τροποποιημένου αλγορίθμου. Η Θεωρία Υπολογισιμότη- τας ερευνά αν και πόσο απο- Η Θεωρία Υπολογισμού (Theory of computation) είναι το πεδίο της δοτικά κάποια προβλήματα πληροφορικής που ασχολείται τόσο με το πρόβλημα ύπαρξης λύσης μπορούν να επιλυθούν με συ- ενός προβλήματος όσο και αποδοτικότητας των αλγορίθμων για την επί- γκεκριμένα υπολογιστικά μο- λυση των προβλημάτων με βάση ένα δεδομένο μοντέλο υπολογισμού. ντέλα.Το πεδίο της θεωρίας υπολογισμού, διαιρείται σε δύο κλάδους: τη Θε- Η Θεωρία Πολυπλοκότη-ωρία Υπολογισιμότητας (Computability Theory) και τη Θεωρία Πολυ- τας μελετά τους πόρους πουπλοκότητας (Computational Complexity Theory). Συνεπώς, για κάθε απαιτούνται για την επίλυσηαλγόριθμο απαιτείται ανάλυση, μέσω της οποίας: ενός προβλήματος βάσει ενός συγκεκριμένου αλγορίθμου.α) τεκμηριώνεται η ορθότητά του, δηλαδή αν ο αλγόριθμος κάνει πραγματικά τη δουλειά για την οποία έχει σχεδιαστεί καιβ) μετριέται ποσοτικά η απόδοσή του, σε σχέση με διάφορα είδη υπο- λογιστικών πόρων, όπως είναι ο χρόνος και η μνήμη που απαιτεί- ται για την εκτέλεσή του. Η ανάλυση ενός αλγορίθμου είναι η εκτίμηση του πλήθους των υπολογιστικών πόρων που απαιτεί η εκτέλεση του αλγορίθμου.Για παράδειγμα, ο αλγόριθμος Ευκλείδης χρησιμοποιεί τόση μνήμη όσηχρειάζεται για να αποθηκευτούν οι τρεις ακέραιοι x, y, z. Ωστόσο, η εύ-ρεση του πλήθους των εντολών που εκτελούνται δεν είναι τόσο τετριμμέ-νη. Κάθε φορά που πραγματοποιείται η επανάληψη εκτελούνται τέσσεραβήματα (έλεγχος της συνθήκης Όσο...επανάλαβε, υπολογισμός του z καιδύο εντολές εκχώρησης). Επομένως, απαιτούνται 4×α βήματα, όπου α εί-ναι ο αριθμός των επαναλήψεων. Πόσες, όμως, θα είναι οι επαναλήψεις; 23

2η ΕΝΟΤΗΤΑ Το ότι για x = 27 και y = 78 γίνονται τέσσερις επαναλήψεις, δεν είναι πολύ διαφωτιστικό. Θα ήταν χρήσιμο να μπορεί να υπολογιστεί ο αριθ-Θέματα Θεωρητικής μός των επαναλήψεων για κάθε ζευγάρι ακεραίων x, y.Επιστήμης των Υπολογιστών Έχει υπολογιστεί, ότι ο αριθμός των επαναλήψεων είναι περίπου ίσοςΟ Lame απέδειξε ότι ο αριθ- με τον λογάριθμο του x (ή του y). Δηλαδή, ο ευκλείδειος αλγόριθμοςμός των βημάτων του ευκλεί- για να υπολογίσει το ΜΚΔ των x και y, κάνει 4×logx βήματα. Συνήθωςδειου αλγορίθμου για δύο παραλείπονται σταθερές, όπως το 4 και έτσι προκύπτει ότι η πολυπλο-αριθμούς είναι πάντα μικρό- κότητα του αλγόριθμου είναι O(logx) (διαβάζεται «η πολυπλοκότητατερος ή ίσος του πενταπλασί- του αλγορίθμου είναι της τάξης logx»).ου των ψηφίων του μεγαλύτε-ρου από τους δύο αριθμούς. Η πολυπλοκότητα ενός αλγορίθμου δίνει ένα μέτρο της χρονικήςs ≥ 4,785×log10n + 1,6723 καθυστέρησης του αλγορίθμου για την επίλυση ενός προβλήματος.O συμβολισμός Ο Οι περισσότεροι αλγόριθμοι έχουν πολυπλοκότητα χρόνου που ανήκει(O-notation), όπου το Ο είναι σε μια από τις κατηγορίες που φαίνονται στον Πίνακα 2.2. Με n συμ-το αρχικό γράμμα της αγγλι- βολίζεται το μέγεθος του προβλήματος και εξαρτάται από το πρόβλη-κής λέξης order και διαβάζε- μα. Για παράδειγμα, αν ζητείται να ταξινομηθούν k αριθμοί, τότε το μέ-ται «όμικρον κεφαλαίο», χρη- γεθος του προβλήματος είναι k, επομένως n = k.σιμοποιείται για να αναδείξειτη γενική συμπεριφορά (την Πίνακας 2.2: Κατηγορίες πολυπλοκότητας αλγορίθμωντάξη) του αλγορίθμου. Πολυπλοκότητα Ονομασία ΠαρατηρήσειςΥπολογισιμότητα:Τι μπορεί να υπολογιστεί; Ο(1) Σταθερή Κάθε βήμα εκτελείται μια φορά ή το πολύΜπορεί ένας υπολογιστής να μερικές φορέςλύσει οποιοδήποτε πρόβλη- Ο(logn) Λογαριθμικήμα δοθέντος αρκετού χρόνου Αν δεν σημειώνεται αλλιώς, οι λογάριθμοικαι χώρου; Ο(n) Γραμμική είναι δυαδικοί (Δυαδική Αναζήτηση)Πολυπλοκότητα Ο(nlogn)Πόσο γρήγορα μπορεί να λυ- Ο(n2) Τετραγωνική Σειριακή αναζήτησηθεί ένα πρόβλημα; O(n3) ΚυβικήΠόσος χώρος (μνήμη) χρειάζε- Ο(2n) Εκθετική Γρήγορη Ταξινόμησηται για να λυθεί ένα πρόβλημα; Ταξινόμηση με επιλογή Πολλαπλασιασμός πινάκων Μερισμός συνόλου Στην εικόνα 2.10 έχουν παρασταθεί οι καμπύλες των κυριότερων συναρ- τήσεων πολυπλοκότητας, ενώ στον Πίνακα 2.3 παρουσιάζονται οι χρό- νοι εκτέλεσης για διάφορες πολυπλοκότητες και μεγέθη προβλημάτων.Γενικά, τα δεδομένα συνι- Εικόνα 2.10: Καμπύλες των κυριότερων συναρτήσεων πολυπλοκότητας.στούν το μέγεθος της εισό-δου ενός αλγορίθμου. Για πα-ράδειγμα στην ταξινόμηση,το πλήθος των αντικειμένωνπου θα ταξινομηθούν δίνει τομέγεθος του προβλήματος. 24

Πίνακας 2.3. Χρόνοι εκτέλεσης για διάφορες ΚΕΦΑΛΑΙΟ 2.2 πολυπλοκότητες και μεγέθη προβλημάτων ΑλγόριθμοιΤάξη αλγο- Μέγεθος Προβλήματος ρίθμου Η συνάρτηση Ο καλείται πο- 4 16 64 λυωνυμική αν είναι έκφρα- Ο(logn) 6×10-10 sec 1,6×10-8 1,8×10-8 ση πολυωνύμου ως προς n, διαφορετικά καλείταιO(nlogn) 2×10-8 sec 19×10-8 1,2×10-6 μη-πολυωνυμική, αν περιέχει όρους όπως 2n, n! κτλ. ΣτηνO(n) 4×10-8 sec 16×10-8 64×10-8 πράξη οι τρεις τελευταίες πο- λυπλοκότητες χρησιμοποι-O(n2) 2×10-8 sec 2,6×10-6 4×10-5 ούνται μόνο για προβλήματα μικρού μεγέθους.O(n3) 64×10-8 sec 4×10-5 3×10-3O(2n) 16×10-8 sec 65×10-5 5×103 χρόνιαO(n!) 24×10-8 sec 58 ώρες 4×1073 χρόνιαΜετά την επίλυση ενός προβλήματος με ένα αλγόριθμο γίνεται προ- Για το πρόβλημα της ταξινό-σπάθεια να σχεδιαστεί ένας νέος αλγόριθμος με μεγαλύτερη ταχύτη- μησης ενός πίνακα δεν έχειτα εύρεσης της λύσης του προβλήματος. Για παράδειγμα ένας αλγόριθ- βρεθεί μέχρι σήμερα ταχύτε-μος ταξινόμησης με συγκρίσεις (ο οποίος περιγράφεται σε επόμενο κε- ρος αλγόριθμος από τον αλ-φάλαιο) απαιτεί Ο(n2) συγκρίσεις. Υπάρχουν όμως ταχύτεροι αλγόριθ- γόριθμο γρήγορης ταξινό-μοι, όπως ο αλγόριθμος γρήγορης ταξινόμησης (Quicksort), που απαι- μησης, ενώ για το πρόβληματεί Ο(nlogn) συγκρίσεις. του υπολογισμού του ΜΚΔ δεν έχει βρεθεί ταχύτεροςΗ μελέτη αυτού του ζητήματος γίνεται στο πλαίσιο της Θεωρίας Πο- αλγ­ όριθμος από εκείνον τουλυπλοκότητας. Η έρευνα στην περιοχή αυτή προσπαθεί να βρει τους Ευκλείδη. Αυτό οδηγεί, μοι-εγγενείς περιορισμούς στην ταχύτητα των αλγορίθμων για τη λύση συ- ραία, στο ερώτημα: Μήπωςγκεκριμένων προβλημάτων. Έτσι αποδεικνύεται, για παράδειγμα, ότι δεν υπάρχει καλύτερος αλ-δεν είναι δυνατόν να ταξινομηθούν n ακέραιοι με λιγότερο από nlοgn γόριθμος, μήπως δηλαδή τασυγκρίσεις και συνεπώς ο αλγόριθμος γρήγορης ταξινόμησης είναι ου- προβλήματα αυτά έχουν μίασιαστικά βέλτιστος, όσον αφορά την ταχύτητα ταξινόμησης. εγγενή πολυπλοκότητα;2.2.4 Βασικοί τύποι αλγορίθμων Σειριακοί λέγονται οι αλγό- ριθμοι που χρησιμοποιούνΟ ορισμός του αλγορίθμου που δόθηκε στην αρχή αυτού του κεφαλαί- μία κεντρική μονάδα επεξερ-ου, συμφωνεί με τη φιλοσοφία των περισσότερων υπολογιστών σήμε- γασίας και οι εντολές τουςρα, που διαθέτουν μία Κεντρική Μονάδα Επεξεργασίας (ΚΜΕ) στην εκτελούνται σε σειρά η μίαοποία οι εντολές εκτελούνται με σειρά, η μία μετά την άλλη. Για το μετά την άλλη.λόγο αυτό ονομάζονται σειριακοί αλγόριθμοι. Όμως η ύπαρξη προβλη-μάτων στα οποία απαιτείται πολύ μεγάλος χρόνος για τον υπολογισμό Παράλληλοι χαρακτηρίζο-της λύσης ενός προβλήματος, δημιούργησε την ανάγκη εύρεσης αλγο- νται οι αλγόριθμοι που χρη-ρίθμων, όπου ορισμένα ή μία σειρά από βήματα αυτών των αλγορίθ- σιμοποιούν πολλαπλές κε-μων θα μπορούσαν να εκτελούνται παράλληλα (ταυτόχρονα). Σε αυτή ντρικές μονάδες επεξεργασί-την περίπτωση, η εκτέλεση του ενός βήματος δεν εξαρτάται από την ας όπου ορισμένες ή μία σει-ολοκλήρωση της εκτέλεσης του προηγούμενου. Αλγόριθμοι αυτής της ρά από εντολές εκτελούνταιμορφής ονομάζονται παράλληλοι αλγόριθμοι και η υλοποίησή τους γί- παράλληλα (ταυτόχρονα).νεται με την ύπαρξη πολλαπλών ΚΜΕ στο σύστημα του υπολογιστή. 25

2η ΕΝΟΤΗΤΑ Παράδειγμα 2.5. Έστω ότι υπάρχει ένας πίνακας που έχει ως περιεχό- μενο τους αριθμούς:Θέματα ΘεωρητικήςΕπιστήμης των Υπολογιστών 1234Ο πίνακας του παραδείγμα-τος 2.5 είναι μονοδιάστα- 6983τος πίνακας που έχει τέσσεραστοιχεία, στις θέσεις 1, 2, 3, Στόχος είναι να τοποθετηθούν οι αριθμοί σε αύξουσα σειρά από το μι-4. Στη θέση 1 το περιεχόμενο κρότερο στο μεγαλύτερο (αύξουσα ταξινόμηση). Η διαδικασία ταξινό-του πίνακα είναι 6, στη θέση μησης θα επιχειρηθεί με σειριακή και παράλληλη επεξεργασία.2 το περιεχόμενο του πίνακαείναι 9 κτλ. ΑπάντησηΔεν μπορούν να λυθούν όλα ¾¾ Σειριακάτα προβλήματα κάνοντας Εντοπίζεται το μικρότερο στοιχείο του πίνακα (στην περίπτωση αυτήχρήση παράλληλου υπολογι- είναι το 3) και αντιμετατίθεται με το στοιχείο της πρώτης θέσης.σμού. Το σε βάθος σκάψιμογια να ανοιχτεί ένα χαντάκι Εντοπίζεται το μικρότερο από τα υπόλοιπα στοιχεία του πίνακα (πουδεν μπορεί να υλοποιηθεί με είναι το 6) και αντιμετατίθεται με το στοιχείο της δεύτερης θέσης.παράλληλο αλγόριθμο, αφούτο δεύτερο μέτρο δεν είναι Εντοπίζεται το μικρότερο από τα υπόλοιπα στοιχεία του πίνακα (πουπροσβάσιμο αν δεν τελειώσει είναι το 8), το οποίο όμως είναι το τρίτο στοιχείο του πίνακα, οπότε ηπρώτα το πρώτο μέτρο. ταξινόμηση έχει ολοκληρωθεί. 26 ¾¾ Παράλληλα Συγκρίνονται ταυτόχρονα με δύο διαφορετικούς επεξεργαστές το 1ο με το 2ο στοιχείο και το 3ο με το 4ο. Αν δεν είναι σωστά διαταγμένα, αντι- μετατίθενται. Συγκρίνονται ταυτόχρονα με δύο διαφορετικούς επεξεργαστές το 1ο με το 3ο στοιχείο και το 2ο με το 4ο. Αν δεν είναι σωστά διαταγμένα, αντι- μετατίθενται. Τώρα το μικρότερο από όλα τα στοιχεία είναι στη σωστή θέση (την 1η) και το μεγαλύτερο επίσης στη σωστή θέση (την 4η). Ωστόσο τα δύο μεσαία στοιχεία δεν είναι βέβαιο ότι είναι σωστά διαταγμένα. Οπότε απαιτείται μια ακόμη σύγκριση αυτών των δύο από έναν επεξεργαστή και ολοκληρώνεται η ταξινόμηση. Οι αλγόριθμοι επιλύουν προβλήματα. Υπάρχουν απλά και σύνθετα προβλήματα. Λίγα απλά προβλήματα μπορούν να επιλυθούν με δια- δοχική εκτέλεση μερικών βημάτων, αφού τα περισσότερα προβλήμα- τα απαιτούν την εκτέλεση ορισμένων συγκεκριμένων βημάτων πολλές φορές. Αυτοί οι αλγόριθμοι αποκαλούνται επαναληπτικοί. Παράδειγμα 2.6. Να αναπτυχθεί αλγόριθμος ο οποίος θα διαβάζει τον αριθμό Ν και θα υπολογίζει και θα εμφανίζει το Ν παραγοντικό (συμ- βολισμός: Ν!). Το Ν! ορίζεται ως το γινόμενο των ακέραιων αριθμών 1, 2 έως Ν. Δηλαδή Ν!=1·2·3·….· (Ν-1) ·Ν Αν Ν = 5, το 5! = 1·2·3·4·5 = 120

Ο αλγόριθμος υπολογισμού του Ν! με μια επανάληψη βρίσκει το γινό- ΚΕΦΑΛΑΙΟ 2.2μενο (βλέπε παράδειγμα 2.20). ΑλγόριθμοιΌμως το Ν! μπορεί να οριστεί και με άλλο τρόπο, που αποκαλείταιαναδρομικός, ως εξής: Ενδιαφέρον ζήτημα αποτε- λεί ο εντοπισμός του καλύ-{ Ν! = Ν·(Ν-1)! για Ν ≥ 1 (1) τερου τρόπου υποδιαίρεσης0! = 1 (2) των προβλημάτων, για να εί- ναι εφικτή η επεξεργασίαΑπό τη σχέση (1) φαίνεται ότι το παραγοντικό του Ν ορίζεται χρησι- τους από πολλούς επεξεργα-μοποιώντας το παραγοντικό του (Ν - 1). Ο όρος αναδρομικότητα εδώ στές παράλληλα.εκφράζει, ότι για να βρεθεί η τιμή του Ν! πρέπει να βρεθεί η τιμή του(Ν - 1)!, η τιμή του οποίου χρειάζεται την τιμή του (Ν - 2)! κ.ο.κ. Για παράδειγμα, επαναλη- πτικοί αλγόριθμοι είναι ο ευ-Έτσι το 5! κάνει διαδοχικά: κλείδειος αλγόριθμος, καθώς και ο αλγόριθμος ταξινόμη-5! = 4!·5 = 3!·4·5=2!·3·4·5=1!·2·3·4·5=0!·1·2·3·4·5=1·1·2·3·4·5=120 σης με επιλογή που περιγρά- φηκε πιο πριν.Φαίνεται ότι ο υπολογισμός του Ν! με αναδρομικό τρόπο είναι πιο πο-λύπλοκος από τον επαναληπτικό. Ωστόσο σε άλλες περιπτώσεις και ιδί- Αλγόριθμοι που υλοποιούν μιαως σε μερικά δύσκολα προβλήματα η αναδρομή διευκολύνει σημαντικά. αναδρομική σχέση, αποκαλού- νται αναδρομικοί και μερικά2.2.5 Αναπαράσταση αλγορίθμου παραδείγματα παρουσιάζονται στην παράγραφο 2.2.7.6.Προκειμένου να επιτευχθεί η «ακριβής περιγραφή» ενός αλγορίθ-μου, χρησιμοποιείται κάποια γλώσσα που μπορεί να περιγράφει σει- Όταν περιγράφεται στην ομι-ρές ενεργειών με τρόπο αυστηρό, χωρίς ασάφειες και διφορούμενα. Τέ- λούμενη γλώσσα ο τρόπος μετοιες γλώσσες είναι οι γλώσσες προγραμματισμού (με την προϋπόθεση τον οποίο θα μπορέσει κάποιοςότι η σημασιολογία τους είναι αυστηρά διατυπωμένη), μαθηματικά μο- να επισκεφθεί ένα μουσείο,ντέλα, κάποιες συμβολικές γλώσσες που χρησιμοποιούν αυστηρά κα- τότε ο αλγόριθμος έχει διατυ-θορισμένους κανόνες περιγραφής, καθώς και κατάλληλα διαμορφωμέ- πωθεί με φυσική γλώσσα.να υποσύνολα των φυσικών (ομιλούμενων) γλωσσών. Οι φυσικές γλώσσες, είναι οι γλώσσες που μιλούν οιΗ αναπαράσταση των αλγορίθμων μπορεί να πραγματοποιηθεί με: άνθρωποι, ενώ οι τεχνητές γλώσσες έχουν αναπτυχθεί•• Φυσική γλώσσα όπου η αναπαράσταση γίνεται με την ομιλ­ ούμενη κυρίως για διευκόλυνση της γλώσσα, μέσω της οποίας περιγράφονται τα βήματα επίλυσης του επικοινωνίας ιδεών. προβλήματος. Ωστόσο, με τη φυσική γλώσσα μπορούν να παρατη- ρηθούν ασάφειες στις οδηγίες. 27•• Ψευδοκώδικα ή ψευδογλώσσα η οποία είναι μια υποθετική γλώσ- σα για την αναπαράσταση αλγορίθμων με στοιχεία από κάποιες γλώσσες προγραμματισμού, παραλείποντας λεπτομέρειες που δεν είναι ουσιαστικές για την ανθρώπινη κατανόηση του αλγορίθμου.•• Γλώσσα προγραμματισμού η οποία είναι μια τεχνητή γλώσσα, που έχει αναπτυχθεί για να δημιουργεί ή να εκφράζει προγράμματα για τον υπολογιστή. Η αναπαράσταση των αλγορίθμων με γλώσσα προ- γραμματισμού μπορεί να γίνει είτε με οπτικές είτε με κειμενικές γλώσσες προγραμματισμού.

2η ΕΝΟΤΗΤΑ o Στις οπτικές γλώσσες προγραμματισμού, η αναπαράσταση των αλγορίθμων γίνεται μέσα από το γραφικό χειρισμό προ-Θέματα Θεωρητικής γραμματιστικών στοιχείων.Επιστήμης των ΥπολογιστώνΤα κυριότερα χρησιμοποι- o Στις κειμενικές γλώσσες προγραμματισμού, η αναπαράστα-ούμενα γεωμετρικά σχήματα ση των αλγορίθμων γίνεται με τη χρήση σειρών κειμένου που- σύμβολα στα διαγράμματα περιλαμβάνουν λέξεις, αριθμούς και σημεία στίξης.ροής είναι τα ακόλουθα: • Η έλλειψη, που δηλώνει •• Μεθοδολογίες διαγραμματικής αναπαράστασης αλγορίθμων που συνιστούν έναν γραφικό τρόπο παρουσίασης του αλγόριθμου. την αρχή και το τέλος του Από τις διάφορες μεθοδολογίες διαγραμματικής αναπαράστασης αλγορίθμου. αλγορίθμων που έχουν επινοηθεί η πιο διαδεδομένη είναι το διά- γραμμα ροής, όπου η περιγραφή και η αναπαράσταση των αλγορίθ-• Το πλάγιο παραλληλό- μων γίνεται με τη χρήση γεωμετρικών σχημάτων - συμβόλων, όπου γραμμο, που δηλώνει εί- το καθένα δηλώνει μια συγκεκριμένη ενέργεια ή λειτουργία. σοδο ή έξοδο στοιχείων. Παράδειγμα 2.7. Να αναπτυχθεί αλγόριθμος με φυσική γλώσσα, με δι-• Το ορθογώνιο παραλλη- άγραμμα ροής και με ψευδογλώσσα, ο οποίος θα διαβάζει τις τιμές δύο λόγραμμο, που δηλώνει μεταβλητών και θα αντιμεταθέτει το περιεχόμενό τους. Στη συνέχεια την εκτέλεση μιας ή πε- θα εμφανίζει ως αποτέλεσμα το περιεχόμενο των μεταβλητών μετά την ρισσότερων πράξεων. αντιμετάθεση.• Ο ρόμβος, που δηλώνει Να εκτελεστεί ο αλγόριθμος για τις τιμές 8 και 12. μία ερώτηση με δύο εξό- δους για απάντηση. Απάντηση• Στα διαγράμματα ροής, Φυσική γλώσσα: Αφού εισαχθούν οι τιμές δύο μεταβλητών α και β, εκτός των παραπάνω να δώσετε το περιεχόμενο της μεταβλητής α και σε μία νέα μεταβλητή σχημάτων, χρησιμοποιεί- temp (προσωρινή). Στη συνέχεια, να δώσετε το περιεχόμενο της μετα- ται και το βέλος, το οποίο βλητής β στη μεταβλητή α και τέλος να δώσετε το περιεχόμενο της με- δείχνει τη ροή εκτέλεσης ταβλητής temp και στη μεταβλητή β. του αλγορίθμου. Ψευδογλώσσα Διάγραμμα ροήςΟ αλγόριθμος Αντιμετάθεσηαντιμεταθέτει το περιεχόμενο 1. Αλγόριθμος Αντιμετάθεσητων δύο μεταβλητών και πα- 2. Διάβασε α, βρουσιάζεται με τρεις τρόπους 3. temp ← ααναπαράστασης. 4. α ← βΣτην ψευδογλώσσα έχουν 5. β ← tempκαταγραφεί οι ενέργειες που 6. Εμφάνισε α, βπεριγράφονται στο πλαίσιο 7. Τέλος Αντιμετάθεσητης φυσικής γλώσσας σε κω-δικοποιημένη μορφή, ενώ τέ- Αρ. Εντ. α β temp Έξοδοςλος έχει δημιουργηθεί και το 2 8 12αντίστοιχο διάγραμμα ροής. 38 4 12 58 6 12 828

2.2.6 Δεδομένα και αναπαράστασή τους ΚΕΦΑΛΑΙΟ 2.2Ένας αλγόριθμος λαμβάνει κάποια δεδομένα από την είσοδο, τα επεξερ- Αλγόριθμοιγάζεται μέσα από μια σειρά βημάτων και δίνει ως έξοδο τα αποτελέσματα. Εικόνα 2.11. Σχέση δεδομένωνΗ επεξεργασία δεδομένων, η οποία στην πράξη πραγματοποιείται μέσω και πληροφοριώναλγορίθμων, αναφέρεται στην εκτέλεση διαφόρων πράξεων/ λειτουργιώνπάνω στα δεδομένα. Το αποτέλεσμα της επεξεργασίας δεδομένων είναι η Týðïé ÄåäïìÝíùíπληροφορία. Έτσι, θα μπορούσε κανείς γενικεύοντας να πει ότι ένας αλγό- Áñéèìçôéêüòριθμος μετατρέπει τα δεδομένα σε πληροφορία. Για παράδειγμα, ένας τη- ÁêÝñáéïòλεφωνικός αριθμός και ένα ονοματεπώνυμο αποτελούν δεδομένα. Δεν πα- Ðñáãìáôéêüòρέχουν όμως καμία πληροφορία. Πληροφορία παράγεται μόνο αν σχετι-σθούν μεταξύ τους, ότι δηλαδή κάποιο τηλέφωνο ανήκει σε κάποιο συγκε- Áëöáñéèìçôéêüòκριμένο συνδρομητή. Με βάση τις πληροφορίες λαμβάνονται αποφάσεις Ëïãéêüòκαι γίνονται διάφορες ενέργειες. Στη συνέχεια οι ενέργειες αυτές παράγουννέα δεδομένα, αυτά νέες πληροφορίες, οι τελευταίες νέες αποφάσεις και Εικόνα 2.12. Τύποι Δεδομένωνενέργειες κ.ο.κ. όπως φαίνεται στην εικόνα 2.11. Η διεργασία αυτή μπο-ρεί να επαναλαμβάνεται, οι πληροφορίες που παρήχθησαν, να επανατρο- Ο σκληρός δίσκος και η μνή-φοδοτούν μέσω ανάδρασης την είσοδο για επανάληψη του κύκλου κ.ο.κ.. μη flash, αποτελούν παρα- δείγματα βοηθητικής μνήμηςΗ θεωρία αλγορίθμων, μελετά τα δεδομένα κυρίως από τις σκοπιές του του υπολογιστή.υλικού και των γλωσσών προγραμματισμού. 29Όσον αφορά τις γλώσσες προγραμματισμού, κάθε γλώσσα μπορεί ναυποστηρίζει τη χρήση διαφόρων τύπων δεδομένων. Κάθε γλώσσα έχεισυγκεκριμένους τύπους δεδομένων, ενώ μπορούν να δημιουργηθούννέοι τύποι ορισμένοι από το χρήστη. Οι πιο συνήθεις τύποι δεδομένωνείναι οι ακόλουθοι (εικόνα 2.12):Ακέραιος τύπος: για την αναπαράσταση ακεραίων αριθμών.Πραγματικός τύπος: για την αναπαράσταση πραγματικών αριθμών.Λογικός τύπος: για την αναπαράσταση λογικών δεδομένων.Αλφαριθμητικός τύπος: για την αναπαράσταση αλφαριθμητικών δε-δομένων.Σε κάθε τύπο δεδομένων μπορούν να εφαρμοστούν διαφορετικές πρά-ξεις. Επομένως, κατά τον σχεδιασμό ενός αλγορίθμου έχει σημασία τοείδος των τύπων δεδομένων που υποστηρίζονται.Το υλικό επιτρέπει την αποθήκευση των δεδομένων ενός προγράμματοςστην κύρια μνήμη ή και στις περιφερειακές συσκευές ενός υπολογιστή μεδιάφορες μορφές. Με σκοπό την πρόσβαση στα δεδομένα που βρίσκονταιστη βοηθητική μνήμη είναι πιθανό να χρησιμοποιούνται διαφορετικοί αλ-γόριθμοι για την επεξεργασία τους. Επομένως, το υλικό του υπολογιστήέχει επίδραση στο είδος των αλγορίθμων που θα χρησιμοποιηθούν.Τα δεδομένα μπορεί να είναι απλές μεταβλητές, οι οποίες λαμβάνουνμία τιμή κάθε φορά (απλά δεδομένα) ή μπορούν να αποθηκεύονται ωςμία δομή δεδομένων.

2η ΕΝΟΤΗΤΑ Δομή δεδομένων (data structure) είναι ένα σύνολο αποθηκευμένων δεδομένων, τα οποία είναι έτσι οργανωμένα, ώστε να υπόκεινται σεΘέματα Θεωρητικής συγκεκριμένες απαιτούμενες επεξεργασίες.Επιστήμης των Υπολογιστών Ο όρος αναφέρεται σε ένα σύνολο δεδομένων μαζί με ένα σύνολο λει- Εικόνα 2.13. Δισδιάστατος τουργιών που επιτρέπονται στα δεδομένα αυτά. Οι δομές δεδομένων πίνακας είναι πολύ στενά συνδεδεμένες με την έννοια του αλγορίθμου. Είναι πολύ χαρακτηριστική η ακόλουθη «σχέση» που διατύπωσε ο Νικλάους Εικόνα 2.14. Στοίβα Βιρθ (Niklaus Wirth), δημιουργός της γλώσσας Pascal: Εικόνα 2.15. Ουρά Εικόνα 2.16. Λίστα Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα 30 Η ανωτέρω σχέση έχει την έννοια ότι αν κάποιος διαθέτει τον κατάλλη- λο αλγόριθμο και τις δομές δεδομένων, οι οποίες θα χρησιμοποιηθούν, είναι εντελώς άμεση η μετατροπή και υλοποίησή του σε πρόγραμμα σε γλώσσα υπολογιστή. Κάθε δομή δεδομένων αποτελείται, στην πιο γε- νική της μορφή, από ένα σύνολο στοιχείων ή κόμβων. Οι πιο ευρέως χρησιμοποιούμενες δομές δεδομένων είναι ο πίνακας, η στοίβα, η ουρά, η λίστα, το δένδρο και ο γράφος. O πίνακας (table) αποτελείται από ένα σύνολο ομοειδών απλών στοι- χείων, καθένα από τα οποία καθορίζεται με τη βοήθεια ενός ή περισ- σοτέρων δεικτών. Ένας πίνακας μπορεί να είναι μίας, δύο ή περισσο- τέρων διαστάσεων, ανάλογα με το πλήθος δεικτών που χρειάζονται για να καθοριστεί η θέση του. Στην εικόνα 2.13, παρουσιάζεται ένας δισδι- άστατος πίνακας Α με 4 γραμμές και 3 στήλες. Στο παράδειγμα 2.5 είχε παρουσιαστεί ένας μονοδιάστατος πίνακας. Μία στοίβα (stack) είναι μια γραμμική διάταξη στοιχείων, στην οποία εισάγονται και εξάγονται στοιχεία μόνο από το ένα άκρο (εικόνα 2.14). Η λειτουργία της εισαγωγής αποκαλείται ώθηση (push) και της εξαγω- γής απώθηση (pull ή pop). Η φιλοσοφία εισαγωγής και εξαγωγής των στοιχείων ονομάζεται LIFO (Last In, First Out), δηλαδή το τελευταίο εισαγόμενο δεδομένο εξέρχεται και πρώτο. Μια ουρά (queue) αποτελεί μια γραμμική διάταξη στοιχείων, στην οποία εισάγονται νέα στοιχεία από ένα άκρο και εξάγονται υπάρχοντα στοιχεία από το άλλο άκρο (εικόνα 2.15). Η λειτουργία της ουράς απο- καλείται FIFO (First In, First Out), δηλαδή το στοιχείο το οποίο εισά- γεται πρώτο στην ουρά εξέρχεται και πρώτο. Σε μια (συνδεσμική) λίστα (linked list) τα στοιχεία φαίνονται «λογι- κά» ότι είναι γραμμικά διατεταγμένα, χωρίς όμως αυτό να σημαίνει ότι βρίσκονται σε συνεχόμενες θέσεις της μνήμης του υπολογιστή (εικόνα 2.16). Ανεξάρτητα από τη θέση που καταλαμβάνει στη μνήμη ένα δε- δομένο, συσχετίζεται με το επόμενό του με τη βοήθεια κάποιου δείκτη (pointer).

Τo δένδρο (tree) είναι μη γραμμική δομή που αποτελείται από ένα σύ- ΚΕΦΑΛΑΙΟ 2.2νολο κόμβων, οι οποίοι συνδέονται με ακμές (εικόνα 2.17). Υπάρχειμόνο ένας κόμβος, από τον οποίο μόνο ξεκινούν ακμές, που ονομάζε- Αλγόριθμοιται ρίζα (root). Σε όλους τους άλλους κόμβους καταλήγει μία ακμή καιξεκινούν καμία, μία ή περισσότερες. Οι κόμβοι στους οποίους καταλή- Εικόνα 2.17. Δένδρογουν μόνο ακμές, ονομάζονται φύλλα. Εικόνα 2.18. ΓράφοςΟ γράφος (graph) αποτελεί τη πιο γενική δομή δεδομένων μια και απο-τελείται από κόμβους και ακμές χωρίς όμως κάποια ιεράρχηση. Για παράδειγμα, η εγγραφή ενός μαθητή μπορεί να απο-Υπάρχουν διάφοροι τρόποι διάκρισης των δομών δεδομένων. Διακρί- τελείται από το όνομα, τονονται σε στατικές και δυναμικές. Οι στατικές δομές έχουν σταθερό επώνυμο, τον αριθμό κινητούμέγεθος και μπορούν να κατακρατήσουν συγκεκριμένο πλήθος στοι- τηλεφώνου, τη διεύθυνση αλ-χείων. Αντίθετα οι δυναμικές δομές δεν έχουν σταθερό μέγεθος και το ληλογραφίας, την ηλεκτρονι-πλήθος των στοιχείων τους μπορεί να μεγαλώνει ή να μικραίνει καθώς κή διεύθυνση, τη φωτογρα-στη δομή εισάγονται νέα δεδομένα ή διαγράφονται άλλα. φία του κ.ά., που καλούνται πεδία της εγγραφής.Οι δομές δεδομένων διακρίνονται επίσης σε γραμμικές και μη γραμ-μικές. Στις γραμμικές δομές μπορεί να ορισθεί κάποια σχέση διάταξης Εικόνα 2.19. Δομή αρχείουγια δύο οποιαδήποτε διαδοχικά στοιχεία τους. Αυτό σημαίνει ότι κά-ποιο στοιχείο θα είναι πρώτο και κάποιο τελευταίο. Οποιοδήποτε από Αλφάβητοτα υπόλοιπα θα έπεται από το προηγούμενό του και θα προηγείται από Το σύνολο των χαρακτήρωντο επόμενό του. Στις μη γραμμικές δομές δεν μπορεί να οριστεί μια που χρησιμοποιούνται στηνσχέση διάταξης όπως η παραπάνω. Τέτοιες δομές είναι τα δένδρα και οι ψευδογλώσσα περιλαμβάνει:γράφοι. Στα δένδρα ένας κόμβος έχει έναν προηγούμενο αλλά πιθανόν • όλα τα γράμματα της ελ-πολλούς επόμενους. Στους γράφους κάθε κόμβος μπορεί να έχει πολ-λούς προηγούμενους και πολλούς επόμενους. ληνικής ή αγγλικής αλφα- βήτου πεζά και κεφαλαίαΤέλος διάκριση των δομών μπορεί να γίνει και ανάλογα με το είδος της • τους αριθμητικούς χαρα-χρησιμοποιούμενης μνήμης (κύρια ή βοηθητική). Οι δομές δεδομένων κτήρες 0-9βοηθητικής μνήμης αποκαλούνται αρχεία δεδομένων (data files). Ένα • τους επόμενους ειδικούςαρχείο απαρτίζεται από έναν αριθμό ομοειδών εγγραφών (records). χαρακτήρεςΚάθε εγγραφή διαθέτει ορισμένα πεδία (fields), που περιέχουν δεδο- '' εισαγωγικά (διπλά)μένα για μια οντότητα (π.χ. μαθητής), όπως φαίνεται στην εικόνα 2.19. ( ) παρενθέσεις [ ] αγκύλες2.2.7 Εντολές και δομές αλγορίθμου * αστερίσκος + συνΣτην παράγραφο αυτή δίδονται διάφορα παραδείγματα αλγορίθμων, , κόμμαόπου εξετάζονται τα συστατικά μέρη ενός αλγορίθμου και οι τρεις συ- - μείοννιστώσες του (δομή ακολουθίας, δομή επιλογής και δομή επανάληψης) . τελείαξεκινώντας από τις απλούστερες και προχωρώντας προς τις συνθετότε- / κάθετοςρες. Στα περιθώρια παρουσιάζονται ορισμένα βασικά εισαγωγικά στοι- ! θαυμαστικόχεία της χρησιμοποιούμενης ψευδογλώσσας. < μικρότερο από = ίσονΚάθε αλγόριθμος διατυπωμένος σε ψευδογλώσσα ξεκινά με τη γραμμή > μεγαλύτερο από ≤ μικρότερο ή ίσοΑλγόριθμος όνομα_αλγορίθμουκαι τελειώνει με τη γραμμή 31Τέλος όνομα_αλγορίθμου

2η ΕΝΟΤΗΤΑ Μεταξύ αυτών των δύο γραμμών γράφονται οι εντολές του αλγορίθ- μου. Οι εντολές είναι λέξεις (συνήθως ρήματα σε προστακτική) ή συμ-Θέματα Θεωρητικής βολισμοί που προσδιορίζουν μία σαφή ενέργεια. Οι λέξεις που έχουνΕπιστήμης των Υπολογιστών αυστηρά καθορισμένο νόημα στην ψευδογλώσσα καλούνται δεσμευ- μένες λέξεις και στο πλαίσιο του βιβλίου θα γράφονται με έντονα μπλε ≥ μεγαλύτερο ή ίσο γράμματα. ≠ διάφορο ^ άνω βέλος Οι εντολές γράφονται σε ξεχωριστές γραμμές. Επεξηγηματικά σχόλια _ κάτω παύλα μπορούν να γράφονται οπουδήποτε στο σώμα του αλγορίθμου. Ένα κενό σχόλιο αρχίζει με το χαρακτήρα θαυμαστικό (!) και στο πλαίσιο του βι-• και ένα γραφικό σύμβολο βλίου θα γράφεται με πλάγια γράμματα. το ← (αριστερό βέλος) Στη συνέχεια επεξηγούνται οι διάφορες εντολές που μπορούν να χρη-Σταθερές σιμοποιηθούν για τη σύνταξη ενός αλγορίθμου.Οι σταθερές στην ψευδο-γλώσσα μπορεί να είναι 2.2.7.1 Εκχώρηση, Είσοδος και Έξοδος τιμώναριθμητικές, αλφαριθμητικέςή λογικές. Για το σχηματισμό Η γενική μορφή της εντολής εκχώρησης είναι:μιας αριθμητικής σταθεράςχρησιμοποιούνται οι αριθμη- Μεταβλητή ← Έκφρασητικοί χαρακτήρες και πιθα-νά ένας από τους χαρακτή- και η λειτουργία της είναι «εκτελούνται οι πράξεις στην έκφραση και ηρες +, -. Επίσης, μπορεί να τιμή της εκχωρείται (αποδίδεται, μεταβιβάζεται) στη μεταβλητή».χρησιμοποιηθεί το κόμμα γιατο δεκαδικό σημείο. Π.χ. 5, Στην εντολή χρησιμοποιείται το αριστερό βέλος προκειμένου να δεί-123,27, -1, 1000000 κ.λπ. χνει τη φορά της εκχώρησης. Για το σκοπό αυτό χρησιμοποιούνται διά-Για το σχηματισμό μιας αλ- φορα σύμβολα από τις γλώσσες προγραμματισμού. Για παράδειγμαφαριθμητικής σταθεράς χρη- στην Pascal και Delphi χρησιμοποιείται το :=, ενώ στην Basic και τησιμοποιούνται οποιοιδήποτε C το =. Προσοχή, λοιπόν, το σύμβολο της ισότητας ( = ) στις γλώσσεςχαρακτήρες περικλειόμενοι προγραμματισμού ή το αριστερό βέλος ( ← ) στην ψευδογλώσσα, δενσε διπλά εισαγωγικά. είναι σύμβολο εξίσωσης. Το σύμβολο = χρησιμοποιείται ως τελεστήςΜια σταθερά μπορεί να έχει σύγκρισης.οποιοδήποτε πλήθος αριθμη-τικών ή αλφαριθμητικών χα- Αριστερά του συμβόλου ← υπάρχει πάντα μόνο μια μεταβλητή, ενώρακτήρων αντίστοιχα. δεξιά μπορεί να υπάρχει σταθερά, μεταβλητή ή έκφραση.Οι λογικές σταθερές είναιδύο, η Αληθής και Ψευδής. Η εκχώρηση τιμών επιτυγχάνεται και με τις εντολές εισόδου. Η εντολήΜεταβλητές Διάβασε λίστα_μεταβλητώνΓια το σχηματισμό του ονό-ματος μιας μεταβλητής χρη- επιτρέπει την είσοδο τιμών και την εκχώρηση αυτών στις μεταβλητέςσιμοποιείται οποιοσδήποτε που αναφέρονται στη λίστα_μεταβλητών.αριθμός αλφαβητικών ή αριθ-μητικών χαρακτήρων και ο Η εντολή Διάβασε διαφέρει από την εντολή εκχώρησης, γιατί στη δεύ-χαρακτήρας κάτω παύλα. Ο τερη οι τιμές των μεταβλητών προσδιορίζονται κατά τη συγγραφή τουπρώτος χαρακτήρας της με- αλγορίθμου, ενώ στην πρώτη κατά την εκτέλεση του αλγορίθμου.ταβλητής πρέπει να είναι αλ-φαβητικός και δεν μπορεί να Για την έξοδο τιμών (αποτελεσμάτων) μπορούν να χρησιμοποιηθούνχρησιμοποιηθεί δεσμευμένη οι εντολές Γράψε, Εμφάνισε ή Εκτύπωσε με ίδια σύνταξη. Κάθε μίαλέξη ως όνομα μεταβλητής. από αυτές τις εντολές συνοδεύεται από μια λίστα μεταβλητών ή σταθε-Οι μεταβλητές χαρακτηρίζο- ρών. Π.χ. Γράψε ''Τιμή:'', αξία.νται ως αριθμητικές, αλφα-ριθμητικές ή λογικές ανάλογαμε την τιμή που θα αποδοθείσε αυτές. Πριν από την από-δοση κάποιας τιμής σε μια με-ταβλητή (με εντολή εισόδου ήεκχώρησης) η μεταβλητή έχειαπροσδιόριστη τιμή.Οι σταθερές και οι μεταβλη-τές καλούνται και τελεστέοι. 32

2.2.7.2 Δομή ακολουθίας ΚΕΦΑΛΑΙΟ 2.2Η δομή ακολουθίας χρησιμοποιείται για την αντιμετώπιση προβλημά- Αλγόριθμοιτων στα οποία οι εντολές εκτελούνται η μία μετά την άλλη από πάνωπρος τα κάτω. Τελεστές Τελεστές είναι τα σύμβολαΠαράδειγμα 2.8. Είσοδος και έξοδος αριθμών και οι λέξεις που χρησιμο- ποιούνται στις διάφορες πρά-Να διαβαστούν δύο αριθμοί και να υπολογιστεί και να εμφανιστεί το ξεις. Υπάρχουν οι επόμενοιάθροισμά τους. τελεστές: Αλγόριθμος Άθροισμα  Αριθμητικοί Διάβασε α, β Οι αριθμητικοί τελεστές χρη- Σ←α+β σιμοποιούνται για την εκτέ- Εμφάνισε Σ λεση αριθμητικών πράξεων. Τέλος Άθροισμα Είναι οι: + για πρόσθεσηΗ πρώτη ενέργεια που γίνεται είναι η εισαγωγή δεδομένων. Αυτό επιτυγ- - για αφαίρεσηχάνεται με τη χρήση της εντολής Διάβασε. Μετά την εκτέλεση της εντο- * για πολλαπλασιασμόλής αυτής στις μεταβλητές α και β έχουν εκχωρηθεί τιμές, οπότε υπάρ- / για διαίρεσηχει η δυνατότητα επεξεργασίας των τιμών. Εδώ απαιτείται η πρόσθεση mod για το υπόλοιποτων δύο αριθμών και η απόδοση του αθροίσματος σε μια άλλη μεταβλη-τή, τη Σ, που επιτυγχάνεται με την επόμενη εντολή εκχώρησης. Τελευ- ακέραιας διαίρεσηςταία ενέργεια αποτελεί η εμφάνιση (ή εκτύπωση) του αποτελέσματος. div για το πηλίκο ακέ-Παράδειγμα 2.9. Υπολογισμός τελικής αξίας είδους ραιας διαίρεσης ^ για ύψωση σε δύναμηΝα γραφεί αλγόριθμος, ο οποίος να διαβάζει την καθαρή αξία ενός είδουςκαι το ποσοστό ΦΠΑ και να υπολογίζει και να εκτυπώνει την τελική αξία.  Σχεσιακοί Οι σχεσιακοί τελεστές χρη- Αλγόριθμος Υπολογισμός σιμοποιούνται για τη σύ- Διάβασε ΚΑ, ΠΦΠΑ γκριση δύο τιμών. Το αποτέ- ΤΑ ← ΚΑ + ΚΑ * ΠΦΠΑ / 100 λεσμα μιας σύγκρισης είναι Εκτύπωσε ''Τελική Αξία:'', ΤΑ είτε Αληθής είτε Ψευδής. Οι Τέλος Υπολογισμός σχεσιακοί ή συγκριτικοί τε- λεστές είναι οι επόμενοι:Η τελική αξία (ΤΑ) ενός είδους βρίσκεται, αν στην καθαρή αξία (ΚΑ) < μικρότεροπροστεθεί η αξία ΦΠΑ. Αυτό επιτυγχάνεται με την εντολή εκχώρησης. > μεγαλύτερο = ίσο Ο ΦΠΑ (Φόρος Προστιθέμενης Αξίας) είναι ένας φόρος που επιβάλλεται ≤ μικρότερο ή ίσο σε κάθε προϊόν που πωλείται ή σε κάθε παρεχόμενη υπηρεσία. Σήμερα για ≥ μεγαλύτερο ή ίσο τα περισσότερα είδη το ποσοστό του ΦΠΑ είναι 23%, για την εστίαση και ≠ διάφορο είδη πρώτης ανάγκης είναι 13% και για τα βιβλία 6,5%. Όμως στα νησιά του Αιγαί- ου (εκτός της Κρήτης) εφαρμόζονται μειωμένοι συντελεστές. Τα ποσοστά του ΦΠΑ Αντί των τριών τελευταίων αλλάζουν με κυβερνητική απόφαση. τελεστών μπορεί να χρησιμο- ποιηθούν και οι συνδυασμοίΟι εντολές εισόδου/εξόδου μπορούν να συνδυάζονται προκειμένου να των χαρακτήρων <=, >= καιείναι πιο κατανοητή η ενέργεια που απαιτείται από το χρήστη του προ- < > αντίστοιχα.γράμματος που θα υλοποιεί έναν αλγόριθμο. 33Εμφάνισε ''Δώστε τιμές για τα α και β''Διάβασε α, β

2η ΕΝΟΤΗΤΑ Εναλλακτική είσοδος και έξοδος τιμών παρέχεται με τη χρήση των εντολών Δεδομένα και Αποτελέσματα. Η εντολή Δεδομένα γράφεταιΘέματα Θεωρητικής δεύτερη (μετά την εντολή Αλγόριθμος) και περιγράφει εντός των συμ-Επιστήμης των Υπολογιστών βόλων // .... // τα δεδομένα του αλγορίθμου, δηλαδή τις μεταβλητές που Λογικοί έχουν ήδη κάποια τιμή. Αντίστοιχα η εντολή Αποτελέσματα γράφεταιΟι λογικοί τελεστές υλοποι- προτελευταία και περιέχει τις μεταβλητές εξόδου. Οι επόμενοι δύο αλ-ούν τις λογικές πράξεις. Το γόριθμοι για τις ίδιες τιμές εισόδου έχουν την ίδια τιμή εξόδου.αποτέλεσμα μιας λογικήςπράξης είναι Αληθής ή Ψευ- Αλγόριθμος Άθροισμα_1 Αλγόριθμος Άθροισμα_2δής. Λογικοί τελεστές είναι: Διάβασε α, β Δεδομένα // α, β //όχι πράξη άρνησης Σ←α+β Σ←α+βκαι πράξη σύζευξης Γράψε Σ Αποτελέσματα // Σ //ή πράξη διάζευξης Τέλος Άθροισμα_1 Τέλος Άθροισμα_2 Συναρτησιακοί τελεστές Η χρήση των εντολών Δεδομένα και Αποτελέσματα γενικά προτιμάται ή Συναρτήσεις προκειμένου ο αλγόριθμος να απαλλαγεί από τις λεπτομέρειες εισόδου/Μια συνάρτηση χρησιμο- εξόδου και να επικεντρωθεί στο πρόβλημα που επιλύει (εκτός βέβαιαποιείται για να εκτελέσει μια αν το πρόβλημα είναι η εισαγωγή δεδομένων). Επίσης η χρήση τουςπροκαθορισμένη λειτουρ- συνιστάται στην περίπτωση που τα δεδομένα εισόδου ή/και εξόδου εί-γία. Κάθε συνάρτηση έχει ναι πολυπληθή, όπως για παράδειγμα σε προβλήματα επεξεργασίας πι-ένα όνομα ακολουθούμενο νάκων. Τέλος η χρήση τους επιβάλλεται, στην περίπτωση που ένας αλ-από ζεύγος παρενθέσεων που γόριθμος καλείται από άλλον (βλ. παρ. 2.2.7.5).περικλείουν μια μεταβλη-τή ή μια σταθερά ή γενικότε- Αν και η χρήση της μιας ή της άλλης μεθόδου αφήνεται γενικά στην ευ-ρα μια έκφραση. Στην ψευ- χέρεια του συντάκτη του αλγορίθμου, ο μαθητής χρειάζεται να είναι προ-δογλώσσα μπορούν να χρη- σεκτικός στη χρήση των δύο εντολών. Έτσι αν η εκφώνηση ενός θέμα-σιμοποιηθούν όλες οι συνη- τος λέει «Να γραφεί αλγόριθμος ο οποίος να διαβάζει ....»», τότε είναι απαραίτη-θισμένες συναρτήσεις, όπως το να χρησιμοποιηθεί η εντολή Διάβασε. Αντίθετα αν η εκφώνηση λέει «Δίδεταιοι τριγωνομετρικές ΗΜ(x), ένας πίνακας Α. Να γραφεί αλγόριθμος ο οποίος ...», τότε χρειάζεται να χρησιμο-ΣΥΝ(x), ΕΦ(x), οι μαθημα- ποιηθεί η εντολή Δεδομένα.τικές Α_Τ(x) για την απόλυτητιμή, Ε(x) για την ex, ΛΟΓ(x) 2.2.7.3 Δομή επιλογήςγια το δεκαδικό λογάριθμο,ΛΝ(x) για το φυσικό λογάριθ- Στην πράξη πολύ λίγα προβλήματα μπορούν να επιλυθούν με τον προ-μο, Τ_Ρ(x) για την τετραγω- ηγούμενο τρόπο της σειριακής/ακολουθιακής δομής ενεργειών. Συνή-νική ρίζα, και Α_Μ(x) για το θως τα προβλήματα έχουν κάποιες ιδιαιτερότητες και δεν μπορούν ναακέραιο μέρος. εκτελεστούν τα ίδια βήματα για κάθε περίπτωση. Τις πιο πολλές φορές λαμβάνονται κάποιες αποφάσεις με βάση κάποια κριτήρια που μπορεί 34 να είναι διαφορετικά για κάθε στιγμιότυπο ενός προβλήματος. Για πα- ράδειγμα το πρόβλημα της εξόδου (από το σπίτι) σχετίζεται με τις και- ρικές συνθήκες. Έτσι κάποιος μπορεί να πει ότι, «αν βρέχει, θα πάρω ομπρέλα». Με τη δομή επιλογής μπορεί να τροποποιηθεί η σειρά εκτέλεσης των εντολών ενός αλγορίθμου. Η διαδικασία επιλογής περιλαμβάνει τον έλεγχο μιας συνθήκης που μπορεί να έχει δύο τιμές (Αληθής ή Ψευδής) και ακολουθεί η απόφαση εκτέλεσης εντολών με βάση την τιμή αυτής της συνθήκης. Ως συνθήκη εννοείται μια λογική έκφραση στην οποία

ΚΕΦΑΛΑΙΟ 2.2 ΕκφράσειςΜια έκφραση μπορεί να είναι μια σταθερά, μια μεταβλη- ρενθέσεις. Οι παρενθέσεις μπορεί να μεταβάλλουν τηντή, μια συνάρτηση ή ένας συνδυασμός σταθερών, μετα- προτεραιότητα των πράξεων.βλητών, συναρτήσεων, τελεστών και παρενθέσεων.  Στην έκφραση 4 * (1 + 2) εκτελείται πρώτα η πρόσθε-Σε μία έκφραση που αποτελείται από συνδυασμό στοι- ση (1 + 2 = 3) και μετά ο πολλαπλασιασμός (4 * 3 = 12)χείων, εκτελούνται οι πράξεις επί των σταθερών και  Παρατίθεται ένας πίνακας με τη γραφή μερικώνμεταβλητών που ορίζουν οι τελεστές. Οι χρησιμοποι- μαθηματικών τύπων ως εκφράσεις της ψευδογλώσσας.ούμενοι τελεστές έχουν διαφορετική ιεραρχία. Αυτόσημαίνει ότι κάποιες πράξεις μπορεί να προηγούνται Πίνακας 2.4. Μαθηματικοί τύποι ωςαπό κάποιες άλλες σε μια έκφραση. εκφράσεις της ψευδογλώσσαςΗ ιεραρχία των πράξεων είναι η ακόλουθη: Μαθηματικός τύπος Έκφραση ψευδογλώσσαςΑ. Αριθμητικοί τελεστές x-yΣε κάθε έκφραση που υπάρχουν αριθμητικοί τελεστές, (x - y) / zακολουθείται η προσδιορισμένη από τα μαθηματικάιεραρχία των πράξεων. z1. Ύψωση σε δύναμη2. Πολλαπλασιασμός, Διαίρεση, Πηλίκο ακέραιας δι- xy x * y / (z + 1) z+1 αίρεσης, Υπόλοιπο ακέραιας διαίρεσης3. Πρόσθεση, Αφαίρεση (x2)3 (x^2)^3 x23 x^(2^3)Β. Σχεσιακοί τελεστές x * (-y) x(-y)Γ. Λογικοί τελεστές1. όχι Στην ακέραια διαίρεση οι τελεστέοι των τελεστών div2. και και mod είναι υποχρεωτικά θετικοί ακέραιοι αριθμοί.3. ή  Λογικές εκφράσειςΑν οι πράξεις είναι ίδιας ιεραρχίας, τότε εκτελούνταιαπό τα αριστερά προς τα δεξιά. Οι σχεσιακοί τελεστές χρησιμοποιούνται για τη σύ-Οι τελεστέοι ενός αριθμητικού τελεστή πρέπει να είναι γκριση δύο τιμών. Το αποτέλεσμα μιας σύγκρισηςαριθμητικές εκφράσεις. (π.χ. α + β^3) μπορεί να είναι είτε Αληθής είτε Ψευδής.Στις λογικές εκφράσεις μπορούν να χρησιμοποιηθούνόλοι οι τελεστές. Αν μία λογική έκφραση περιλαμβάνει  Στην έκφραση x + y < (z - 1) / t το αποτέλεσμα εί-τελεστές, τότε ένας τουλάχιστον πρέπει να είναι λογι- ναι Αληθής, αν το αποτέλεσμα της πράξης x + y είναικός ή συγκριτικός. (π.χ. α + β^3 > 5 και γ / 3 < 2) μικρότερο από το αποτέλεσμα της πράξης z - 1 διαι-Οι συγκριτικοί τελεστές συνδυάζονται με εκφράσεις ρούμενο δια t.ιδίου τύπου, ενώ οι λογικοί τελεστές μόνο με λογικέςεκφράσεις. (π.χ. α + β > 3, ''ΑΒ'' < ''Γ'') Οι σχεσιακοί τελεστές μπορούν να χρησιμοποιηθούν και με αλφαριθμητικούς τελεστέους. Η σύγκριση αλ-Οι συγκρίσεις λογικών εκφράσεων έχουν νόημα μόνο φαριθμητικών εκφράσεων πραγματοποιείται βάσει δι-στην περίπτωση του = και ≠. εθνών προτύπων που στοχεύουν στην κωδικοποίηση όλων των συστημάτων γραφής. Ο υπολογισμός του Αριθμητικές εκφράσεις αποτελέσματος, λοιπόν, της σύγκρισης αλφαριθμητι- κών εκφράσεων που περιέχουν οποιονδήποτε χαρα-Στη συνέχεια παρουσιάζονται μερικά παραδείγματα κτήρα είναι πέρα από τους στόχους του μαθήματος.και διευκρινίσεις που αφορούν τις αριθμητικές εκφρά- Για το λόγο αυτό, στην ψευδογλώσσα θα γίνεται σύ-σεις. γκριση αλφαριθμητικών εκφράσεων που περιέχουν μόνο τα κεφαλαία γράμματα του ελληνικού αλφαβή- Στην έκφραση 5 + 12 / 3 * 2 - 1 οι πράξεις εκτελού- του, στα οποία ισχύει η αλφαβητική σειρά. Για παρά- δειγμα η λογική έκφραση ''ΑΔΓ'' > ''ΑΒΚ'' είναι αλη-νται με την επόμενη σειρά θής, διότι κατά τη σύγκριση χαρακτήρα προς χαρα- κτήρα από αριστερά προς τα δεξιά εντοπίζεται ότι το1. 12 / 3 (= 4) γράμμα Δ είναι διαφορετικό και μεγαλύτερο του γράμ- ματος Β.2. 4 * 2 (= 8)3. 5 + 8 (= 13)4. 13 - 1 (= 12)Σε μια έκφραση μπορούν να χρησιμοποιηθούν και πα- 35

2η ΕΝΟΤΗΤΑ και είναι αληθής, αν x θετικό και ταυτόχρονα μικρότε- ρο του 2 * k + 1. Οι λογικοί τελεστές πραγματοποιούν τις λογικές πρά- ξεις σε μια έκφραση. Το αποτέλεσμα μιας λογικής Ο τελεστής όχι έχει έναν τελεστέο, ενώ οι και, ή έχουν πράξης είναι πάντα Αληθής ή Ψευδής, σύμφωνα με δύο (ή περισσότερους). τον επόμενο πίνακα τιμών, όπου με Χ και Υ εννοού- νται δύο λογικές εκφράσεις, στις οποίες χρησιμοποι- Προσοχή. Ο συγκριτικός τελεστής ≤ είναι ένας και ούνται μόνο αριθμητικοί και σχεσιακοί τελεστές. διαβάζεται «μικρότερο ή ίσο». Δεν πρέπει να ανα- λύεται και σε μια λογική έκφραση με χρήση του λο- Πίνακας 2.5. Πίνακας τιμών δύο λογικών εκ- γικού τελεστή ή, διότι υπάρχει μεγάλη πιθανότητα φράσεων (όχι, και, ή) να προκληθεί λάθος, ιδιαίτερα αν υπάρχουν πολλοί τελεστές σε μια σύνθετη έκφραση. Χ Υ όχι Χ Χ και Υ Χ ή Υ Αληθής Αληθής Ψευδής Αληθής Αληθής  Η σχέση 0 < x ≤ 10 γράφεται στην ψευδογλώσσα Αληθής Ψευδής Ψευδής Ψευδής Αληθής x > 0 και x ≤ 10 Ψευδής Αληθής Αληθής Ψευδής Αληθής Ψευδής Ψευδής Αληθής Ψευδής Ψευδής Στην πιο πάνω έκφραση δεν μπορούμε να αναλύσουμε την x ≤ 10 σε x = 10 ή x < 10, διότι θα λάβουμε την x > 0 και Σε μια λογική έκφραση οι λογικές πράξεις εκτελού- x = 10 ή x < 10 η οποία για x = -1 θα δώσει τιμή Αληθής. νται μετά τις αριθμητικές και συγκριτικές. Συνιστάται ανεπιφύλακτα να χρησιμοποιούνται παρενθέ- σεις όταν σε έκφραση υπάρχουν πολλοί λογικοί τελεστές.  Η σχέση 0 < x < 2k + 1 γράφεται στην ψευδογλώσ- σα x > 0 και x < 2 * k + 1 υπάρχει τουλάχιστον ένας σχεσιακός τελεστής (δηλαδή η συνθήκη δεν μπορεί να απαρτίζεται από μόνο μια μεταβλητή ή μια σταθερά ή μια αριθμητική παράσταση).Σύγκριση αριθμών με απλή Παράδειγμα 2.10. Να διαβαστεί ένας αριθμός και να εμφανιστεί ηεπιλογή απόλυτη τιμή του.Απλή εντολή επιλογής Η απόλυτη τιμή ενός αριθμού είναι ο ίδιος ο αριθμός, αν είναι θετικός ή ο αντίθετός του, αν είναι αρνητικός. Έτσι για να υπολογιστεί η από-Αν Συνθήκη τότε λυτη τιμή ενός αριθμού αρκεί να ελεγχθεί, αν τυχόν ο δεδομένος αριθ- Εντολές μός είναι αρνητικός και αν ναι, να βρεθεί ο αντίθετός του. Ο συλλογι-Τέλος_αν σμός αυτός οδηγεί στον επόμενο αλγόριθμο.Αν η συνθήκη είναι αληθής, Αλγόριθμος Απόλυτη_τιμή1 Αλγόριθμος Απόλυτη_τιμή2τότε εκτελούνται οι εντολές. Διάβασε α Διάβασε αΟι εντολές μπορούν να είναι Αν α < 0 τότε ! Η εμφάνιση της απόλυτης τιμήςμία ή περισσότερες. α ← α * (-1) ! μπορεί να γίνει με τη χρήση της ! α ←-α ! συνάρτησης Α_Τ(α)ÓõíèÞêç Íáé Τέλος_αν Εμφάνισε Α_Τ(α) Εμφάνισε α Τέλος Απόλυτη_τιμή2 Τέλος Απόλυτη_τιμή1¼÷é Παράδειγμα 2.11. Να αναπτύξετε αλγόριθμο ο οποίος με δεδομένα τα ÅíôïëÝò μήκη τριών ευθυγράμμων τμημάτων θα υπολογίζει και θα εμφανίζει το εμβαδόν του τριγώνου που μπορούν να σχηματίσουν, με βάση τονΕικόνα 2.20. Διάγραμμα ροής της απλής εντολής επιλογής τύπο του Ήρωνα E = ô (ô -á) (ô - â) (ô - ã) , όπου τ είναι η ημιπερίμε- τρος του τριγώνου τ = (α + β + γ) / 2 και α, β, γ τα μήκη των ευθυγράμ-36 μων τμημάτων. Σε περίπτωση που τα ευθύγραμμα τμήματα δεν μπο-

ρούν να σχηματίσουν τρίγωνο, εμφανίζεται κατάλληλο μήνυμα. Για να ΚΕΦΑΛΑΙΟ 2.2σχηματιστεί τρίγωνο θα πρέπει το άθροισμα των μηκών δύο οποιονδή-ποτε ευθυγράμμων τμημάτων να είναι μεγαλύτερο από το μήκος του Αλγόριθμοιάλλου τμήματος. Σύνθετη εντολή επιλογήςΑλγόριθμος Εμβαδό Αν Συνθήκη τότεΔεδομένα // α, β, γ // Εντολές_1Αν α + β > γ και β + γ > α και γ + α > β τότε αλλιώς τ ← (α + β + γ) / 2 Εντολές_2 Εμβ ← Τ_Ρ(τ * (τ - α) * (τ - β) * (τ - γ)) Τέλος_αν Εμφάνισε Εμβ Αν η συνθήκη είναι αληθής,αλλιώς τότε εκτελούνται οι εντολές Εμφάνισε ''Δεν σχηματίζεται τρίγωνο'' 1, αλλιώς (δηλαδή αν η συν-Τέλος_αν θήκη είναι ψευδής) εκτελού-Τέλος Εμβαδό νται οι εντολές 2.Παράδειγμα 2.12. Το όζον (Ο3) αποτελεί έναν από τους ρύπους που Εικόνα 2.21. Διάγραμμα ροήςπροκαλούν μόλυνση στην ατμόσφαιρα. Σε περιπτώσεις που ο ρύπος της σύνθετης εντολής επιλογήςαυτός ξεπεράσει τα 300 μg/m3 τότε πρέπει να ληφθούν μέτρα. Να ανα-πτυχθεί αλγόριθμος ο οποίος θα διαβάζει την τιμή του Ο3 και θα εκτυ- 37πώνει το αντίστοιχο μήνυμα σύμφωνα με τον παρακάτω πίνακα:Τιμές Ο3 (μg/m3) Μήνυμα Τιμή > 250 Προειδοποίηση Τιμή > 300 Μέτρα Α Μέτρα Β Τιμή > 500Επιπλέον, σε περίπτωση που έχουν ξεπεραστεί τα όρια, θα εκτυπώνεικατά πόσο τα ξεπέρασε.Αλγόριθμος Όζον1 Αλγόριθμος Όζον2Διάβασε τ Διάβασε τΑν τ > 250 και τ ≤ 300 τότε Αν τ > 500 τότε Εκτύπωσε ''Προειδοποίηση'' πο ← τ - 300αλλιώς_αν τ > 300 και τ ≤ 500 τότε Εκτύπωσε ''Μέτρα Β'', πο πο ← τ - 300 αλλιώς_αν τ > 300 τότε Εκτύπωσε ''Μέτρα Α'', πο πο ← τ - 300αλλιώς_αν τ > 500 τότε Εκτύπωσε ''Μέτρα A'', πο πο ← τ - 300 αλλιώς_αν τ > 250 τότε Εκτύπωσε ''Μέτρα Β'', πο Εκτύπωσε ''Προειδοποίηση''Τέλος_αν Τέλος_ανΤέλος Όζον1 Τέλος Όζον2Εμφωλευμένες εντολές επιλογήςΣε όλες τις προηγούμενες περιπτώσεις όπου αναφέρεται εντολή ή εντο-λές, τίποτα δεν απαγορεύει αυτές οι εντολές να είναι επίσης εντολέςεπιλογής. Αναφερόμαστε τότε σε εμφωλευμένες εντολές επιλογής.

2η ΕΝΟΤΗΤΑ Παράδειγμα 2.13. ΑριθμομηχανήΘέματα Θεωρητικής Να αναπτυχθεί αλγόριθμος, ο οποίος:Επιστήμης των Υπολογιστών 1. Θα διαβάζει πρώτα έναν αριθμό α, στη συνέχεια έναν από τους χα-Πολλαπλή ρακτήρες +, -, *, /, ανάλογα με την πράξη που θα εκτελέσει και τέ- λος έναν αριθμό β.Αν συνθήκη_1 τότε 2. Θα εκτελεί την αντίστοιχη πράξη και θα τυπώνει το αποτέλεσμα. Σε εντολές_1 περίπτωση που έχει επιλεγεί η πράξη της διαίρεσης, ο αλγόριθμοςαλλιώς_αν συνθήκη_2 τότε πρέπει να ελέγχει αν το β είναι μηδέν και τότε να τυπώνει το μήνυ- εντολές_2 μα «Προσοχή, διαίρεση με το μηδέν» και να οδηγείται στο τέλος του................... 3. Θα εκτυπώνει το μήνυμα «Λάθος πράξη», αν για το χαρακτήρα τηςαλλιώς_αν συνθήκη_ν τότε πράξης δοθεί άλλο σύμβολο. εντολές_ναλλιώς Αλγόριθμος Αριθμομηχανή εντολές_αλλιώςΤέλος_αν Διάβασε α, πράξη, βΑν η συνθήκη_k είναι αλη- Αν πράξη = ''+'' τότεθής, εκτελούνται οι εντολές_kκαι η συνέχεια είναι η επόμε- Εμφάνισε α + βνη εντολή από το Τέλος_αν.Εφόσον καμία συνθήκη δεν αλλιώς_αν πράξη = ''-'' τότεείναι αληθής, τότε εκτελού-νται οι εντολές_αλλιώς. Οι Εμφάνισε α - βεντολές_αλλιώς χρησιμοποι-ούνται κατά περίσταση. αλλιώς_αν πράξη = ''*'' τότεΣημειώνεται ότι, αν σε μια Εμφάνισε α * βπολλαπλή εντολή επιλογήςυπάρχουν πάνω από μία συν- αλλιώς_αν πράξη = ''/'' τότεθήκες αληθείς, τότε εκτελού-νται οι εντολές που ανήκουν Αν β ≠ 0 τότεστην πρώτη αληθή συνθήκηκατά σειρά. Εμφάνισε α / β αλλιώς Εμφάνισε ''Προσοχή, διαίρεση με το μηδέν'' Τέλος_αν αλλιώς Εμφάνισε ''Λάθος πράξη'' Τέλος_αν Τέλος Αριθμομηχανή 2.2.7.4 Δομή επανάληψης Λίγοι αλγόριθμοι χρησιμοποιούν μόνο τις δομές ακολουθίας και επιλο- γής. Στα ρεαλιστικά προβλήματα χρειάζεται συνήθως μια σειρά εντο- λών να επαναληφθεί πολλές φορές. Άλλωστε σε τέτοια προβλήματα «αξίζει τον κόπο» να εκπονηθεί κάποιος αλγόριθμος και στη συνέχεια να υλοποιηθεί ένα αντίστοιχο πρόγραμμα υπολογιστή. Οι επαναληπτικές διαδικασίες μπορεί να έχουν διάφορες μορφές και να εμπεριέχουν συνθήκες επιλογών, όπως αυτές που περιγράφηκαν στις προηγούμενες παραγράφους. Παράδειγμα 2.14. Να εκπονηθεί αλγόριθμος ο οποίος με δεδομένο ένα θετικό ακέραιο αριθμό θα εμφανίζει τους ακέραιους αριθμούς από το 1 μέχρι και τον δεδομένο αριθμό Ν.38

Οι ζητούμενοι αριθμοί μπορούν να παραχθούν με ένα συστηματικό ΚΕΦΑΛΑΙΟ 2.2τρόπο, αφού ο καθένας δημιουργείται από τον προηγούμενό του προ-σθέτοντας το 1. Με την αξιοποίηση αυτού του γεγονότος, ο αλγόριθμος Αλγόριθμοιδημιουργεί κάθε νέο αριθμό σε μια μεταβλητή, έστω i. Αυτό μπορεί ναγίνει με τη χρήση της εντολής εκχώρησης: i ← i + 1. Εντολή Όσο ... επανάλαβεΟπότε προκύπτει το ακόλουθο: Όσο Συνθήκη επανάλαβε Εντολέςi←1 ! Εμφανίζεται το 1 Τέλος_επανάληψηςΕμφάνισε i ! Εμφανίζεται το 2i←i+1 ! Εμφανίζεται το 3 Εκτελούνται οι εντολές όσο ηΕμφάνισε i συνθήκη είναι αληθήςi←i+1Εμφάνισε i Íáé….. ÓõíèÞêç ¼÷éΤο ζεύγος των εντολών i ← i + 1 και Εμφάνισε i επαναλαμβάνεται αυ- ÅíôïëÝòτούσιο. Αν μπορούσαν οι εντολές αυτές να γραφούν μία φορά και ναεκτελεστούν Ν φορές, τότε το πρόβλημα θα λυνόταν. Αυτό επιτυγχά- Εικόνα 2.22. Διάγραμμα ροήςνεται με τις εντολές επανάληψης. Το πόσες φορές μπορούν να εκτελε- της Όσο...επανάλαβεστούν οι εντολές επανάληψης καθορίζεται με διαφορετικούς τρόπους.Στο παράδειγμα οι εντολές εκτελούνται όσο διάστημα η μεταβλητή i Η εντολή i ← i + 1 δεν είναιείναι μικρότερη ή ίση της μεταβλητής Ν. εξίσωση (γιατί και να ήταν δεν έχει λύση), αλλά δρα ωςΚατόπιν αυτών ο αλγόριθμος γίνεται εξής: κάθε φορά που εκτελεί- ται, το περιεχόμενο της μετα-Αλγόριθμος Σειρά_αριθμών βλητής i αυξάνεται κατά 1.Δεδομένα // Ν //i←1 Όλες οι εντολές επανάληψηςΌσο i ≤ Ν επανάλαβε μπορούν να πραγματοποιούν την εκτέλεση ενός συνόλου Εμφάνισε i εντολών πάνω από μια φορά. i←i+1Τέλος_επανάληψης Στην εντολή Όσο… επανάλα-Τέλος Σειρά_αριθμών βε οι εμπεριεχόμενες εντολές μπορεί να μην εκτελεστούνΣυχνά η μεταβλητή i αποκαλείται μετρητής, επειδή αυξάνεται κατά 1. Σε ποτέ, αφού η συνθήκη τερμα-άλλες περιπτώσεις όμως το βήμα αύξησης μπορεί να είναι οποιοδήποτε. τισμού ελέγχεται στην αρχή.Παράδειγμα 2.15. Να γραφεί αλγόριθμος ο οποίος διαβάζει το όνομα Οι εντολές που συγκροτούνενός μαθητή, τους βαθμούς του σε τρία μαθήματα και υπολογίζει και μια εντολή επανάληψης απο-τυπώνει το μέσο όρο του. Ο αλγόριθμος να σταματάει, όταν για όνομα καλούνται βρόχος (αγγλ.μαθητή δοθεί το κενό εμφανίζοντας το πλήθος των μαθητών για τους loop, γαλ. boucle).οποίους υπολογίστηκε ο μέσος όρος. Προσοχή: βρόχος, όχι βρόγ-Αλγόριθμος Μέσος_όρος χος. Βρόχος = θηλιά, βρόγχοςπ←0 = πνευμόνι.Διάβασε όνομαΌσο όνομα ≠ '' '' επανάλαβε 39

2η ΕΝΟΤΗΤΑ Διάβασε α, β, γ Εμφάνισε (α + β + γ) / 3Θέματα Θεωρητικής π←π+1Επιστήμης των Υπολογιστών Διάβασε όνομα Τέλος_επανάληψης Εντολή Εμφάνισε πΕπανάλαβε ... Μέχρις_ότου Τέλος Μέσος_όροςΕπανάλαβε Εντολές Παράδειγμα 2.16. Σε ένα σουπερμάρκετ κάθε πελάτης δικαιούται μιαΜέχρις_ότου Συνθήκη δωροεπιταγή 6 € αν συμπληρώσει 200 πόντους. Να αναπτυχθεί αλγό-Εκτελούνται οι εντολές μέ- ριθμος ο οποίος θα διαβάζει τους πόντους που κερδίζει ένας συγκεκρι-χρις ότου η συνθήκη γίνει μένος πελάτης σε κάθε επίσκεψη στο σουπερμάρκετ και θα εμφανίζειαληθής. μετά από πόσες επισκέψεις παίρνει τη δωροεπιταγή και ποιος είναι ο μέσος όρος πόντων σε κάθε επίσκεψη. ÅíôïëÝò Αλγόριθμος Παράδειγμα ¼÷é Σ←0 ÓõíèÞêç π←0 Íáé Όσο Σ < 200 επανάλαβε Διάβασε πόντοι Εικόνα 2.23. Διάγραμμα ροής Σ ← Σ + πόντοι της Επανάλαβε...Μέχρις_ότου π←π+1 Τέλος_επανάληψης ΜΟ ← Σ / π Εμφάνισε π, ΜΟ Τέλος Παράδειγμα Παράδειγμα 2.17. Κατάλογος επιλογών Πολύ συχνά στις εφαρμογές προβάλλεται στην οθόνη ένας κατάλογος από δυνατές επιλογές (menu) και στη συνέχεια ζητείται από το χρήστη να διαλέξει μία μόνο από αυτές. Στην πιο απλή περίπτωση, οι δυνατές επιλογές είναι αριθμημένες, οπότε απλά ζητείται η εισαγωγή ενός ακέ- ραιου αριθμού. … Επανάλαβε Εμφάνισε ''1. Ενημέρωση'' Εμφάνισε ''2. Εκτύπωση'' Εμφάνισε ''3. Έξοδος'' Εμφάνισε ''Επιλογή:'' Διάβασε Επιλογή Μέχρις_ότου Επιλογή = 1 ή Επιλογή = 2 ή Επιλογή = 3 Στο παραπάνω τμήμα αλγορίθμου, ο βρόχος επαναλαμβάνεται μέχρι να δοθεί 1, 2 ή 3. Με τον τρόπο αυτό προστατεύεται το πρόγραμμα εφαρ- μογής από τυχόν λανθασμένη εισαγωγή τιμών από τον χρήστη. Ας ση- μειωθεί με την ευκαιρία, ότι τα προγράμματα εισαγωγής δεδομένων40

είναι συνήθως τα πιο δύσκολα και μακροσκελή λόγω της ανάγκης να ΚΕΦΑΛΑΙΟ 2.2είναι φιλικά προς το χρήστη. ΑλγόριθμοιΥποτίθεται ότι ανάλογα με την επιλογή, ο πιο πάνω αλγόριθμος δι-ακλαδίζεται σε άλλα σημεία, όπου υπάρχουν οι εντολές υλοποίησης Εντολή Για ... από ... μέχρικάθε λειτουργίας. Για μεταβλητή από τ1 μέχρι τ2 [με_βήμα β]Παράδειγμα 2.18. Να εκπονηθεί αλγόριθμος ο οποίος θα διαβάζει 100 Εντολέςαριθμούς και θα υπολογίζει και θα εμφανίζει το άθροισμά τους. Τέλος_επανάληψης Εκτελούνται οι εντολές μεΑλγόριθμος Άθροισμα_Αριθμών αρχική τιμή της μεταβλητήςΣ←0 τ1 μέχρι και την τελική τιμήΓια i από 1 μέχρι 100 της μεταβλητής τ2. Διάβασε α Στη δομή αυτή τ1, τ2 είναι Σ←Σ+α αριθμητικές σταθερές, μετα-Τέλος_επανάληψης βλητές ή εκφράσεις. ΠρέπειΕμφάνισε ''Άθροισμα:'', Σ τ1 ≤ τ2, αν β > 0 και τ1 ≥ τ2,Τέλος Άθροισμα_Αριθμών αν β < 0. Το βήμα β, αν είναι 1, παραλείπεται. Οι τιμές τωνΣε αυτό το παράδειγμα η εντολή Για…από…μέχρι περιλαμβάνει τ1, τ2 και β μπορεί να είναιόλα τα απαραίτητα δεδομένα για την επανάληψη, δηλαδή αρχική ακέραιες ή πραγματικές.τιμή της μεταβλητής i, τελική τιμή και το βήμα μεταβολής που είναι Αν τ1 > τ2 και β = 0 δεν θα1 και παραλείπεται. Ο βρόχος εκτελείται για όλες τις τιμές της μετα- εκτελεστούν οι εμπεριεχό-βλητής i. μενες εντολές της Για, ενώ αν τ1 ≤ τ2 και β = 0 η εντο-Η εντολή εκχώρησης Σ ← Σ + α δεν είναι εξίσωση και καλύτερα να λή επανάληψης θα εκτελεί-διαβάζεται ως «η νέα τιμή της μεταβλητής Σ είναι η παλιά συν α». ται άπειρες φορές (ατέρμο- νας βρόχος).Συχνά η μεταβλητή Σ αποκαλείται αθροιστής, γιατί της εκχωρείται τοτρέχον και τελικό άθροισμα των αριθμών και δεν πρέπει να λησμονεί- Γενικά οι εμφωλευμένεςται ότι απαιτείται ο μηδενισμός του πριν από την έναρξη της επαναλη- εντολές επιτρέπουν το συν-πτικής διαδικασίας. δυασμό συνιστωσών ενός αλγορίθμου με οποιαδήποτεΗ χρήση της εντολής Για…από…μέχρι γενικά προτιμάται όταν είναι σειρά. Για παράδειγμα: Επα-γνωστός ο αριθμός των φορών που θα γίνει μια επανάληψη, με άλλα νάληψη μέσα σε επιλογή,λόγια όταν είναι γνωστά τα τ1, τ2 και β. επανάληψη μέσα σε επανά- ληψη κ.α.Εμφωλευμένες εντολές επανάληψηςΣε όλες τις προηγούμενες περιπτώσεις όπου αναφέρεται εντολή ή εντο-λές, τίποτα δεν απαγορεύει αυτές οι εντολές να είναι επίσης εντολές επα-νάληψης. Αναφερόμαστε τότε σε εμφωλευμένες εντολές επανάληψης.2.2.7.5 Κλήση αλγόριθμου από αλγόριθμοΈνας αλγόριθμος μπορεί να κληθεί από έναν άλλο αλγόριθμο με χρή-ση της εντολής Κάλεσε.Η επικοινωνία μεταξύ των δύο αλγορίθμων γίνεται ως εξής: 41

2η ΕΝΟΤΗΤΑ Παράδειγμα 2.19.Θέματα Θεωρητικής Αλγόριθμος Καλών Αλγόριθμος ΚαλούμενοςΕπιστήμης των Υπολογιστών Διάβασε α, β Δεδομένα // x, y // Κάλεσε Καλούμενος (α, β, γ, δ) z1 ← x + yΗ εντολή Κάλεσε συνοδεύ- Γράψε ''Άθροισμα:'', γ z2 ← x - yεται με το όνομα του κα- Γράψε ''Διαφορά:'', δ Αποτελέσματα // z1, z2 //λούμενου αλγορίθμου ακο- Τέλος Καλών Τέλος Καλούμενοςλουθούμενο πιθανά από λί-στα μεταβλητών ή σταθερών Η αντιστοιχία των μεταβλητών των δύο αλγορίθμων γίνεται με τη σει-μέσα σε παρενθέσεις. Οι τι- ρά που αναφέρονται στις αντίστοιχες γραμμές, δηλ. α ⇒ x, β ⇒ y καιμές των μεταβλητών ή στα- γ ⇐ z1, δ ⇐ z2. Συνώνυμες μεταβλητές διαφορετικών αλγορίθμων δενθερών μεταβιβάζονται κατά έχουν καμία σχέση μεταξύ τους.την κλήση στις αντίστοιχεςμεταβλητές της γραμμής Δε- Παράδειγμα 2.20. Υπολογισμός συνδυασμώνδομένα του καλούμενου αλ-γορίθμου. Όταν ο καλού- Να εκπονηθεί αλγόριθμος ο οποίος να υπολογίζει το πλήθος των συν-μενος αλγόριθμος τερματί- δυασμών των Ν πραγμάτων ανά Κ. Ο συνδυασμός των Ν πραγμάτωνσει τη λειτουργία του, γίνε-ται επιστροφή στην αμέσως ανά Κ συμβολίζεται με n και δίνεται από τον τύπο n! .επόμενη εντολή της Κάλε- k k!(n - k)!σε. Κατά την επιστροφή μπο-ρεί επίσης να μεταβιβάζονται Αλγόριθμος Παραγοντικό Αλγόριθμος Συνδυασμοίτιμές της εντολής Αποτελέ- Δεδομένα // n // Δεδομένα //n, k//σματα. nfact ← 1 Κάλεσε Παραγοντικό(n, nfact) Για i από 2 μέχρι n Κάλεσε Παραγοντικό(k, kfact)Οι συνδυασμοί απαντούν στο nfact ← nfact * i Κάλεσε Παραγοντικό(n - k, nkfact)ερώτημα κατά πόσους δια- Τέλος_επανάληψης combin ← nfact / (kfact * nkfact)φορετικούς τρόπους είναι δυ- Αποτελέσματα // nfact // Αποτελέσματα //combin//νατό π.χ. να εξαχθούν 5 φύλ- Τέλος Παραγοντικό Τέλος Συνδυασμοίλα από μια τράπουλα των 52φύλλων. Από τον τύπο των συνδυασμών φαίνεται ότι απαιτείται ο υπολογισμός του παραγοντικού τριών διαφορετικών ποσοτήτων. Για το σκοπό αυτόΟ αλγόριθμος Παραγοντικό δημιουργείται ο αλγόριθμος Παραγοντικό, που υπολογίζει το παραγοντι-καλείται τρεις φορές από τον κό ενός αριθμού. Σε αυτόν τον αλγόριθμο με μια απλή επανάληψη βρί-αλγόριθμο Συνδυασμοί. Σε σκεται το παραγοντικό της μεταβλητής n στη μεταβλητή nfact. Ας προ-κάθε κλήση μεταβιβάζεται σεχθεί εδώ, ότι επειδή ζητείται γινόμενο, η αρχική τιμή του nfact είναι 1.η τιμή του αριθμού για τονοποίον ζητείται το παραγο- Με τον ίδιο τρόπο που καλείται ο αλγόριθμος Παραγοντικό από τον αλ-ντικό, στη μεταβλητή n του γόριθμο Συνδυασμοί, μπορεί να κληθεί και ο τελευταίος από έναν άλλοκαλούμενου αλγόριθμου Πα- αλγόριθμο, όπως π.χ. τον επόμενο.ραγοντικό. Όταν ο τελευταί-ος τερματίσει, επιστρέφει το Αλγόριθμος Τράπουλααποτέλεσμα nfact. Εμφάνισε ''Αριθμός Φύλλων:'' Διάβασε fyllaΟι μεταβλητές n και nfact deck ← 52του αλγόριθμου Συνδυασμοί Κάλεσε Συνδυασμοί(deck, fylla, number)δεν έχουν καμία σχέση με τις Εμφάνισε ''Οι συνδυασμοί'', deck, ''φύλλων ανά'', fylla, ''είναι:'', numberσυνώνυμες μεταβλητές του Τέλος Τράπουλααλγορίθμου Παραγοντικό. 42

2.2.7.6 Αναδρομή ΚΕΦΑΛΑΙΟ 2.2Πολλές επιστημονικές εφαρμογές χρησιμοποιούν συναρτήσεις ή σχέ- Αλγόριθμοισεις γενικότερα που χρησιμοποιούν τις ίδιες στον ορισμό τους. Αυτέςοι συναρτήσεις ή σχέσεις ονομάζονται αναδρομικές (Recursive). Από τη μελέτη του παραδείγ- ματος 2.20 αναδεικνύεται καιΠαράδειγμα 2.21. Ν Παραγοντικό ο σωστός τρόπος αντιμετώ- πισης προβλημάτων. ΚάθεΕίδαμε στην παράγραφο 2.2.4 τον αναδρομικό ορισμό του Ν!. Με πρόβλημα διασπάται σε μι-βάση αυτόν τον ορισμό, παρατίθεται ο αναδρομικός αλγόριθμος υπο- κρότερα προβλήματα, ταλογισμού του Ν!. οποία μπορούν να επιλυθούν πιο εύκολα. Ο αλγόριθμοςΑλγόριθμος Ν_Παραγοντικό Αλγόριθμος Factorial επίλυσης ενός προβλήμα-Διάβασε Ν Δεδομένα // n // τος πρέπει να επικεντρώνεταιΚάλεσε Factorial (N, N_Fact) Aν n > 0 τότε στο πρόβλημα που επιλύειΕμφάνισε Ν, ''!='', N_Fact Kάλεσε Factorial(n - 1, Fact) και να αδιαφορεί για το πούΤέλος Ν_Παραγοντικό1 Fact ← Fact * n θα χρησιμοποιηθεί, καθώς αλλιώς και για την είσοδο και έξοδο Fact ← 1 των δεδομένων. Με τη χρήση Τέλος_αν των εντολών Δεδομένα και Αποτελέσματα // Fact // Αποτελέσματα επιτυγχάνεται Τέλος Factorial πολύ εύκολα η μεταφορά των δεδομένων ενός προβλήμα-Παράδειγμα 2.22. Μέγιστος Κοινός Διαιρέτης τος από/ προς τον αλγόριθ- μο επίλυσης. Στα επόμενα θαΠαρατίθεται εδώ η αναδρομική εκδοχή του αλγόριθμου του Ευκλείδη γίνεται αποκλειστική χρήση των εντολών αυτών, εκτόςΑλγόριθμος Ευκλείδης Αλγόριθμος ΜΚΔ από τις περιπτώσεις που η εί-Διάβασε α, β Δεδομένα // x, y // σοδος δεδομένων και η έξο-Κάλεσε ΜΚΔ(α, β) Αν y = 0 τότε δος αποτελεσμάτων είναι τοΤέλος Ευκλείδης Εμφάνισε x προς επίλυση πρόβλημα. αλλιώς x ← x mod y Στο παράδειγμα αυτό, ο αλ- Κάλεσε ΜΚΔ (y, x) γόριθμος Ευκλείδης κα- Τέλος_αν λεί τον αλγόριθμο ΜΚΔ με- Τέλος ΜΚΔ ταβιβάζοντάς του τις τιμές των μεταβλητών α και β στις2.2.8 Βασικές αλγοριθμικές λειτουργίες σε δομές με­ταβλητές x και y αντίστοι- δεδομένων χα. O αλγόριθμος ΜΚΔ με την εντολή Κάλεσε καλεί τονΌπως αναφέρθηκε ήδη, οι δομές δεδομένων διαθέτουν οργανωμένα δε- εαυτό του δίνοντας άλλες τι-δομένα, στα οποία μπορούν να γίνουν διάφορες επεξεργασίες. Οι βασι- μές στις μεταβλητές x και y.κές λειτουργίες ή πράξεις επί των δομών δεδομένων είναι οι ακόλουθες: Προσπέλαση (access), πρόσβαση σε δεδομένα με σκοπό την ανά- γνωση ή εγγραφή ή μετακίνηση. Ανάκτηση (retrieval), η με οποιονδήποτε τρόπο λήψη (ανάγνωση) του περιεχομένου ενός κόμβου. 43

2η ΕΝΟΤΗΤΑ  Αναζήτηση (searching) ενός συνόλου στοιχείων δεδομένων προ- κειμένου να εντοπιστούν ένα ή περισσότερα στοιχεία, που έχουνΘέματα Θεωρητικής μια δεδομένη ιδιότητα.Επιστήμης των Υπολογιστών  Εισαγωγή (insertion), η προσθήκη ή δημιουργία νέων κόμβων σεΣτην πράξη σπάνια υπάρχουν μια υπάρχουσα δομή.όλες οι λειτουργίες σε μιαδομή. Συνήθως παρατηρείται  Μεταβολή ή τροποποίηση (modification), η αλλαγή του περιεχο-το φαινόμενο μια δομή δεδο- μένου ενός κόμβου.μένων να είναι αποδοτικότε-ρη από μια άλλη για κάποια  Διαγραφή (deletion) ή ακύρωση που συνιστά το αντίθετο της ει-λειτουργία π.χ. την αναζήτη- σαγωγής.ση, αλλά λιγότερο αποδοτι-κή για κάποια άλλη λειτουρ-  Ταξινόμηση (sorting), όπου τα στοιχεία μιας δομής διατάσσονταιγία, όπως π.χ. την εισαγωγή. κατά αύξουσα ή φθίνουσα τάξη.Αυτό εξηγεί τόσο την ύπαρ-ξη διαφορετικών δομών όσο Άλλες λειτουργίες είναι η συγχώνευση (merging), κατά την οποία δύοκαι τη σπουδαιότητα της επι- ή περισσότερες ταξινομημένες δομές συνενώνονται σε μια ενιαία δομή,λογής της κατάλληλης δομής η προσάρτηση (append), κατά την οποία μία δομή επικολλάται στο τέ-κάθε φορά. λος μιας άλλης, η αντιγραφή (copying), κ.ά..Oι πίνακες με ένα δείκτη λέ- Η πιο συνηθισμένη και απλή δομή δεδομένων είναι ο πίνακας. Οι πί-γονται μονοδιάστατοι, οι πί- νακες υποστηρίζονται από όλες σχεδόν τις γλώσσες προγραμματισμού.νακες με 2 δείκτες δισδιά- Αποτελούνται από ένα σύνολο ομοειδών απλών στοιχείων. Το μέγεθοςστατοι, .... οι πίνακες με ν ενός πίνακα, δηλαδή το πλήθος των στοιχείων που περιέχει, συνήθωςδείκτες ν-διάστατοι. είναι σταθερό και προκαθορισμένο. Η αναφορά σε ένα στοιχείο του πί- νακα γίνεται με τη χρήση ενός συμβολικού ονόματος που έχει αποδοθείΕδώ χρησιμοποιείται η εντο- στον πίνακα, μαζί με ένα ή περισσότερα στοιχεία που ονομάζονται δεί-λή επανάληψης Όσο συνθή- κτες (indexes). Για παράδειγμα το πέμπτο στοιχείο του πίνακα Α συμ-κη επανάλαβε. Απαιτεί ένα βολίζεται με Α[5].αρχικό διάβασμα προκειμέ-νου να ενεργοποιηθεί η συν- Στη συνέχεια παρουσιάζονται χαρακτηριστικά παραδείγματα επεξερ-θήκη συνέχισης της επανά- γασίας πινάκων.ληψης. Κάθε θετική τιμή πουδιαβάζεται καταχωρείται σε Παράδειγμα 2.23. Εισαγωγή στοιχείων σε πίνακαεπόμενο στοιχείο του πίνακαμε τη χρήση του δείκτη i. Στο  Είσοδος δεδομένων αγνώστου πλήθουςτέλος φυλάσσεται στη μετα-βλητή n η τρέχουσα τιμή του Στο επόμενο τμήμα αλγορίθμου εισάγονται θετικοί αριθμοί στο μονο-i, ώστε να είναι γνωστό το διάστατο πίνακα Α. Δεν είναι γνωστός ο αριθμός των στοιχείων που θαπλήθος των στοιχείων του πί- εισαχθούν, αλλά έχει συμφωνηθεί ότι το τέλος της εισαγωγής θα καθο-νακα στη συνέχεια. ριστεί από την είσοδο ενός αρνητικού αριθμού (ή γενικότερα μιας τιμής που δεν μπορεί να ανήκει στο σύνολο τιμών του πίνακα). i←0 Διάβασε Κ Όσο Κ ≥ 0 επανάλαβε i←i+1 A[i] ← K Διάβασε Κ Τέλος_επανάληψης n←i44

 Είσοδος δεδομένων γνωστού πλήθους ΚΕΦΑΛΑΙΟ 2.2Όταν είναι γνωστό το πλήθος n των τιμών μπορεί να χρησιμοποιηθεί Αλγόριθμοιη εντολή επανάληψης Για … από …μέχρι. Η πιο απλή εκδοχή είναι ηεπόμενη. Πριν από κάθε επεξεργασία πίνακα απαιτείται να εισα-Για i από 1 μέχρι n χθούν δεδομένα σε αυτόν. Η Διάβασε Α[i] εισαγωγή δεδομένων σε πί-Τέλος_επανάληψης νακα μπορεί να είναι επίπο- νη διαδικασία, ιδιαίτερα ανΣε όλες τις προηγούμενες περιπτώσεις εισαγωγής τιμών σε πίνακα, ο ο πίνακας είναι μεγάλος. Επίχρήστης του σχετικού προγράμματος μπορεί να υποβοηθείται με την πλέον τα λάθη πληκτρολόγη-εμφάνιση κατάλληλων μηνυμάτων. σης είναι πολύ συνηθισμένα και πρέπει να υπάρχει τρόποςΠαράδειγμα 2.24. Εκτύπωση πίνακα διόρθωσης κάποιων τιμών.Η εκτύπωση των στοιχείων του πίνακα, καθώς και της θέσης που υπάρ-χει το στοιχείο, επιτυγχάνεται με τις επόμενες εντολές:Για i από 1 μέχρι n Εμφάνισε i, Α[i]Τέλος_επανάληψηςΠαράδειγμα 2.25. Τροποποίηση στοιχείων πίνακαΜετά την εισαγωγή στοιχείων και την εκτύπωση μπορεί να απαιτείταιη διόρθωση ενός ή περισσοτέρων στοιχείων.Διάβασε iΌσο i > 0 και i <= n επανάλαβε Εμφάνισε Α[i] Διάβασε Α[i] Διάβασε iΤέλος_επανάληψηςΣτον αλγόριθμο αυτό η επανάληψη εκτελείται όσο δίνεται τιμή του iεντός ορίων. Κάθε φορά εμφανίζεται το στοιχείο Α[i] και ζητείται ηεισαγωγή μιας άλλης τιμής που την αντικαθιστά.Μετά την εισαγωγή δεδομένων σε ένα πίνακα μπορεί να ακολουθήσειη επεξεργασία του. Στη συνέχεια παρουσιάζονται μερικές συνηθισμέ-νες επεξεργασίες πινάκων.Παράδειγμα 2.26. Άθροισμα στοιχείων πίνακαΔίδεται ο μονοδιάστατος πίνακας Β που περιέχει Ν βαθμούς μαθητών.Να αναπτυχθεί αλγόριθμος, ο οποίος να υπολογίζει και να εμφανίζει τομέσο όρο βαθμολογίας των μαθητών. 45

2η ΕΝΟΤΗΤΑ Αλγόριθμος Βαθμολογία Με το βρόχο Για i από 1 μέχρι Ν δια- Δεδομένα // Β, Ν // τρέχονται όλα τα στοιχεία του πίνακα καιΘέματα Θεωρητικής Σ←0 κάθε ένα αθροίζεται στη μεταβλητή Σ, ηΕπιστήμης των Υπολογιστών Για i από 1 μέχρι Ν οποία έχει μηδενιστεί πριν από την έναρξη Σ ← Σ + Β[i] της επανάληψης. Ο Μέσος όρος είναι τοΗ επανάληψη θα μπορούσε Τέλος_επανάληψης πηλίκο του αθροίσματος όλων των στοι-να ξεκινά από 1. ΜΟ ← Σ / Ν χείων δια του πλήθους των στοιχείων. Εμφάνισε ''Μ.Ο.:'', ΜΟ Τέλος Βαθμολογία Για τη δημιουργία προγράμματος που να υλοποιεί τον παραπάνω αλ- γόριθμο και προκειμένου να γίνει ο έλεγχος ορθότητας, απαιτείται και η εισαγωγή κάποιων δεδομένων. Σύμφωνα με όσα αναφέρθηκαν στις προηγούμενες παραγράφους αυτό μπορεί να γίνει π.χ. με τον επόμενο αλγόριθμο. Αλγόριθμος Επεξεργασία_Πίνακα Στις πρώτες γραμμές έχουν γραφεί Διάβασε n οι σχετικές εντολές με τις οποίες Για i από 1 μέχρι n γίνεται η εισαγωγή δεδομένων στο Διάβασε Α[i] μονοδιάστατο πίνακα Α, ο οποίος Τέλος_επανάληψης έχει n στοιχεία. Στη συνέχεια προ- Κάλεσε Βαθμολογία (Α, n) κειμένου να βρεθεί ο μέσος όρος Τέλος Επεξεργασία_Πίνακα των στοιχείων του Α, καλείται ο αλγόριθμος Βαθμολογία, που δη- μιουργήθηκε για το σκοπό αυτό. Κατά την κλήση μεταβιβάζονται στον πίνακα Β οι τιμές των στοιχεί- ων του πίνακα Α και στη μεταβλη- τή Ν η τιμή της μεταβλητής n. Παράδειγμα 2.27. Μέγιστο στοιχείο πίνακα Δίδεται ο μονοδιάστατος πίνακας Β που περιέχει Ν βαθμούς μαθητών. Να αναπτυχθεί αλγόριθμος, ο οποίος να βρίσκει και να εμφανίζει την υψηλότερη βαθμολογία. Αλγόριθμος Μέγιστο_πίνακα Στη μεταβλητή max εκχωρείται η τιμή του πρώτου στοιχείου του πίνακα. Στη Δεδομένα // Β, Ν // συνέχεια με το βρόχο Για i από 2 μέχρι Ν εξετάζονται όλα τα υπόλοιπα στοιχεία max ← Β[1] του πίνακα. Για κάθε ένα, αν είναι με- γαλύτερο από το max, τότε αντικαθιστά- Για i από 2 μέχρι Ν ται η τιμή του max με το νέο στοιχείο. Δηλαδή στη μεταβλητή max εκχωρείται Αν Β[i] > max τότε το εκάστοτε μέγιστο στοιχείο, οπότε στο τέλος της επανάληψης θα έχει το μέγι- max ← Β[i] στο στοιχείο του πίνακα. Τέλος_αν Τέλος_επανάληψης Εμφάνισε ''Μέγιστο:'', max Τέλος Μέγιστο_πίνακα46

Παράδειγμα 2.28. Επεξεργασία δισδιάστατου πίνακα ΚΕΦΑΛΑΙΟ 2.2Να αναπτυχθεί αλγόριθμος ο οποίος με δεδομένο το πλήθος των μαθητών Αλγόριθμοιτης Γ’ γυμνασίου ενός σχολείου και τους βαθμούς των μαθητών στη γυ-μναστική, σε καθένα από τα 3 τρίμηνα, να υπολογίζει και να επιστρέφει το Για την εισαγωγή δεδομένωνμέσο όρο βαθμολογίας κάθε μαθητή και το συνολικό μέσο όρο. σε ένα δισδιάστατο πίνακα Α που έχει Ν γραμμές και ΜΟ πίνακας Β έχει Ν γραμμές και 3 στήλες. Σε κάθε μία γραμμή υπάρ- στήλες, θα μπορούσε να ανα-χουν οι βαθμολογίες των τριών τριμήνων για κάθε ένα μαθητή. πτυχθεί το ακόλουθο τμήμα αλγορίθμου:Αλγόριθμος Αθροίσματα Με το διπλό βρόχο Για i και Για j σαρώ- Για i από 1 μέχρι Ν Για j από 1 μέχρι ΜΔεδομένα // Β, Ν // νονται κατά γραμμή όλα τα στοιχεία του Διάβασε Α[i, j]Σ←0 πίνακα Β. Σε κάθε μία γραμμή, δηλαδή Τέλος_επανάληψηςΓια i από 1 μέχρι Ν για κάθε μία τιμή του i, μηδενίζεται το Τέλος_επανάληψης ΣΜ (άθροισμα βαθμών μαθητή) και ακο- ΣΜ ← 0 λούθως με τον εσωτερικό βρόχο αθροίζο- Ο αλγόριθμος αθροίζει τα Για j από 1 μέχρι 3 νται όλα τα στοιχεία της γραμμής αυτής. στοιχεία κάθε γραμμής ενός Όταν ολοκληρωθεί ο εσωτερικός βρόχος, δισδιάστατου πίνακα Ν ΣΜ ← ΣΜ + Β[i, j] στο ΜΟΒ[i] βρίσκεται ο μέσος όρος των γραμμών και 3 στηλών. Τέλος_επανάληψης στοιχείων της εκάστοτε γραμμής, δηλα- ΜΟΒ[i]← ΣΜ / 3 δή ο μέσος όρος κάθε μαθητή στα τρία Ο μέσος όρος είναι το πηλίκο Σ ← Σ + ΣΜ του αθροίσματος δια του πλή- θους των στοιχείων του δισ-Τέλος_επανάληψης τρίμηνα. Το άθροισμα που υπολογίστη- διάστατου πίνακα. Το πλήθος των στοιχείων του είναι Ν*3.ΜΟ ← Σ / (Ν * 3) κε ανά γραμμή αξιοποιείται και αυξάνει Κάθε σχολείο μπορεί να έχειΑποτελέσματα // ΜΟΒ, ΜΟ // τη μεταβλητή Σ κατά το άθροισμα γραμ- ένα περίπτερο. μής, η οποία στο τέλος θα έχει το άθροι-Τέλος Αθροίσματα σμα όλων των στοιχείων του πίνακα. Στον αλγόριθμο είναι δεδο­ μένος ο πίνακας Α και τοΠαράδειγμα 2.29. Σειριακή αναζήτηση πλήθος των στοιχείων του (Ν).Σε ένα μονοδιάστατο πίνακα είναι καταχωρημένα τα ονόματα των σχολεί- Η λογική μεταβλητή Βρέθη-ων που συμμετέχουν σε έναν διαγωνισμό επιχειρηματικότητας και έχουν κε έχει την αρχική τιμή Ψευ-κατασκευάσει ένα χώρο παρουσίασης του επιχειρηματικού τους σχεδίου δής, όπου θεωρείται ότι δεν(που εν συντομία θα λέγεται περίπτερο). Ο αριθμός του περιπτέρου κάθε υπάρχει το ζητούμενο σχο-σχολείου είναι η θέση του σχολείου στον πίνακα. Δηλαδή στο πρώτο κελί λείο και η μεταβλητή Θέσητου πίνακα είναι το όνομα του σχολείου που έχει το περίπτερο με αριθμό 1, έχει την αρχική τιμή 0 γιαστο δεύτερο κελί του πίνακα είναι το όνομα του σχολείου που έχει το περί- τον ίδιο λόγο.πτερο με αριθμό 2 κ.ο.κ. Να αναπτυχθεί αλγόριθμος ο οποίος με δεδομέ- Η επανάληψη του αλγορίθ-νο το πλήθος των σχολείων που συμμετέχουν στο διαγωνισμό με περίπτε- μου εκτελείται όσο δεν τε-ρο και τον πίνακα με τα ονόματα των σχολείων, να διαβάζει το όνομα ενός λείωσε η σάρωση του πίνα-σχολείου και να ψάχνει στον πίνακα, αν υπάρχει αυτό το σχολείο. Ο αλγό- κα (i ≤ Ν) και όσο δεν βρέ-ριθμος θα επιστρέφει το αποτέλεσμα της αναζήτησης, δηλαδή αν υπάρχει θηκε το στοιχείο (Βρέθηκε =ή όχι το αναζητούμενο σχολείο, και αν υπάρχει τη θέση του στον πίνακα, Ψευδής).αλλιώς ως θέση την τιμή μηδέν. 47Αλγόριθμος ΑναζήτησηΔεδομένα // Α, Ν //Εμφάνισε ''Αναζητούμενο σχολείο:''Διάβασε Κi←1Βρέθηκε ← ΨευδήςΘέση ← 0

2η ΕΝΟΤΗΤΑ Όσο i ≤ Ν και Βρέθηκε = Ψευδής επανάλαβεΘέματα Θεωρητικής Αν Κ = Α[i] τότεΕπιστήμης των Υπολογιστών Θέση ← i Εικόνα 2.24. Σειριακή αναζήτηση. Βρέθηκε ← ΑληθήςΗ μέθοδος της ταξινόμη- αλλιώςσης με επιλογή βασίζεται σταακόλουθα τρία βήματα: i←i+1α. επιλογή του στοιχείου μετην ελάχιστη τιμή. Tέλος_ανβ. ανταλλαγή του με το πρώ-το στοιχείο. Τέλος_επανάληψηςγ. επανάληψη των (α), (β) μετα υπόλοιπα στοιχεία. Αποτελέσματα // Βρέθηκε, Θέση //Ο αλγόριθμος ταξινόμησης Τέλος Αναζήτησημε επιλογή είναι πολυπλοκό-τητας Ο(n2) Τα αποτελέσματα είναι η μεταβλητή Βρέθηκε, η οποία, αν είναι αληθής σημαίνει ότι η αναζήτηση ήταν επιτυχής και η μεταβλητή Θέση, που έχει τη θέση του στοιχείου στον πίνακα, εφ’ όσον βρέθηκε, αλλιώς θα έχουν την τιμή Ψευδής και μηδέν αντίστοιχα. Η τιμή μηδέν δεν μπορεί να είναι θέση πίνακα. Παράδειγμα 2.30. Ταξινόμηση με επιλογή Να αναπτυχθεί αλγόριθμος ο οποίος με δεδομένο το πλήθος των μαθη- τών της Γ’ γυμνασίου ενός σχολείου και τον τελικό βαθμό του κάθε μα- θητή στο μάθημα «Πληροφορική», να ταξινομεί τον πίνακα των βαθ- μών σε αύξουσα τάξη, από το μικρότερο στο μεγαλύτερο βαθμό. Στη συνέχεια να επιστρέφει τον ταξινομημένο πίνακα. Αλγόριθμος Ταξινόμηση_με_επιλογή Δεδομένα // A, N // Για i από 1 μέχρι Ν j←i min ← A[j] Για k από i + 1 μέχρι Ν Αν A[k] < min τότε j←k min ← A[j] Τέλος_αν Τέλος_επανάληψης temp ← A[i] A[i] ← A[j] A[j] ← temp Τέλος_επανάληψης Αποτελέσματα // Α // Τέλος Ταξινόμηση_με_επιλογή 2.2.9 Εκσφαλμάτωση σε λογικά λάθη Ένας αλγόριθμος χρειάζεται να δοκιμαστεί σε διαφορετικές συνθήκες και με ποικιλία δεδομένων ώστε να συγκριθούν τα παραγόμενα αποτελέσματα με τα αναμενόμενα, και να προβλεφτούν απρόσμενες καταστάσεις λάθους.48

Ως εκσφαλμάτωση των λογικών λαθών ενός αλγορίθμου προσδιο- ΚΕΦΑΛΑΙΟ 2.2 ρίζεται η διαδικασία εύρεσης των λογικών λαθών που υπάρχουν σε αυτόν. ΑλγόριθμοιΗ ανίχνευση τέτοιων λαθών δεν είναι δυνατό να πραγματοποιηθεί από Το πρώτο βήμα στην εύρεσηκάποιο εργαλείο του υπολογιστή και διαπιστώνονται μόνο με τη δια- των λογικών λαθών είναι ναδικασία ελέγχου και την ανάλυση των αποτελεσμάτων του. Ένα λογι- γίνει προσπάθεια εντοπισμούκό λάθος είναι ένα λάθος που, ενώ εκτελείται ο αλγόριθμος, τα αποτε- των πιθανών πηγών τους. Γιαλέσματά του δεν είναι σωστά. Αυτό μπορεί να οφείλεται είτε σε λανθα- να επιτευχθεί αυτό χρειάζε-σμένη προσέγγιση για το πώς θα λυθεί το πρόβλημα, είτε σε λανθασμέ- ται να δώσετε προσοχή στανη υλοποίηση της προσέγγισης που επιλέχθηκε. Κατά γενική ομολογία, αποτελέσματα που έχει ωςτα λογικά λάθη είναι δύσκολο να εντοπιστούν. έξοδο ο αλγόριθμος και να σκεφτείτε πιθανές αιτίες πουΠαράδειγμα 2.31. Λανθασμένος αλγόριθμος μπορεί να οδήγησαν σε τέ- τοιου είδους αποτελέσματα.Με σκοπό να αναπτυχθεί αλγόριθμος ο οποίος με δεδομένες τις τιμέςδύο μεταβλητών, θα αντιμεταθέτει το περιεχόμενο των δύο μεταβλη- Η εκτέλεση του αλγορίθμουτών και θα επιστρέφει ως αποτέλεσμα το περιεχόμενο των μεταβλητών με το χέρι είναι πολύ χρήσι-μετά την αντιμετάθεση γράφτηκε ο ακόλουθος λανθασμένος αλγόριθ- μη διαδικασία για τον εντοπι-μος σε ψευδογλώσσα. Ζητείται να εντοπιστούν τα λογικά λάθη. σμό των λογικών λαθών.1. Αλγόριθμος Αντιμετάθεση Για το λόγο αυτό χρειάζεται2. Δεδομένα // α, β // να δοκιμάζετε εξονυχιστικά3. α ← β τον αλγόριθμό σας με διάφο-4. β ← α ρα παραδείγματα, απλά, σύν-5. Αποτελέσματα // α, β // θετα και ασυνήθιστα, για να6. Τέλος Αντιμετάθεση βεβαιωθείτε ότι είναι σωστός.Απάντηση Αν κάποιο από τα παραδείγ- ματα δεν δίνει το αναμενόμε-Το πρώτο βήμα είναι η εκτέλεση του αλγορίθμου με πίνακα παρακο- νο αποτέλεσμα τότε υπάρχειλούθησης τιμών για να ελεγχθεί η λειτουργία του. παράλειψη στον κώδικα και δεν έχει καλυφθεί η σχετική Αριθμός Εντολής α β Έξοδος περίπτωση. 2 8 12 Μόλις βρείτε τι φταίει, 3 12 εμπλουτίζετε την αρχική σας 4 12 σχεδίαση ώστε να καλύψετε 5 12 12 και αυτό το είδος περιπτώσε- ων και κάνετε τις απαραίτη-Από την εκτέλεση φαίνεται ότι εκτυπώνει σωστά την τιμή της μετα- τες προσθήκες.βλητής α, αλλά όχι της β. Αφού διαπιστωθεί το λάθος χρειάζεται ναπροσδιοριστεί η απαιτούμενη διόρθωση. Από τον αλγόριθμο απουσιά- Η διαδικασία εκσφαλμάτω-ζει η μεταβλητή στην οποία θα εκχωρούταν προσωρινά η τιμή μίας εκ σης περιλαμβάνει:των δύο μεταβλητών. • Τη διαπίστωση του εί- δους του λάθους. • Την ανεύρεση του ανε- ξάρτητου τμήματος του αλγορίθμου που εκτε- λεί τη λανθασμένη λει- τουργία. • Την ανεύρεση του λά- θους μέσα σε αυτό το ανεξάρτητο τμήμα του αλγορίθμου. 49