ΑΛΓΟΡΙΘΜΙΚΗ

ΑΛΓΟΡΙΘΜΙΚΗ - ΕΞΕΤΑΣΤΙΚΗ Α ΕΞΑΜΗΝΟΥ

(A.25) Ποιούς τρόπους γνωρίζετε για την αναπαράσταση ενός αλγορίθμου; Δώστε μία σύντομη περιγραφή για τον καθένα.

1) Ελεύθερο κείμενο: Αποτελεί τον πιο ανεπεξέργαστο και αδόμητο τρόπο παρουσίασης αλγορίθμου. Μπορεί εύκολα να οδηγήσει σε μη εκτελέσιμη παρουσίαση παραβιάζοντας την "αποτελεσματικότητα".

2) Φυσική γλώσσα κατά βήματα: Στην περίπτωση αυτή χρειάζεται προσοχή, γιατί μπορεί να παραβιασθεί ο "καθορισμός".

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

(A.46) Με ποιούς τρόπους πραγματοποιείται η περιγραφή ενός αλγορίθμου;

1) Ελεύθερο Κείμενο. Αποτελεί τον πιο ανεπεξέργαστο και αδόμητο τρόπο παρουσίασης αλγορίθμου. Έτσι εγκυμονεί τον κίνδυνο ότι μπορεί εύκολα να οδηγήσει σε μη εκτελέσιμη παρουσίαση παραβιάζοντας το τελευταίο χαρακτηριστικό των αλγορίθμων, δηλαδή την αποτελεσματικότητα.

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

3) Διαγραμματικές Τεχνικές. Συνιστούν ένα γραφικό τρόπο παρουσίασης του αλγορίθμου. Από τις διάφορες διαγραμματικές τεχνικές που έχουν επινοηθεί, η πιο παλιά και η πιο γνωστή ίσως, είναι το διάγραμμα ροής (flow chart). Ωστόσο η χρήση διαγραμμάτων ροής για την παρουσίαση αλγορίθμων δεν αποτελεί την καλύτερη λύση, γι'αυτό και εμφανίζονται όλο και σπανιότερα στη βιβλιογραφία και στην πράξη.

4) Κωδικοποίηση . Με ένα πρόγραμμα γραμμένο είτε σε μία ψευδογλώσσα είτε σε κάποια γλώσσα προγραμματισμού που όταν εκτελεσθεί θα δώσει τα ίδια αποτελέσματα με τον αλγόριθμο.

(A.24) Ποιές είναι οι διαφορές ανάμεσα στην επαναληπτική εντολή "όσο•••.επανάλαβε" (while ... do) και την επαναληπτική εντολή "αρχή_επανάληψης•••μέχρις_ότου" (repeat.until);

Η διαφορά, έγκειται στο ότι η επαναληπτική εντολή

while ... do ελέγχει πρώτα την συνθήκη και έπειτα εκτελεί τις εντολές εντός του βρόχου, ενώ η επαναληπτική εντολή
repeat…until ελέγχει την ορθότητα της συνθήκης μετά το πέρας μιας τουλάχιστον επανάληψης. Ακόμη μια διαφορά είναι το γεγονός ότι, για την
while ... do επαναληπτική εντολή απαιτείται να ισχύει η συνθήκη προκειμένου να εκτελεστούν οι εντολές του βρόχου ενώ για τη επαναληπτική εντολή
repeat…until ισχύει ότι επαναλαμβάνεται μέχρι να γίνει αληθής η συνθήκη.(όσο είναι ψευδής)

(A.18) Τι είναι τα δεδομένα και ποιά η έννοια της πληροφορίας; Ποιά είναι η διαφορά μεταξύ πληροφορίας και δεδομένων;

Ειδικότερα στην πληροφορική συναντούμε τα δεδομένα στον πληθυντικό αριθμό, σπανιότερα στον ενικό (δεδομένο). Γενικότερα,

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

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

· Γενικά, μπορούμε να ονομάσουμε Δεδομένα (Data) τα στοιχεία που χρησιμοποιούμε για επεξεργασία. Τα αποτελέσματα που παίρνουμε από την επεξεργασία των δεδομένων και μας μεταδίδουν κάποια επιπρόσθετη γνώση, τα χαρακτηρίζουμε ως Πληροφορία (Information).

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

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

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

· η πληροφορία ή οι πληροφορίες που παίρνουμε εξαρτώνται και από το είδος της επεξεργασίας που εφαρμόζουμε στα δεδομένα τα οποία διαθέτουμε.

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

