[Ανάλυση & Σχεδιασμός Αλγ.] Συζήτηση για τις προόδους και την εξεταστική

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[ονόματα των αρχείων]

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads

με προσοχή στα ονόματα των αρχείων!

[Nessa NetMonster]

1. Το T(0) πρακτικά έχει νόημα; Και πώς μπορεί να έχει τιμή διάφορη του μηδενός...

Τ(0) σημαίνει ότι η είσοδος που θεωρούμε (πχ ένας πίνακας) είναι μηδενική σε μέγεθος (πχ αντί για πίνακα του δίνεις null). Αυτό όμως από ό,τι έχω καταλάβει δεν αποκλείει κάποια δευτερεύουσα είσοδο, πχ ένα bit που θα κοιτάξει από τη μνήμη. Ο αλγόριθμος πάλι μπορεί να τρέξει και να βγάλει αποτέλεσμα.

Τώρα αν το T(0) θα είναι ο ελάχιστος χρόνος, γι'αυτό δεν είμαι σίγουρη, νομίζω ότι παίζει. Αν ο αναλυτικός τύπος για την πολυπλοκότητα είναι πχ Τ(n)=4*n^3-5*n+2 τότε θα κάνει περισσότερο χρόνο για n=0 παρά για n=1. Δεν ξέρω βέβαια πώς θα έπρεπε να είναι το πρόγραμμα για να έχει τέτοια πολυπλοκότητα

[supermodified]

