Τμήμα Μαθηματικών

Πληροφορική Ι

Εβδομάδα 1

(Οδηγίες χρήσης του διαδραστικού κώδικα: δείτε την αρχική σελίδα.)

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

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

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

Ένα πρόγραμμα είναι η ακριβής διατύπωση ενός αλγορίθμου σε μια γλώσσα προγραμματισμού. Ένας αλγόριθμος μπορεί να περιγραφεί με φυσική γλώσσα, με διάγραμμα ροής (flowchart), με ψευδοκώδικα, ή απευθείας με κώδικα.

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

1. Ανάλυση των δεδομένων του προβλήματος.
2. Μαθηματική διατύπωση του προβλήματος.
3. Σχεδιασμός ή επιλογή κατάλληλου αλγορίθμου (συνήθως ένα πρόβλημα λύνεται με πολλούς διαφορετικούς αλγορίθμους).
4. Διατύπωση του αλγορίθμου σε γλώσσα προγραμματισμού, δηλαδή συγγραφή του προγράμματος.
5. Εκτέλεση του προγράμματος για συγκεκριμένα δεδομένα.
6. Ερμηνεία των αποτελεσμάτων.

Σχεδόν κάθε αλγόριθμος χτίζεται από λίγες βασικές αλγοριθμικές ενέργειες:

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

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

1.1 Παράδειγμα: Γραμμική Αναζήτηση (Linear Search)

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

Πρόβλημα: Δίνεται μια λίστα αριθμών v και μια τιμή-στόχος. Να βρεθεί η θέση της τιμής-στόχου μέσα στη λίστα (ή να διαπιστωθεί ότι δεν υπάρχει).

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

Σε φυσική γλώσσα

1. Ξεκίνα από την πρώτη θέση της λίστας (θέση 0).
2. Για κάθε θέση, με τη σειρά, μέχρι το τέλος της λίστας:
   1. Αν το στοιχείο σε αυτή τη θέση είναι ο στόχος, βρέθηκε — τερμάτισε επιστρέφοντας τη θέση.
3. Αν έφτασες στο τέλος χωρίς να βρεις τον στόχο, τότε δεν υπάρχει στη λίστα.

Ως διάγραμμα ροής

