Μάθημα : Α' ΓΥΜΝΑΣΙΟΥ - ΠΛΗΡΟΦΟΡΙΚΗ

Τι είναι αλγόριθμος;

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

ΔΡΑΣΤΗΡΙΟΤΗΤΕΣ

ΤΑ ΧΑΡΑΚΤΗΡΙΣΤΙΚΑ ΤΟΥ ΑΛΓΟΡΙΘΜΟΥ

1. Σαφή βήματα (Σαφήνεια): Κάθε βήμα του αλγορίθμου πρέπει να είναι ξεκάθαρο και εύκολο να ακολουθηθεί. Δεν πρέπει να υπάρχει σύγχυση για το τι πρέπει να γίνει. (πχ ΝΑΙ στρίψε δεξιά  ΟΧΙ στρίψε)

2. Ακριβή βήματα (Ακρίβεια):  Κάθε βήμα πρέπει να είναι εκφρασμένο με ακρίβεια (πχ ΝΑΙ στρίψε δεξιά 90 μοίρες, ΟΧΙ στρίψε δεξιά)
3. Εύκολος και γρήγορος: Τα βήματα του αλγορίθμου πρέπει να είναι απλά και να μπορούν να γίνουν γρήγορα, χωρίς να χρειάζονται πολύπλοκες πράξεις.

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

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

6. Παράγει αποτέλεσμα (Αποτελεσματικότητα): Ο αλγόριθμος πρέπει να σου δίνει κάποιο αποτέλεσμα στο τέλος. Για παράδειγμα, αν είναι μια συνταγή, το φαγητό είναι το αποτέλεσμα.

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

Η λέξη «αλγόριθμος» προέρχεται από τον Πέρση μαθηματικό Abu Ja’far Mohammed ibn Musa al Khowarizmi, που έζησε τον 9ο αιώνα μ.Χ. Το όνομά του λατινοποιήθηκε ως Algorizmi, δίνοντας τη βάση για τον όρο. Έγραψε μια πραγματεία για το ινδουιστικό-αραβικό αριθμητικό σύστημα, η οποία μεταφράστηκε στα λατινικά τον 12ο αιώνα, συμβάλλοντας στη διάδοση των μαθηματικών γνώσεων.

ΑΛΓΟΡΙΘΜΟΙ ΚΡΥΠΤΟΓΡΑΦΗΣΗΣ

Ο Ιούλιος Καίσαρας, κατά τους γαλατικούς πολέμους, χρησιμοποιούσε έναν απλό τρόπο για να κρυπτογραφεί τα μηνύματά του, ώστε αν έπεφταν στα χέρια του εχθρού, να μην μπορούσαν να τα διαβάσουν. Η μέθοδος του λεγόταν "Κώδικας του Καίσαρα" και ήταν πολύ απλή: αντικαθιστούσε κάθε γράμμα του μηνύματος με ένα άλλο γράμμα που βρισκόταν 3 θέσεις πιο μπροστά στο λατινικό αλφάβητο. Για παράδειγμα, το γράμμα A γινόταν D, το B γινόταν E, κ.ο.κ.

Στην κρυπτογραφία, υπάρχουν δύο βασικοί όροι:

1. Κανονικό αλφάβητο: Είναι τα γράμματα του αρχικού μηνύματος.

2. Κρυπτογραφικό αλφάβητο: Είναι τα γράμματα του κρυπτογραφημένου μηνύματος.

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

Παράδειγμα 1

Παράδειγμα 2

Αρχικό μήνυμα: ΓΑΤΑ
(χρησιμοποιούμε το ελληνικό αλφάβητο)

Αν μετατοπίσουμε κάθε γράμμα κατά 3 θέσεις μπροστά, έχουμε:

• Γ → Δ → Ε → Ζ
• Α → Β → Γ → Δ
• Τ → Υ → Φ → Χ
• Α → Β → Γ → Δ

👉 Κρυπτογραφημένο μήνυμα: ΖΔΧΔ

Αν κάποιος λάβει το μήνυμα ΖΔΧΔ χωρίς να ξέρει το μυστικό κλειδί (3 θέσεις), δεν θα μπορεί εύκολα να το αποκρυπτογραφήσει!

📜 Δραστηριότητα 5:

Σπάστε τον κώδικα του Καίσαρα!

Βήμα 1: Κρυπτογράφηση

