Περιεχόμενο του μαθήματος

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

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

Το μάθημα, πέραν της εισαγωγής, αναφέρεται:

1.σε τέσσερις μεγάλες περιοχές αλγοριθμικών προβλημάτων:

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

2.σε πέντε βασικές μεθόδους σχεδίασης δραστικών αλγορίθμων:

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

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