flowchart TD
    A(["Αρχή"]) --> B["θέση = 0"]
    B --> C{"θέση < μήκος(v) ;"}
    C -- "Όχι" --> H["Δεν βρέθηκε
(επίστρεψε -1)"]
    C -- "Ναι" --> D{"v[θέση] == στόχος ;"}
    D -- "Ναι" --> F["Βρέθηκε
(επίστρεψε θέση)"]
    D -- "Όχι" --> E["θέση = θέση + 1"]
    E --> C
    F --> K(["Τέλος"])
    H --> K

Ως ψευδοκώδικας

ΓΡΑΜΜΙΚΗ_ΑΝΑΖΗΤΗΣΗ(v, στόχος):
    για θέση από 0 έως μήκος(v) - 1:
        αν v[θέση] = στόχος:
            επίστρεψε θέση          // βρέθηκε
    επίστρεψε -1                    // δεν βρέθηκε

Ως κώδικας Python

Ο βρόχος for, η εντολή if, οι λίστες και οι συναρτήσεις (def) έρχονται στις Εβδομάδες 3–6 — δείτε τον παρακάτω κώδικα απλώς ως πρόγευση του πού πηγαίνουμε. Οι τρεις προηγούμενες μορφές (φυσική γλώσσα, διάγραμμα, ψευδοκώδικας) δεν χρειάζονται καθόλου Python:

Δοκιμάστε ένα target που δεν υπάρχει (π.χ. 99), και παρατηρήστε ότι επιστρέφεται -1. Οι τέσσερις μορφές παραπάνω περιγράφουν ακριβώς τον ίδιο αλγόριθμο — από τη γενική ιδέα σε φυσική γλώσσα, μέχρι τον εκτελέσιμο κώδικα.

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

2 Η Python

Η Python είναι μια γλώσσα προγραμματισμού υψηλού επιπέδου, η οποία:

• χρησιμοποιεί διερμηνέα (είναι scripting language), και μπορεί να εκτελεστεί είτε ανά εντολή σε διαδραστικό κέλυφος (shell), είτε ως πλήρες αρχείο .py,
• είναι δυναμική ως προς τον ορισμό τύπου μεταβλητών (δεν χρειάζεται να δηλώσουμε τον τύπο μιας μεταβλητής),
• έχει απλή σύνταξη, με υποχρεωτική στοίχιση (indentation) που οριοθετεί τα μπλοκ κώδικα,
• διαθέτει μεγάλη πρότυπη βιβλιοθήκη (standard library) έτοιμων συναρτήσεων.

Αναπτύχθηκε από τον Ολλανδό Guido van Rossum στις αρχές της δεκαετίας του ’90 (πρώτη έκδοση Python 0.9.0, Φεβρουάριος 1991). Ακολούθησαν η Python 2.0 (2000) και η Python 3.0 (2008, μη συμβατή προς τα πίσω με την 2.x), η οποία και χρησιμοποιούμε σήμερα.

Ένα πρόγραμμα Python εκτελείται με δύο τρόπους:

• διαδραστικά: πληκτρολογούμε εντολές μία-μία στο κέλυφος (shell) της Python, που τις διερμηνεύει και τις εκτελεί αμέσως·
• σε λειτουργία script: γράφουμε ολόκληρο το πρόγραμμα σε ένα αρχείο .py και το εκτελούμε συνολικά.

Στις σημειώσεις αυτές, κάθε φορά που πατάτε “Run Code” ολόκληρο το πλαίσιο εκτελείται σαν script.

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

2.1 Μεταβλητές και τύποι

Μια μεταβλητή είναι ένα όνομα που αναφέρεται σε ένα αντικείμενο αποθηκευμένο στη μνήμη· το αντικείμενο έχει μια τιμή και έναν τύπο (type). Δημιουργούμε μια μεταβλητή με μία εντολή εκχώρησης (assignment): μεταβλητή = τιμή.

Στην Python δεν δηλώνουμε τον τύπο: προσδιορίζεται αυτόματα από την τιμή, και μπορεί να αλλάξει αν εκχωρήσουμε αργότερα τιμή διαφορετικού τύπου.

Κανόνες ονοματολογίας. Ένα όνομα μεταβλητής:

• ξεκινά με γράμμα ή κάτω παύλα (_)·
• περιέχει μόνο γράμματα, αριθμούς και κάτω παύλες — όχι κενά ή τελείες·
• δεν μπορεί να είναι δεσμευμένη λέξη-κλειδί (for, if, while, …).

Η Python κάνει διάκριση πεζών/κεφαλαίων: το age και το Age είναι διαφορετικές μεταβλητές.

Επανεκχώρηση τιμών

Η τιμή (και ο τύπος) μιας μεταβλητής μπορούν να αλλάξουν οποτεδήποτε με μια νέα εκχώρηση:

Ταυτόχρονη εκχώρηση πολλών μεταβλητών

Η Python επιτρέπει την εκχώρηση πολλών τιμών σε πολλές μεταβλητές με μία μόνο εντολή:

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

Μεταβλητές ως αναφορές (references)

Είναι σημαντικό να καταλάβουμε τι πραγματικά κάνει η εκχώρηση: μια μεταβλητή στην Python δεν είναι ένα “κουτί” που περιέχει την τιμή, αλλά ένα όνομα (ετικέτα) που δείχνει σε ένα αντικείμενο, κάπου στη μνήμη.

Μετά τις εντολές a = 1000 και b = a, δύο ονόματα δείχνουν στο ίδιο αντικείμενο:

flowchart LR
    a(["a"]) --> obj["1000"]
    b(["b"]) --> obj

Η συνάρτηση id(x) επιστρέφει έναν μοναδικό αριθμό-ταυτότητα για το αντικείμενο στο οποίο δείχνει η x, και ο τελεστής is ελέγχει αν δύο μεταβλητές δείχνουν στο ίδιο ακριβώς αντικείμενο (σε αντίθεση με το ==, που ελέγχει αν οι τιμές είναι ίσες):

Η b = b + 1 δεν “πειράζει” το 1000: υπολογίζει το 1001 ως νέο αντικείμενο και στρέφει εκεί μόνο το όνομα b. Το a συνεχίζει να δείχνει στο αρχικό:

flowchart LR
    a(["a"]) --> obj1["1000"]
    b(["b"]) --> obj2["1001 (νέο)"]

Επειδή οι αριθμοί (και οι συμβολοσειρές) είναι αμετάβλητοι (immutable) τύποι, κάθε “τροποποίησή” τους στην πραγματικότητα φτιάχνει ένα νέο αντικείμενο, οπότε αυτή η λεπτομέρεια συνήθως περνάει απαρατήρητη. Θα δούμε στην Εβδομάδα 4 ότι για μεταβλητούς (mutable) τύπους, όπως οι λίστες, αυτή η διάκριση ανάμεσα σε “όνομα” και “αντικείμενο” έχει πολύ πιο ορατές συνέπειες.

Συνηθισμένα λάθη

Ένα όνομα μεταβλητής που δεν ακολουθεί τους κανόνες ονοματολογίας προκαλεί συντακτικό σφάλμα (SyntaxError), το οποίο εντοπίζεται πριν καν εκτελεστεί οτιδήποτε από το πρόγραμμα. Δοκιμάστε:

Άλλα παραδείγματα μη έγκυρων ονομάτων (μην τα τρέξετε — δείτε γιατί είναι λάθος):

my.var = 5      # λάθος: περιέχει τελεία
else = 10       # λάθος: το 'else' είναι δεσμευμένη λέξη-κλειδί
αριθμός φοιτητών = 3   # λάθος: περιέχει κενό

2.2 Είσοδος με την input

Σε ένα κανονικό πρόγραμμα Python, η συνάρτηση input('μήνυμα') διαβάζει δεδομένα από το πληκτρολόγιο και πάντα επιστρέφει συμβολοσειρά — ακόμα κι αν ο χρήστης πληκτρολογήσει έναν αριθμό. Για να χρησιμοποιηθεί αριθμητικά, πρέπει να μετατραπεί με τις συναρτήσεις int() ή float():

flowchart LR
    kb["ο χρήστης πληκτρολογεί<br>25"] -->|"input()"| s["'25'<br>str — πάντα!"]
    s -->|"int()"| n["25<br>int"]

age = input('Δώσε την ηλικία σου: ')   # η age είναι πάντα str
age = int(age)                          # μετατροπή σε int

ή, πιο σύντομα, με άμεση σύνθεση των δύο κλήσεων:

age = int(input('Δώσε την ηλικία σου: '))

Σημείωση

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

Παράδειγμα 1: είσοδος συμβολοσειράς

Όταν δεν χρειαζόμαστε αριθμητική τιμή, δεν χρειάζεται καμία μετατροπή — η input επιστρέφει ήδη str:

Παράδειγμα 2: μετατροπή σε ακέραιο (int)

Παράδειγμα 3: μετατροπή σε πραγματικό (float)

Παράδειγμα 4: ο συντομότερος τρόπος

Συνήθως συνδυάζουμε την input με την int/float σε μία εντολή:

Παράδειγμα 5: πολλαπλές είσοδοι σε ένα μικρό πρόγραμμα

Οι τρεις βασικές συναρτήσεις μετατροπής τύπου είναι οι int(), float() και str(). Η μετατροπή float σε int κόβει (δεν στρογγυλοποιεί) το δεκαδικό μέρος:

flowchart LR
    str["str<br>'42' · '3.14'"]
    int["int<br>42"]
    float["float<br>3.14"]
    str -->|"int()"| int
    str -->|"float()"| float
    int -->|"str()"| str
    float -->|"str()"| str
    int -->|"float()"| float
    float -->|"int() κόβει το δεκαδικό"| int

Συνηθισμένα λάθη

Οι int() και float() δουλεύουν μόνο αν η συμβολοσειρά αναπαριστά έγκυρη τιμή του αντίστοιχου τύπου. Ο παρακάτω κώδικας δίνει ValueError — ακριβώς το σφάλμα που θα έπαιρνε ένα κανονικό πρόγραμμα αν ο χρήστης πληκτρολογούσε δεκαδικό εκεί που περιμένουμε ακέραιο:

Η ίδια τιμή όμως μετατρέπεται κανονικά με float(), αφού είναι έγκυρος δεκαδικός αριθμός:

2.3 Έξοδος με την print

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

Τα ορίσματα μπορούν να έχουν διαφορετικούς τύπους — η print τα μετατρέπει αυτόματα σε κείμενο:

Οι τελεστές sep και end

Ο τελεστής sep καθορίζει τι μπαίνει ανάμεσα στα ορίσματα (αντί για το προεπιλεγμένο κενό), και ο τελεστής end καθορίζει τι μπαίνει στο τέλος της εκτύπωσης (αντί για την προεπιλεγμένη αλλαγή γραμμής):

Οι δύο τελεστές συνδυάζονται ελεύθερα:

Ακολουθίες διαφυγής

Μέσα σε συμβολοσειρές μπορούν να χρησιμοποιηθούν ακολουθίες διαφυγής (escape sequences): \n (αλλαγή γραμμής), \t (tab), \'/\" (εμφάνιση εισαγωγικού), και \\ (εμφάνιση ανάστροφης καθέτου):

Οι τελεστές + και *

Ο τελεστής + μεταξύ συμβολοσειρών κάνει συνένωση (concatenation) χωρίς να προσθέτει κενό, ενώ ο τελεστής * μεταξύ συμβολοσειράς και ακεραίου επαναλαμβάνει τη συμβολοσειρά:

Σημαντικό

Ο τελεστής + λειτουργεί μόνο ανάμεσα σε ίδιους τύπους (π.χ. δύο συμβολοσειρές, ή δύο αριθμούς) — δεν κάνει αυτόματη μετατροπή. Δοκιμάστε το παρακάτω και δείτε το πραγματικό σφάλμα (TypeError):

Δύο σωστοί τρόποι να διορθωθεί:

Μορφοποίηση με format

Η συνάρτηση format(τιμή, μορφή) μορφοποιεί αριθμούς κατά την εκτύπωση:

f-strings

Τα f-strings (από την Python 3.6) είναι ο σύγχρονος, πιο ευανάγνωστος τρόπος: ενσωματώνουμε τιμές μεταβλητών απευθείας μέσα στη συμβολοσειρά, μέσα σε άγκιστρα { }, με προαιρετική μορφοποίηση μετά από άνω-κάτω τελεία — τους ίδιους ακριβώς κωδικούς μορφοποίησης με τη format. Θα τα δούμε αναλυτικά στην Εβδομάδα 2 και θα τα χρησιμοποιούμε παντού από εκεί και μετά.

2.4 Γραφική έξοδος: το matplotlib

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

Τη φορτώνουμε με την εντολή import (θα τη δούμε αναλυτικά στην Εβδομάδα 2) και της δίνουμε, κατά σύμβαση, το σύντομο όνομα plt:

Τα βασικά:

• plt.plot(xs, ys) — γράφημα γραμμής· τα xs, ys είναι λίστες αριθμών ίδιου μήκους (τις λίστες τις μελετάμε στην Εβδομάδα 4)·
• plt.scatter(xs, ys) — διάγραμμα διασποράς (μεμονωμένα σημεία)·
• plt.bar(xs, ys) — ραβδόγραμμα·
• plt.xlabel, plt.ylabel, plt.title, plt.legend — επεξηγήσεις·
• plt.show() — εμφανίζει το γράφημα.

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

3 Σύνοψη

Σε αυτή την εβδομάδα είδαμε:

• Την έννοια του αλγορίθμου, και τις τέσσερις μορφές περιγραφής του (φυσική γλώσσα, διάγραμμα ροής, ψευδοκώδικας, κώδικας) — με τη γραμμική αναζήτηση ως παράδειγμα αλγορίθμου.
• Μεταβλητές και βασικούς τύπους δεδομένων (int, float, str), και ότι η Python είναι δυναμικά τυποποιημένη.
• Ότι μια μεταβλητή είναι στην πραγματικότητα μια αναφορά σε ένα αντικείμενο (id, is), όχι ένα “κουτί” με τιμή.
• Είσοδο/έξοδο με input/print, και μετατροπές τύπου (int(), float(), str()).
• Μορφοποίηση εξόδου: τους τελεστές sep/end, τη συνάρτηση format, και τα f-strings.
• Γραφική έξοδο με το matplotlib (plt.plot, plt.scatter, plt.bar, plt.show) — ένα εργαλείο που θα χρησιμοποιούμε σε όλο το μάθημα.

---

⤺ Πίσω στην αρχική σελίδα / πρόγραμμα μαθήματος  ·  Διαφάνειες αυτής της εβδομάδας