Αρχική ΑΕΠΠ - Δομές Δεδομένων Λειτουργικά Συστήματα Δίκτυα Υπολογιστών ΙΙ Βάσεις Δεδομένων Παιδαγωγικά - Διδακτική

Βασικές Έννοιες

Μεταβλητή - Έκφραση Δομή Ακολουθίας Δομή Επιλογής Δομή Επανάληψης

Αναπαράσταση Αλγορίθμων

Διάγραμμα Ροής

Πίνακας Τιμών

Πίνακες

Μονοδιάστατοι Δισδιάστατοι Πολυδιάστατοι Αναζήτηση Ταξινόμηση Στοίβα Ουρά

Υποπρογράμματα

Συναρτήσεις Διαδικασίες Σχετικά με τις παράμετρους

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

Λίστες Δέντρα Γράφοι

 Ιστορικό Πρόσφατες αλλαγές Εκτύπωση Αναζήτηση

Το μάθημα Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον διδάσκεται στην Γ' Γενικού Λυκείου και αποτελεί εξεταζόμενο πανελλαδικά μάθημα για την Τεχνολογική Κατεύθυνση.

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

Το μάθημα αυτό το συναντάμε στις περισσότερες σχολές πληροφορικής σε ΑΕΙ και ΑΤΕΙ. Το πιο γνωστό βιβλίο, το οποίο θεωρείτε σαν "ευαγγέλιο", είναι το “Αλγόριθμοι και Δομές Δεδομένων” του Niklaus Wirth, δημιουργού των Pascal, Modula-2 και Modula-3.

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

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

Βασικές Έννοιες Αλγορίθμων

Στο δομημένο προγραμματισμό χρησιμοποιούνται τρεις (3) βασικές δομές με τις οποίες γράφουμε κάθε τύπο προγράμματος. Στις βασικές έννοιες αναπτύσσουμε αυτές τις δομές:

Πριν, όμως, από αυτές θα πρέπει να αναπτύξουμε τις έννοιες Μεταβλητή και Έκφραση.

Αναπαράσταση Αλγορίθμων

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

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

Πίνακες

Μονοδιάστατοι

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

Δισδιάστατοι

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

Πολυδιάστατοι

Εκτός ύλης για το μάθημα ΑΕΠΠ

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

Αναζήτηση

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

Συγκεκριμένα θα ασχοληθούμε με τα παρακάτω είδη αναζήτησης:

Ταξινόμηση

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

Οι αλγόριθμοι με τους οποίους θα ασχοληθούμε είναι:

Στοίβα

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

Ουρά

Η ουρά είναι μία δομή στην οποία μπορούμε κάθε φορά να αναφερόμαστε στην αρχή και στο τέλος της. Νέα στοιχεία μπορούν να εισαχθούν στο τέλος και τα στοιχεία που εξάγονται βρίσκονται στην αρχή. Η μέθοδος που υλοποιεί καλείται FIFO (First In First Out).

Υποπρογράμματα

Με τη χρήση των συναρτήσεων και των διαδικασιών γίνεται πράξη ο τμηματικός προγραμματισμός.

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

Εκτός ύλης για το μάθημα ΑΕΠΠ

Λίστες

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

Δέντρα

Τα δέντρα ανήκουν στις μη γραμμικές δομές. Έχουν πολλές εφαρμογές στους υπολογιστές. Για παράδειγμα, η δομή των φακέλων και των αρχείων του λειτουργικού συστήματος είναι δενδρική. Σ' αυτή την ενότητα αναπτύσσουμε τις βασικές λειτουργίες που εκτελούνται σε μία σε δενδρικές δομές.

Γράφοι

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

Τελευταία ενημέρωση: 09-02-2008 (18:43)

Copyright 2008 - Άρης Φεργάδης