1. Χωριστείτε σε ομάδες των 3-4 ατόμων.
2. Επιλέξτε ένα μυστικό κλειδί (π.χ., μετατόπιση 3 θέσεων).
3. Κρυπτογραφήστε μια φράση, μετατοπίζοντας κάθε γράμμα στο αλφάβητο.
4. Γράψτε το κρυπτογραφημένο μήνυμα στον πίνακα.
5. Προσπαθήστε να αποκρυπτογραφήσετε τα μηνύματα των άλλων ομάδων!

Βήμα 2: Κρυπτανάλυση

1. Προσπαθήστε να αποκρυπτογραφήσετε τα μηνύματα των άλλων ομάδων:

   • Κοιτάξτε το κρυπτογραφημένο μήνυμα τους και δοκιμάστε να το αποκρυπτογραφήσετε χρησιμοποιώντας διαφορετικά κλειδιά (1, 2, 3, ..., 26).

   • Όταν βρείτε το σωστό κλειδί, το μήνυμα θα βγάζει νόημα!

2. Καταγράψτε τη στρατηγική σας:

   • Πώς αποφασίσατε ποιο κλειδί να δοκιμάσετε πρώτο;

   • Ποια λέξη ή γράμμα σας βοήθησε να μαντέψετε το κλειδί;

🎯 Στόχος: Η ομάδα που θα αποκρυπτογραφήσει τα περισσότερα μηνύματα κερδίζει! 🚀

Καλή επιτυχία! 🕵️‍♂️🔑

ΑΛΓΟΡΙΘΜΟΙ ΣΥΜΠΙΕΣΗΣ

• Σκοπός Συμπίεσης Δεδομένων:

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

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

• Ορισμός Συμπίεσης:

  • Η συμπίεση δεδομένων (data compression) είναι η μετατροπή ενός ψηφιακού αρχείου σε μικρότερο μέγεθος, με τρόπο που να επιτρέπει την αναδόμηση του αρχικού αρχείου.

• Εφαρμογές Συμπίεσης:

  • Χρησιμοποιείται συστηματικά σε υπολογιστικά συστήματα για τη διαχείριση μεγάλων όγκων δεδομένων.

  • Παραδείγματα συμπιεσμένων αρχείων: μουσικά αρχεία (mp3), βίντεο (mp4), εικόνες (jpeg).

• Συνοπτικά:

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

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

• Αλγόριθμος RLE (Run Length Encoding):

  • Είναι ένας από τους απλούστερους αλγόριθμους συμπίεσης.

  • Λειτουργία:

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

    • Αντικαθιστά τις επαναλήψεις με το πλήθος τους και το σύμβολο (π.χ., "AAAA" → "4A").

• Σύμβολα/Χαρακτήρες:

  • Σύμβολο μπορεί να είναι αριθμός, γράμμα ή σημείο στίξης.

  • Συχνά αναφέρεται ως "χαρακτήρας".

• Αποτελεσματικότητα του RLE:

  • Λειτουργεί καλά όταν υπάρχουν συχνές επαναλήψεις χαρακτήρων.

  •  

• • • Παράδειγμα: Μια ακολουθία 63 χαρακτήρων μπορεί να συμπιεστεί σε μόλις 9 χαρακτήρες.

• • Αν δεν υπάρχουν επαναλήψεις, ο αλγόριθμος μπορεί να αυξήσει το μέγεθος του αρχείου αντί να το μειώσει.

Δραστηριότητα:

"Συμπίεσε κείμενο με τον RLE!"

Έστω ότι έχουμε το κείμενο:

ΑΑΑΒΒΓΓΓΓΔΔΕΕΕΕΕΖΖΗΗΗΘΘΘΘΘΙΙΚΚΚΚΛΛΛΜΜΜΜΜΝΝΞΞΞΟΟΠΠΡΡΣΣΣΣΤΤΥΥΦΦΦΧΧΨΨΩΩΩ

Εφαρμόστε τον αλγόριθμο RLE για να συμπιέσετε το κείμενο. Ποιό είναι το νέο σας κείμενο;

Έστω τώρα ότι έχετε το κείμενο:

Η ζωή είναι ωραία, η ζωή είναι όμορφη

Εφαρμόστε τον αλγόριθμο RLE για να συμπιέσετε το κείμενο. Ποιό είναι το νέο σας κείμενο;

Μπορείτε να κάνετε κάποιες παρατηρήσεις για την αποτελεσματικότητα του αλγόριθμου;