κεφάλαιο 4 από βακάλη
- 1. Κεφάλαιο 4 : Τεχνικές Σχεδίασης Αλγορίθμων „ Ανάλυση Προβλημάτων „ Μέθοδοι Σχεδίασης Αλγορίθμων „ Μέθοδος Διαίρει και Βασίλευε
- 2. Κεφάλαιο 4 : Τεχνικές Σχεδίασης Αλγορίθμων Διδακτικοί στόχοι κεφαλαίου „ να τεκμηριωθεί η αναγκαιότητα ανάλυσης του προβλήματος και της σχεδίασης του κατάλληλου αλγορίθμου, „ να μπορεί να σχεδιασθεί ένας αλγόριθμος ως μία ακολουθία βημάτων „ να θεωρηθούν μερικές οικογένειες σχεδιασμού αλγορίθμων
- 3. Κεφάλαιο 4 : Τεχνικές Σχεδίασης Αλγορίθμων Ανάλυση Προβλημάτων Κατά την ανάλυση ενός προβλήματος „ καταγράφεται η υπάρχουσα πληροφορία, „ αναγνωρίζονται ιδιαιτερότητες, „ αποτυπώνονται συνθήκες και προϋποθέσεις, οπότε „ προτείνεται κάποια μέθοδος (ιδεατή), και „ επιλύεται το πρόβλημα με τον υπολογιστή.
- 4. Κεφάλαιο 4 : Τεχνικές Σχεδίασης Αλγορίθμων Ανάλυση Προβλημάτων Πρόβλημα: με ποιά σειρά πρέπει ένας ταχυδρομικός διανομέας να επισκεφθεί κάποια χωριά ώστε να ελαχιστοποιήσει τη συνολική απόσταση που θα διανύσει ?? Πιθανές λύσεις „ κάθε φορά να διαλέγει τον κοντινότερο προορισμό „ να ακολουθήσει ένα δρομολόγιο που να ελαχιστοποιεί τη συνολική απόσταση και όχι τις επιμέρους.
- 5. Κεφάλαιο 4 : Τεχνικές Σχεδίασης Αλγορίθμων Μέθοδοι Σχεδίασης Αλγοριθμων Οι αλγόριθμοι έχουν ομαδοποιηθεί ανάλογα με τα βασικά τους χαρακτηριστικά σε διάφορες οικογένειες. „ Μέθοδος Διαίρει και Βασίλευε (Δυαδική αναζήτηση, μέθοδος διχοτόμησης-Bolzano) „ Μέθοδος Δυναμικού Προγραμματισμού (υπολογισμός δύναμης: x16) „ Άπληστη Μέθοδος (η πρώτη προσέγγιση στο πρόβλημα του ταχυδρόμου)
- 6. κάθε φορά να διαλέγει τον κοντινότερο προορισμό 1 6 Km 13 Km Km 5 4 m 10 K 8K m 2 3 9 Km 5 Km 8 Km 10 Km 13 Km 1 2 4 3 1 =36 Κm
- 7. να ακολουθήσει ένα δρομολόγιο που να ελαχιστοποιεί τη συνολική απόσταση και όχι τις επιμέρους 1 6 Km 13 Km Km 5 4 m 10 K 8K m 2 3 9 Km 6 Km 10 Km 9 Km 5 Km 1 4 3 2 1 =30 Κm