Ανάλυση προβλημάτων

Η ενότητα 4.1 στο πρώτο βιβλίο έχει μόνο θεωρία με περιορισμένο ενδιαφέρον. 

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

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

Τι περιλμβάνει η ανάλυση ενός προβλήματος

Η ανάλυση ενός προβλήματος περιλαμβάνει 5 στάδια. Παράδειγμα: Υπολογισμός φόρου εισοδήματος.

Στάδιο

Περιγραφή & Παράδειγμα

1. Καταγραφή της υπάρχουσας πληροφορίας

Συλλογή δεδομένων & κανόνων.
Παράδειγμα: Ο φόρος εισοδήματος υπολογίζεται με κλίμακες (0–10.000€ → 10%, 10.001–20.000€ → 20%, κ.λπ.).

2. Αναγνώριση των ιδιαιτεροτήτων του προβλήματος

Λεπτομέρειες που δυσκολεύουν τη λύση.
Παράδειγμα: Το εισόδημα πρέπει να είναι θετικός αριθμός, ο φόρος υπολογίζεται τμηματικά.

3. Αποτύπωση των συνθηκών και προϋποθέσεων υλοποίησης

Προϋποθέσεις για σωστή λειτουργία.
Παράδειγμα: Ο χρήστης πρέπει να εισάγει σωστά το εισόδημα, οι συντελεστές να είναι ενημερωμένοι.

4. Πρόταση επίλυσης με χρήση κάποιας μεθόδου

Σχεδιασμός στρατηγικής – περιγραφή αλγορίθμου.
Παράδειγμα:
1. Διάβασε εισόδημα
2. Βρες σε ποια κλίμακα ανήκει
3. Υπολόγισε τον φόρο
4. Εμφάνισε αποτέλεσμα

5. Τελική επίλυση με χρήση υπολογιστικών συστημάτων

Μετατροπή αλγορίθμου σε πρόγραμμα.
Παράδειγμα (ΓΛΩΣΣΑ):
Αλγόριθμος Foros
Διάβασε eisodima
Αν eisodima <= 10000 τότε
    foros <- eisodima * 0.10
Αλλιώς_αν eisodima <= 20000 τότε
    foros <- 10000*0.10 + (eisodima-10000)*0.20
Αλλιώς
    foros <- 10000*0.10 + 10000*0.20 + (eisodima-20000)*0.30
Τέλος_αν
Εμφάνισε foros
Τέλος Foros

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

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

Οι μέθοδοι ανάλυσης και επίλυσης των προβλημάτων παρουσιάζουν ιδιαίτερο ενδιαφέρον διότι:

  • παρέχουν ένα γενικό πρότυπο κατάλληλο για την επίλυση προβλημάτων ευρείας κλίμακας,

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

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

Ωραία, ας τα δούμε πιο αναλυτικά και «μεταφρασμένα» σε πιο απλή γλώσσα, με παραδείγματα.

«Παρέχουν ένα γενικό πρότυπο κατάλληλο για την επίλυση προβλημάτων ευρείας κλίμακας»

📌 Τι σημαίνει:

  • Οι μέθοδοι ανάλυσης/επίλυσης (δηλαδή τα «μοτίβα αλγορίθμων») δεν είναι μόνο για ένα συγκεκριμένο πρόβλημα.

  • Δίνουν μια γενική συνταγή που μπορεί να χρησιμοποιηθεί σε πολλά και διαφορετικά προβλήματα.

  • Υπάρχουν «οικογένειες αλγορίθμων» (π.χ. Διαίρει και Βασίλευε, Δυναμικός Προγραμματισμός) που δίνουν λύσεις σε ολόκληρες κατηγορίες προβλημάτων.

🔹 Παράδειγμα:

  • Αν μάθεις τη λογική «Διαίρει και Βασίλευε» (π.χ. στη δυαδική αναζήτηση), μπορείς να καταλάβεις και άλλους αλγορίθμους που ανήκουν στην ίδια οικογένεια (π.χ. Merge Sort, Quick Sort, Μάντεψε τον αριθμό).

  • Οπότε δεν χρειάζεται κάθε φορά να ξεκινάς από το μηδέν, γιατί το «πρότυπο» είναι κοινό.

«Μπορούν να αναπαρασταθούν με κοινές δομές δεδομένων και ελέγχου (που υποστηρίζονται από τις περισσότερες σύγχρονες γλώσσες προγραμματισμού)»

📌 Τι σημαίνει:

  • Όλοι οι αλγόριθμοι τελικά εκφράζονται με τα ίδια εργαλεία που υπάρχουν σε κάθε γλώσσα προγραμματισμού.

  • Αυτά είναι:

    • Δομές δεδομένων: μεταβλητές, πίνακες, λίστες.

    • Δομές ελέγχου: επιλογές (Αν… αλλιώς), επαναλήψεις (Όσο, Για).

🔹 Παράδειγμα:

  • Ο αλγόριθμος της φυσαλίδας (bubble sort) μπορεί να γραφτεί:

    • Σε ΓΛΩΣΣΑ με Για και Αν.

    • Σε Python με for και if.

    • Σε C με for και if.
      👉 Δηλαδή, η «συνταγή» είναι ίδια, μόνο η «γραμματική» αλλάζει.

«Παρέχουν τη δυνατότητα καταγραφής των χρονικών και “χωρικών” απαιτήσεων της μεθόδου επίλυσης, έτσι ώστε να μπορεί να γίνει επακριβής εκτίμηση των αποτελεσμάτων»

📌 Τι σημαίνει:

  • Κάθε αλγόριθμος έχει:

    • Χρονική πολυπλοκότητα → πόσα βήματα χρειάζεται (πόσο «χρόνο» θέλει).

    • Χωρική πολυπλοκότητα → πόση μνήμη καταναλώνει.

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

🔹 Παράδειγμα:

  • Αναζήτηση σε λίστα:

    • Γραμμική αναζήτηση: σε λίστα Ν στοιχείων μπορεί να χρειαστεί μέχρι Ν συγκρίσεις.

    • Δυαδική αναζήτηση: σε ταξινομημένη λίστα χρειάζονται μόνο log₂N συγκρίσεις.
      👉 Για λίστα με 1.000.000 στοιχεία:

  • γραμμική → έως 1.000.000 βήματα

  • δυαδική → μόνο ~20 βήματα

✅ Άρα συνολικά:

  1. Οι μέθοδοι ανάλυσης/επίλυσης δίνουν γενικά πρότυπα που εφαρμόζονται σε πολλές περιπτώσεις.

  2. Μπορούν να εκφραστούν με κοινά εργαλεία που υπάρχουν σε όλες τις γλώσσες.

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