Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

223 Ανάλυση Αλγορίθμων-Θεωρία Υπολογισμού

No description
by

ziskar ziskar

on 12 October 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of 223 Ανάλυση Αλγορίθμων-Θεωρία Υπολογισμού

Ανάλυση Αλγορίθμων
Συμπεριφέρεται ορθά ο αλγόριθμος κάτω από πραγματικές συνθήκες; Βγάζει σωστά αποτελέσματα για έγκυρα δεδομένα;
Αποδίδει ικανοποιητικά σε χρόνο(*) και σε μνήμη;
Έτσι μετά την ανάλυση θα ξέρουμε αν μπορεί αυτός να υλοποιηθεί και να εφαρμοσθεί στην πράξη. Διαφορετικά τον ξανασχεδιάζουμε κάνοντας τροποποιήσεις.

* Ο χρόνος εκτέλεσης υπολογίζεται με βάση το πόσα βήματα εκτελούνται στον αλγόριθμο

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

-Τι μπορεί να υπολογιστεί;
-Μπορεί ένας υπολογιστής να λύσει οποιοδήποτε πρόβλημα δοθέντος αρκετού χρόνου και χώρου;
Αλγόριθμος Ευκλείδη και Πολυπλοκότητα
1. ΜΝΗΜΗ: 3 θέσεις για 3 ακέραίους x, y, z
2. ΧΡΟΝΟΣ: Πλήθος των εντολών που εκτελούνται =
4

εντολές

(z<>0, z<-xmody, x<-y, y<-z) σε κάθε επανάληψη =>
4*ΑρΕπ
(
ΑρΕπ = αριθμός των επαναλήψεων) =>
για x=27 και y=78 έχουμε 4*3=12 εντολές.

Πόσες, όμως, θα είναι οι επαναλήψεις για οποιοδήποτε ζευγάρι ακεραίων; Βρέθηκε ότι ο αλγόριθμος για να υπολογίσει το ΜΚΔ των x και y, κάνει
4*logx
βήματα ή χάριν απλότητας λέμε ότι η πολυπλοκότητα του αλγόριθμου αυτού είναι O(logx) (διαβάζεται «η πολυπλοκότητα του αλγορίθμου είναι της τάξης logx»).
Θεωρία
Πολυπλοκότητας
Μελετά τους
πόρους
(χρόνος και η μνήμη) που απαιτούνται για την επίλυση ενός προβλήματος βάσει ενός συγκεκριμένου αλγορίθμου

-Πόσο γρήγορα μπορεί να λυθεί ένα πρόβλημα;
-Πόσος χώρος (μνήμη) χρειάζεται για να λυθεί ένα πρόβλημα;
Κατηγορίες Πολυπλοκότητας
Η πολυπλοκότητα ενός αλγορίθμου δίνει ένα μέτρο της χρονικής καθυστέρησης του αλγορίθμου για την επίλυση ενός προβλήματος και μπορεί να ανήκει σε μια από τις παρακάτω κατηγορίες:
O συμβολισμός "Ο"
Είναι το αρχικό γράμμα της αγγλικής λέξης order και διαβάζεται «όμικρον κεφαλαίο», χρησιμοποιείται για να αναδείξει τη γενική συμπεριφορά (την τάξη) του αλγορίθμου.
-Ας υποθέσουμε ότι θέλουμε να βρούμε το
μέγιστο
σε μια ακολουθία n αριθμών. Πόσο χρόνο πρέπει να ξοδέψουμε? Ας υποθέσουμε ότι απαιτείται 1 μονάδα χρόνου για να γίνει μια σύγκριση μεταξύ δύο αριθμών. Σε αυτή την περίπτωση χρειαζόμαστε περίπου n μονάδες χρόνου. Δεν έχουμε ιδέα για το πόσο χρόνο θα χρειαστεί το πρόγραμμα για να τρέξει, αλλά γνωρίζουμε ότι αυτό εξαρτάται γραμμικά από το n. Λέμε ότι ο αλγόριθμος έχει χρόνο εκτέλεσης “τάξης n”
-Έχω ένα νούμερο μεταξύ 0 και 63. Κάνετε μια ερώτηση κι εγώ απαντάω με ναι ή όχι. Πόσο χρόνο θα χρειαστείτε για να βρείτε τον αριθμό? Ας υποθέσουμε ότι απαιτείται 1 μονάδα χρόνου για να τεθεί και να απαντηθεί μια ερώτηση. Σε αυτή την περίπτωση χρειαζόμαστε περίπου log n μονάδες χρόνου. Λέμε ότι ο αλγόριθμος έχει χρόνο εκτέλεσης “τάξης log n”
Χρόνοι εκτέλεσης
Στον Πίνακα 2.3 παρουσιάζονται οι χρόνοι εκτέλεσης για διάφορες πολυπλοκότητες και μεγέθη προβλημάτων
http://ee.auth.gr/academics/undergraduate-studies/courses/
Full transcript