(A.47) Ποιά είναι τα χαρακτηριστικά που είναι απαραίτητα προκειμένου να θεωρήσουμε έναν αλγόριθμο πλήρη;

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

2) Έξοδος. Ο αλγόριθμος πρέπει να δημιουργεί τουλάχιστον μία τιμή δεδομένων ως αποτέλεσμα προς το χρήστη ή προς έναν αλλο αλγόριθμο.

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

4) Περατότητα. Ο αλγόριθμος πρέπει να τελειώνει μετά από πεπερασμένα βήματα εκτέλεσης των εντολών του. Μία διαδικασία που δεν τελειώνει μετά από ένα συγκεκριμένο αριθμό βημάτων δεν αποτελεί αλγόριθμο, αλλά λέγεται απλά υπολογιστική διαδικασία (computational procedure).

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

(A.45) Ποιά είναι τα χαρακτηριστικά ενός αλγορίθμου;

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

2) Έξοδος. Ο αλγόριθμος πρέπει να δημιουργεί τουλάχιστον μία τιμή δεδομένων ως αποτέλεσμα προς το χρήστη ή προς έναν αλλο αλγόριθμο.

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

4) Περατότητα. Ο αλγόριθμος πρέπει να τελειώνει μετά από πεπερασμένα βήματα εκτέλεσης των εντολών του. Μία διαδικασία που δεν τελειώνει μετά από ένα συγκεκριμένο αριθμό βημάτων δεν αποτελεί αλγόριθμο, αλλά λέγεται απλά υπολογιστική διαδικασία (computational procedure).

(A.44) Να αναφέρετε τις πιο συνηθισμένες τεχνικές σχεδίασης αλγορίθμων.

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

· Στη διαίρει και βασίλευε το αρχικό σύνθετο πρόβλημα διασπάται σε μικρότερα επιμέρους προβλήματα της ίδιας φύσης με το αρχικό αλλά μικρότερα σε μέγεθος. Ένα παράδειγμα τέτοιας μεθόδου είναι η δυαδική αναζήτηση στην οποία η αναζήτηση ενός στοιχείου σε έναν πίνακα ανάγεται στην αναζήτηση του στοιχείου στο πάνω ή κάτω μισό του πίνακα. Αυτή η προσέγγιση εντάσσεται στη top-down μεθοδολογία, από πάνω προς τα κάτω δηλαδή από το σύνθετο στο απλό.

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

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

(A.39) Τι είναι Αλγόριθμος και τι πρόγραμμα;

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

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

(A.50) Στη δομή δεδομένων τι είναι η στοίβα; Δώστε ένα παράδειγμα.

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

· Είναι μία δομή LIFO (Last In First Out).

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

(A.49) Να αναφέρετε πόσα είναι τα είδη της δομής επανάληψης

1) Επαναληπτικό σχήμα με έλεγχο επανάληψης στην αρχή (όσο..επανάλαβε)

2) Επαναληπτικό σχήμα με έλεγχο επανάληψης στο τέλος (αρχή_επανάληψης..μέχρις ότου)

3) Επαναληπτικό σχήμα ορισμένων φορών επανάληψης ( για i από ...μέχρι)

(A.48) Να αναφέρετε πόσα είναι τα είδη της δομής επιλογής

Υπάρχουν 3 είδη δομών επιλογής.

· Η Απλή επιλογή, (Αν συνθήκη τότε)

· Η σύνθετη επιλογή (Αν συνθήκη τότε..αλλιώς)

· και η Πολλαπλή επιλογή (Αν συνθήκη τότε...αλλιώς_αν...αλλιώς_αν...αλλιώς)

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

(A.43) Τι εννοούμε με τον όρο "πρόβλημα" και σε τι αναφερόμαστε με τον όρο "Ανάλυση Προβλήματος";

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

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

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

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

(A.42) Ποιές είναι οι βασικές λειτουργίες (ή πράξεις) επί των δομών δεδομένων;

1) Προσπέλαση: Πρόσβαση σε ένα κόμβο με σκοπό να εξετασθεί ή να τροποποιηθεί το περιεχόμενό του.

2) Εισαγωγή: Προσθήκη νέων κόμβων.

3) Διαγραφή: Διαγραφή ενός κόμβου

4) Αναζήτηση: Αναζήτηση στους κόμβους μιας δομής, για να εντοπιστούν ένας ή περισσότεροι που έχουν μια δεδομένη ιδιότητα.

5) Ταξινόμηση: Ταξινόμηση των κόμβων κατά αύξουσα ή φθίνουσα σειρά.

6) Αντιγραφή: Αντιγραφή όλων ή μερικών κόμβων σε μία άλλη δομή.

