Αλγόριθμοι


Διδάσκων/ουσα: Ανδρόνικος Θεόδωρος
Κωδικός Μαθήματος: HY-020
Τύπος Μαθήματος: Μάθημα Κορμού
Επίπεδο Μαθήματος: Προπτυχιακό
Γλώσσα Μαθήματος: Ελληνικά
Εξάμηνο: Δ΄
ECTS: 6
Διδακτικές Μονάδες: 4
Ώρες Διάλεξης: 4
Σύνολο Ωρών: 4
Σελίδα E Class: https://opencourses.ionio.gr/courses/DDI189/
Αντικειμενικοί Στόχοι - Επιδιωκόμενα Μαθησιακά Αποτελέσματα:

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

          Με την επιτυχή ολοκλήρωση των σπουδών στο μάθημα οι φοιτήτριες και φοιτητές θα είναι σε θέση:

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

Το μάθημα απευθύνεται σε φοιτήτριες και φοιτητές του δεύτερου έτους σπουδών. Καλύπτει τα εξής θέματα:

  • Η έννοια του αλγορίθμου και της πολυπλοκότητας. Οι βασικές έννοιες της ανάλυσης αλγορίθμων και το απαιτούμενο μαθηματικό υπόβαθρο.
  • Τεχνικές επίλυσης αναδρομικών εξισώσεων και τεχνικές σχεδίασης αλγορίθμων. Η τεχνική «διαίρει και βασίλευε».
  • Ο αλγόριθμος της γρήγορης ταξινόμησης και ο ελάχιστος χρόνος εκτέλεσης αλγορίθμων ταξινόμησης.
  • Η τεχνική του δυναμικού προγραμματισμού, η ιδιότητα βέλτιστων επιμέρους δομών και το πρόβλημα του πολλαπλασιασμού ακολουθίας πινάκων.
  • Το ακέραιο πρόβλημα του σακιδίου, το πρόβλημα της διαμέρισης και η άπληστη τεχνική. Δρομολόγηση εργασιών, απληστία και το κλασματικό πρόβλημα του σακιδίου.
  • Θεωρία γραφημάτων και αναπαράσταση γραφημάτων. Αλγόριθμοι εξερεύνησης γραφημάτων: αναζήτηση πρώτα σε πλάτος, αναζήτηση πρώτα σε βάθος και τοπολογική ταξινόμηση.
  • Ελάχιστα επικαλύπτοντα δένδρα. Άπληστος υπολογισμός ελάχιστου επικαλύπτοντος δέντρου.
  • Συντομότερα μονοπάτια, συντομότερα μονοπάτια μοναδικής πηγής και συντομότερα μονοπάτια για όλα τα ζεύγη κορυφών.
  • Οπισθοδρόμηση, διακλάδωση και φράξιμο.
  • Βασικοί αλγόριθμοι συμβολοσειρών.
  • Εισαγωγή στη Θεωρία Υπολογιστικής Πολυπλοκότητας.
Συνιστώμενη βιβλιογραφία προς μελέτη:
  1. “ΕΙΣΑΓΩΓΗ ΣΤΟΥΣ ΑΛΓΟΡΙΘΜΟΥΣ”, Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Εκδόσεις ΙΤΕ - Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-473-6, 2016
  2. “ΑΛΓΟΡΙΘΜΟΙ”, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Εκδόσεις Κλειδάριθμος ΕΠΕ, ISBN 978-960-461-211-6, 2009
  3. “ΣΧΕΔΙΑΣΜΟΣ ΑΛΓΟΡΙΘΜΩΝ”, Jon Kleinberg, Eva Tardos, Εκδόσεις Κλειδάριθμος ΕΠΕ, ISBN 978-960-461-207-9, 2009

Επιστροφή

Σπουδές

Κτίριο Γραμματειών (Κτίριο 3) Πλατεία Τσιριγώτη 7 (πρώην Πλατεία Παλιού Ψυχιατρείου) Κέρκυρα, 49100 τηλ:26610 87760 / 87761 / 87763
e-mail: cs@ionio.gr
certification
<< <
Μάιος 2024
> >>
Δε Τρ Τε Πε Πα Σα Κυ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Ανάγνωση ΚειμένουΑνάγνωση Κειμένου Αναγνωσιμότητα ΚειμένουΑναγνωσιμότητα Κειμένου Αντίθεση ΧρωμάτωνΑντίθεση Χρωμάτων
Επιλογές Προσβασιμότητας