Τσούκου...
Λοιπόν, ας το πάρουμε σιγά-σιγά.
Έστω ότι υποπτεύεσαι ότι η λύση της αναδρομικής σχέσης είναι O(lgn). Αυτό σημαίνει ότι πρέπει να δείξεις (σύμφωνα με τον ορισμό) ότι T(n)<=clgn. (1)
Έτσι, υποθέτεις ότι Τ(ceiling(n/2))<=clg(ceiling(n/2)) ή για πιο ισχυρά T(ceiling(n/2)<=clg(ceiling(n/2)-a) με το a>0 και προσπαθείς να αποδείξεις την (1) με διάφορες ιδιότητες και ανισότητες.
Ελπίζω να έγινα πιο κατανοητή....

Χμμ, μήπως ισχύουν και τα δύο, απλά στις σημειώσεις και στο βιβλίο (βλ. σελ. 15 στο ένα και σελίδες 16-17 στο άλλο αντίστοιχα) τα γράφει όπως τα είπα εγώ;  Γιατί βλέπω ως σημείο αφετηρίας της επαγωγής να είναι η υπόθεση ότι T(k) = O(k) για k=1,..., n-1 (για το παράδειγμα που έχουμε μαντέψει ότι είναι O(n) η λύση της αναδρομικής σχέσης -- για το δικό σου φαντάζομαι ότι θα είναι T(k) = lg(k) για k=1,...,n-1 -- με κάποια επιφύλαξη γιατί δεν έχω άνεση ακόμα με τα lgn, κτλ.)

Είναι προφανές ότι τα ξέρεις καλύτερα από μένα (και σ'ευχαριστώ και πάλι για την προσπάθεια να τα εξηγήσεις), απλά προσπαθώ να καταλάβω πώς φτάνουμε σε αυτό που λες βάσει των όσων έχω διαβάσει μέχρι τώρα σε βιβλίο και σημειώσεις. Και δε βρίσκω άκρη. Ίσως φαίνεται πιο καθαρά στις ασκήσεις;

1. Το Τ(0) λογικά είναι ο ελάχιστος χρόνος που απαιτείται για την εκτέλεση του αλγορίθμου... ε?

Κοίταξε, το σκέφτομαι καθαρά πρακτικά -- ίσως να κάνω λάθος. Όταν n=0 δε σημαίνει ότι δεν έχουμε πράξεις; Άρα Τ=0; (Μπορεί και να μην ορίζεται γιατί δεν υφίσταται τότε ο αλγόριθμος;) Αν αυτό ισχύει, προσπαθώ να καταλάβω πώς στη σελ. 17 του βιβλίου η αρχική συνθήκη προκύπτει T(1)=4 (γιατί τότε μάλλον θα'πρεπε να βγαίνει 1). EDIT: Τώρα βλέπω την απάντηση της Nessa... το ότι ο αλγόριθμος πάλι μπορεί να τρέξει με κάποια δευτερεύουσα είσοδο και να βγάλει αποτέλεσμα απαντά και στο ερωτημά μου. Ευχαριστώ Nessa!

2. α) Σωστά
   β) Μέχρι τώρα δεν το χρησιμοποιήσαμε πουθενά σε ασκήσεις...

Ωραία, σ'ευχαριστώ.

[ikoufis]

@supermodified
Αυτό που λες

[ Απ'ότι βλέπω δε δείχνουμε (δηλαδή: αποδεικνύουμε) ούτε το T(n/2) βέβαια, έτσι; Πάμε κατευθείαν στην παραδοχή για k=1,...,n-1 και μετά πάμε να αποδείξουμε την πρόταση για k=n. Το κατάλαβα καλά;

ισχύει όταν στην αναδρομική σχέση έχεις Τ(n) και T(n-1).
Οταν έχεις σχέση που έχει μέσα Τ(n) και T(n/2) όπως το παράδειγμα της Εφης κάνεις αυτό που λέει η Εφη.
Νομίζω δηλαδή ότι τα λέω σωστά

[mendelita]

Αμ μπράβο βρε Γιάννη!!
Γιατί μπερδεύτηκα κι εγώ κάποια στιγμή...

[supermodified]

ισχύει όταν στην αναδρομική σχέση έχεις Τ(n) και T(n-1).
Οταν έχεις σχέση που έχει μέσα Τ(n) και T(n/2) όπως το παράδειγμα της Εφης κάνεις αυτό που λέει η Εφη.
Νομίζω δηλαδή ότι τα λέω σωστά

Χμμ, και στο βιβλίο και στις σημειώσεις, το παράδειγμα είναι για T(n) και Τ(n/2) και η υπόθεση της επαγωγής γίνεται για Τ(κ) με k=1,...,n-1 (βλ. σελίδα 15 σημειώσεων).

Επαναλαμβάνω, ίσως να'χετε δίκιο παιδιά, αλλά βάσει των όσων έχω διαβάσει μέχρι τώρα, δεν μπορώ να καταλάβω τι δε λέω σωστά. Αν κάνω κάπου λάθος, διορθώστε με.

[mendelita]

Βασικά νομίζω το ίδιο πράγμα λέμε απλά με άλλα σύμβολα... (k==n)

[cyb3rb0ss]

Από το 1.3 Δομές δεδομένων τι μπορεί να βάλει?

Έχει κάνει τίποτα από αυτά? Ασκήσεις?

[supermodified]

Και γενικά τα παιδιά που έχουν δει τις ασκήσεις... πού να σταθούμε κυρίως στη θεωρία;

[akis]

Και γενικά τα παιδιά που έχουν δει τις ασκήσεις... πού να σταθούμε κυρίως στη θεωρία;

στα ο,ω,θ
και στα αναδρομικα

[co0p]

Παιδια μπορει να μου πει καποιος αν εχει ακουσει απο τον καθηγητη αν μπαινει και θεωρια η μονο ασκησεις?Προσωπικα δεν μπορω να το διαβασω το μαθημα..Σκοπευω να διαβασω μονο ασκησεις και ο θεος βοηθος

[OtiNaNAi]

Oι λυμενες ασκησεις του eTHMMY επιτρεπονται στην εξεταση???

[Krono]

Oι λυμενες ασκησεις του eTHMMY επιτρεπονται στην εξεταση???

Ναι, επιτρέπονται.

Παιδια μπορει να μου πει καποιος αν εχει ακουσει απο τον καθηγητη αν μπαινει και θεωρια η μονο ασκησεις?Προσωπικα δεν μπορω να το διαβασω το μαθημα..Σκοπευω να διαβασω μονο ασκησεις και ο θεος βοηθος

Μάλλον όχι γιατί το μάθημα δίνεται με ανοιχτά βιβλία. Αλλά ο κ. Γεωργιάδης δεν απέκλεισε να βάλει καμιά κρίσεως. Προσωπικά δεν το βλέπω πιθανό.

[glour]

Επειδή δεν παρακολουθώ το μάθημα η προόδος θα γίνει στην ώρα του μαθήματος 11-13 στην αίθ.2?

[akis]

Ναι!
που θα χωρέσουμε?

[svistos]

Τα Ο Ω Θ στην πρωτη ασκηση του βιβλίου πόσο τα βρήκατε??