Michael Kalochristianakis

Electrical and Computer Engineer

---

δομές δεδομένων και αλγόριθμοι (data structures and algorithms) 2012-13

---

διαλέξεις / εργαστήρια

• 16 - ΤΕΛΙΚΗ ΕΞΕΤΑΣΗ
• 15 - ο NP χώρος και τα PN-complete και προβλήματα
• 14 - γράφοι
• 13 - δένδρα
• 12 - συνδεδεμένες λίστες (απλές και διπλές)
• 11 - ουρές
• 10 - πρόοδος / εξέταση εργασιών
• 09 - ο άπληστος ληστής (knapsack problem)
• 08 - παραδείγματα άπληστων αλγόριθμων
• 07 - βασική αναζήτηση και ταξινόμιση πινάκων
• 06 - βασική αναζήτηση και ταξινόμιση πινάκων
• 05 - στοίβες
• 04 - πίνακες και δυναμική δέσμευση μνήμης
• 03 - δομές (structs)
• 02 - πίνακες ως ορίσματα συναρτήσεων, δύο διαστάσεων, ειδικές περιπτώσεις
• 01 - απλή εκτίμηση πολυπλοκότητας

εργασίες

• δομές/λίστες (2), προαιρετική, μέχρι 8/1
• δομές/λίστες, προαιρετική, μέχρι 8/1
• αναδρομή, μέχρι 10/12
• μετατροπή σε τριγωνικό πίνακα, μέχρι 19/11
• δυαδική αναζήτηση, μέχρι 19/11
• οι εργασίες είναι ατομικές και για κάθε μια θα παραδίδονται:
  • (α) κώδικας σε C, ο οποίος:
    • να μπορεί να γίνει compile με GCC αλλιώς με το περιβάλλον DEV-C
    • θα πρέπει να έχει κατάλληλη μορφοποίηση ώστε να είναι εύκολα αναγνώσιμος
    • θα πρέπει να περέχει αναλυτικά σχόλια που να επεξηγούν τις λειτουργίες που εκτελούνται
  • (β) σύντομη αναφορά/περιγραφή (1 σελίδα max, 12pt times new roman) που να περιγράφει την υλοποίηση σας και θα δίνει πληροφορίες για την συμπίλιση (compilation) και την εκτέλεση, εφόσον χρειάζονται
• τα παραπάνω (α) και (β) θα αποστέλλονται στη διεύθυνση kalohr@cs.teicrete.gr με mail:
  • στο θέμα του mail θα πρέπει να γράφετε "Δομές δεδομένων, εργασία Χ, ΑΜ, Ονοματεπώνυμο"
  • θα πρέπει να επισυνάπτετε τον κώδικα και την αναφορά σας
• 2011
  • για τους φοιτητές από πρόγραμμα Εράσμους, Α. Solis και V.Garcia, η προθεσμία για τις εργασίες 1,2 και 3 είναι 31/12

παρουσίες

βαθμοί

υλικό / σύνδεσμοι

• "Reducability among combinational problems", R. M. Karp
• interactive python
• P versus NP problem
• Patrick Prosser
• Petrakis@tuc
• Design and analysis of algorithms, E. Demaine

γράφημα πολυπλοκοτήτων

• 
  
  • sin(x): συχνότητα , πλάτος
  • a * x * x, a=1: πλάτος
  • a * x, a=1: πλάτος
  • a /x, a=1: πλάτος
  • a ^ x, a=2: βάση δύναμης
  • log(x)
  • sqrt(x)

εργαστήριο 2011-2012

η διεξαγωγή του εργαστηρίου

• αρχικά γίνετια περιγραφή του προβλήματος και των απαιτούμενων γνώσεων / εργαλείων από τον διδάσκοντα. Γίνεται περιγραφή της λύσης, συζήτηση των εναλλακτικών και έκφραση σε ψευδοκώδικα
• γίνεται εκτέλεση της άσκησης σε προγραμματιστικό περιβάλλον από τους σπουδαστές.
• το τελικό εκτελέσιμο και ο κώδικας αποστέλλονται στο kalohr@cs.teicrete.gr
• οι σπουδαστές θα πρέπει
  • να κατανοήσουν το πρόβλημα και τη στρατηγική της λύσης που προτείνεται
  • να μπορούν να εκφράσουν αλγόριθμους/ψευδοκώδικα σε κώδικα C που θα μπορεί να εκτελείται. Στην προσπάθεια αυτή οι σπουδαστές θα μπορούν να χρησιμοποιήσουν βοηθήματα, αναφορές και το διαδίκτυο, για παράδειγμα: GNU C reference manual, Dev-C++ resource site, JAVA API

νέα και ανακοινώσεις

• 04/12: στις 11/12 θα γίνει πρόοδος με αντικείμενο την ύλη που έχουμε καλύψει μέχρι σήμερα δηλ. εργ 1 - 7
• 06/11: το σημερινό εργαστήριο δεν έγινε λόγω διακοπής ρεύματος στις 18:30 περίπου
• 17/10: διαβάστε παρακάτω, όσοι έχετε κατωχυρώσει το εργαστήριο
• 09/10: στη σελίδα του εργαστηρίου 1 θα βρείτε κώδικα για την άσκηση 4 ο οποίος τυπώνει τον χρόνο εκτέλεσης
• αναπληρώσεις
  • 26/11 Σάββατο 10-14 πμ: αναπλήρωση (εργ 5, 6) για την ομάδα της Παρασκευής
  • 19/11 Σάββατο 10-12 πμ: αναπλήρωση (εργ 4) για την ομάδα της Παρασκευής
  • 05/11 Σάββατο 10-12 πμ: αναπλήρωση (εργ 2) για την ομάδα της Παρασκευής
• τέλος του εξαμήνου
  • διακοπές Χριστουγέννων: 22/12/2011-8/1/2012
  • τέλος μαθημάτων 20/1/2012
  • 1η εξεταστική: 23/1/2012-17/2/2012
• κατοχύρωση: όποιος έχει κατοχυρώσει το εργαστήριο υποχρεούται
  • να στέλνει με mail τις ασκήσεις που εκτελεούνται κάθε εδομάδα, καθώς και τις εργασίες (κώδικας και εκτελέσιμα)
  • υποχρεούται να λάβει μέρος στην εξέταση του μαθήματος και στις προόδους
• διάφορα
  • τη Δευτέρα 31/10 βρέθηκε στο ΠΚ 1 usb stick
  • όποιος παρακολουθεί άτυπα το εργαστήριο να το γράφει στο παρουσιολόγιο σε κάθε εργαστήριο

April, 2004