7) Συγχώνευση: Δύο ή περισσότερες δομές ενώνονται σε μία ενιαία δομή.

8) Διαχωρισμός: Μια δομή χωρίζεται σε δύο ή περισσότερες δομές

(A.41) Σε ποιές κατηγορίες διακρίνονται τα προβλήματα με κριτήριο το είδος επίλυσης τους;

1) Προβλήματα Απόφασης: Η λύση σε αυτά τα προβλήματα είναι του τύπου «Ναι» και «Όχι».

2) Υπολογιστικά Προβλήματα: Για την επίλυση απαιτείται η διενέργεια υπολογισμών.

3) Προβλήματα Βελτιστοποίησης: Η λύση που ζητάμε είναι το βέλτιστο αποτέλεσμα για τα συγκεκριμένα δεδομένα.

(A.40)Τι ονομάζουμε δομή δεδομένων;

Δομή Δεδομένων είναι ένα σύνολο δεδομένων που είναι αποθηκευμένα σε έναν Η/Υ και μπορούν να επεξεργαστούν μαζικά από ένα σύνολο λειτουργιών.

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

Σε μια Δομή Δεδομένων

1 Υπάρχουν καθορισμένες σχέσεις μεταξύ των στοιχείων.

2 Εισάγουμε και εξάγουμε στοιχεία με τρόπο ώστε όλη η δομή να μην αλλοιώνεται.

Γενικά λέγοντας «Δομή Δεδομένων» αναφερόμαστε στους διαφορετικούς τρόπους οργάνωσης και αποθήκευσης δεδομένων μέσα σε έναν υπολογιστή, ώστε τα δεδομένα αυτά να μπορούν να χρησιμοποιηθούν αποδοτικά.

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

(A.28) Τι είναι οι στατικές και τι οι δυναμικές δομές δεδομένων; Ποιές οι διαφορές τους;

Οι δομές δεδομένων διακρίνονται σε δύο μεγάλες κατηγορίες: τις στατικές (static) και τις δυναμικές(dynamic).

Οι δυναμικές δομές

· δεν αποθηκεύονται σε συνεχόμενες θέσεις μνήμης αλλά στηρίζονται στην τεχνική της λεγόμενης δυναμικής παραχώρησης μνήμης (dynamic memory allocation).

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

Οι στατικές δομές

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

· αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.

(A.27) Τι εννοούμε με τους όρους LIFO (Last In First Out) και FIFO (First In First Out) και σε ποιές δομές δεδομένων βρίσκουν εφαρμογή;

Με τους όρους LIFO (Last In First Out) και FIFO (First In First Out) αναφερόμαστε στη διαχείριση των δεδομένων αναφορικά με τον τρόπο με τον οποίο αυτά αποθηκεύονται (εισάγονται) μέσα σε μια δομή δεδομένων και εν συνεχεία διαχειρίζονται (εξάγονται) από αυτήν.

Πιο συγκεκριμένα, για τις δομές δεδομένων Στοίβα και Ουρά, όπου και οι ανωτέρω τεχνικές εισαγωγής και επεξεργασίας δεδομένων βρίσκουν εφαρμογή, ισχύουν τα παρακάτω.

- Στη στοίβα τα δεδομένα που βρίσκονται στην κορυφή τα επεξεργαζόμαστε πρώτα και τα δεδομένα που βρίσκονται στο τέλος τα επεξεργαζόμαστε τελευταία. Η μέθοδος αυτή ονομάζεται LIFO(Last-In-First-Out).

Στη στοίβα χρειαζόμαστε ένα δείκτη(top)που δείχνει το στοιχείο που βρίσκεται στην κορυφή της στοίβας.

(Στη στοίβα κάνουμε ώθηση και απώθηση στοιχείων)

- Σε μια ουρά εξυπηρετούνται εκείνα τα δεδομένα που τοποθετήθηκαν στην ουρά πρώτα από όλα τα υπόλοιπα. Η μέθοδος αυτή ονομάζεται FIFO (First-In-First-Out).

(Στην ουρά κάνουμε εισαγωγή και εξαγωγή στοιχείων)

Σε αυτή τη δομή δεδομένων επιτρέπεται όλες οι εισαγωγές στοιχείων να γίνονται από το ένα άκρο, και όλες οι διαγραφές, από το άλλο. Κατά συνέπεια χρειαζόμαστε δύο δείκτες τον μπρος (head) και τον πίσω(tail).

Αναζήτηση αυτού του ιστολογίου

Τεχνικός Εφαρμογών Πληροφορικής