[Ανάλυση Αλγορίθμων] Απορίες στις ασκησεις 2015

[Thmmy.gr portal]

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

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Αντιστοίχηση Μαθημάτων ΝΠΣ με ΠΠΣ]

Επίσημη ενημέρωση για Αντιστοίχηση Μαθημάτων ΝΠΣ με ΠΠΣ και η συζήτηση στο forum.

[Πάτρικ Αστέρης]

ρε για πειτε μια στο Β της α προοδου 2015 τελικα ποιο ειναι σωστο;

εγω βρηκα οτι T(n) = 3n/2 - 2

πως το κανες;
Βασικα εγω πηρα το πρωτο και το ελεγξα με ανισοτητα και ψιλο βγαινει
Επισης εχει μια παρομοια λυμενη στο 4ο κεφ στις ασκησεις

[Πάτρικ Αστέρης]

Στο θεμα Α της 1ης προοδου του 2015 βρηκατε τις προτασεις ΛΑΘΟΣ ετσι?

ετσι νομιζω εγω το εκανα στην πρωτη με αντιπαραδειγμα οπου f(n) = n και g(n) = n+1
και στην δευτερη με αντιπαραδειγμα οπου f(n) = 2ⁿ και g(n) = 2²ⁿ  f(n) = 2²ⁿ και  g(n) = 2ⁿ

το 1ο πως βγαινει σαν αντιπαραδειγμα;
εντιτ:
το 2ο πως βγαινει σαν αντιπαραδειγμα;

[nikos1]

ρε για πειτε μια στο Β της α προοδου 2015 τελικα ποιο ειναι σωστο;

εγω βρηκα οτι T(n) = 3n/2 - 2

πως το κανες;
Βασικα εγω πηρα το πρωτο και το ελεγξα με ανισοτητα και ψιλο βγαινει
Επισης εχει μια παρομοια λυμενη στο 4ο κεφ στις ασκησεις

εγω το εκανα ως εξης, λεω εστω οτι ειναι το πρωτο αρα Τ(n) = 2lgn -1.
ελεγχω αν Τ(2) = 1 (Τ(2) = 2lg2 -1 = 1 αρα ισχυει για n=1) και στη συνεχεια κανω οτι λεει η ασκηση 2.3-3. Δοκιμαζοντας και τις 3 περιπτωσεις βγαινει το γ ως σωστο

[Πάτρικ Αστέρης]

ρε για πειτε μια στο Β της α προοδου 2015 τελικα ποιο ειναι σωστο;

εγω βρηκα οτι T(n) = 3n/2 - 2

πως το κανες;
Βασικα εγω πηρα το πρωτο και το ελεγξα με ανισοτητα και ψιλο βγαινει
Επισης εχει μια παρομοια λυμενη στο 4ο κεφ στις ασκησεις

εγω το εκανα ως εξης, λεω εστω οτι ειναι το πρωτο αρα Τ(n) = 2lgn -1.
ελεγχω αν Τ(2) = 1 (Τ(2) = 2lg2 -1 = 1 αρα ισχυει για n=1) και στη συνεχεια κανω οτι λεει η ασκηση 2.3-3. Δοκιμαζοντας και τις 3 περιπτωσεις βγαινει το γ ως σωστο

σωστος εισαι

[κύριος Φασόλης]

Στο θεμα Α της 1ης προοδου του 2015 βρηκατε τις προτασεις ΛΑΘΟΣ ετσι?

ετσι νομιζω εγω το εκανα στην πρωτη με αντιπαραδειγμα οπου f(n) = n και g(n) = n+1
και στην δευτερη με αντιπαραδειγμα οπου f(n) = 2ⁿ και g(n) = 2²ⁿ  f(n) = 2²ⁿ και  g(n) = 2ⁿ

το 1ο πως βγαινει σαν αντιπαραδειγμα;
εντιτ:
το 2ο πως βγαινει σαν αντιπαραδειγμα;

καταρχας ειπα βλακεια το 1ο δεν ειναι λαθος ειναι σωστο (δεν το χω αποδειξει ακομα μαθηματικα αλλα i'm working on it )
το 2ο τωρα... λοιπον εχεις f(n) = 2²ⁿ αρα lgf(n)= 2n ομοια για g(n) βγαζεις οτι lgg(n)=n και ισχυει οτι 2n=Θ(n) ομως αμα δεις δεν ισχυει οτι 2²ⁿ=Θ(2ⁿ) (τσεκαρε ασκηση 6 κεφαλαιο 3 απο αυτες που εκανε ο Θεμης)

[Πάτρικ Αστέρης]

Σχετικα με σωστο - λαθος στην προοδο 2014Β:

Τα πρωτα δυο μου φαινονται σωστα, δεν ξερω πως να τα αποδειξω.

Το τριτο νομιζω οτι ειναι λαθος, αν εχω καταλαβει καλα τι εννοει. Αν εννοει οτι ο κυκλος εχει μοναδικη ακμη μικροτερου βαρους e, τοτε ειναι λαθος και το αντιπαραδειγμα ειναι αυτη η ασχημη εικονα:
http://imgur.com/BfAKqL8
Το 2 ειναι η ακμη μικροτερου βαρους στον κυκλο εκεινο, αλλα οπως φαινεται μπορω να φτιαξω ΕΣΔ, χωρις να την συμπεριλαβω.

Αν εννοει οτι ειναι η μιρκοτερη σε ολοκληρο το γραφημα, τοτε παω πασο, σωστο πρεπει να ειναι. Να το αποδειξω δε μπορω 

Ας το επιβεβαιωσει καποιος.

Λεει παντως να μην θεωρησουμε οτι οι ολες οι ακμες εχουν διαφορετικα βαρη,εκτος αν το λεει ρητα.Αρα η ακμη ειναι η μικροτερη απο ολες.

[Πάτρικ Αστέρης]

Στο θεμα Α της 1ης προοδου του 2015 βρηκατε τις προτασεις ΛΑΘΟΣ ετσι?

ετσι νομιζω εγω το εκανα στην πρωτη με αντιπαραδειγμα οπου f(n) = n και g(n) = n+1
και στην δευτερη με αντιπαραδειγμα οπου f(n) = 2ⁿ και g(n) = 2²ⁿ  f(n) = 2²ⁿ και  g(n) = 2ⁿ

το 1ο πως βγαινει σαν αντιπαραδειγμα;
εντιτ:
το 2ο πως βγαινει σαν αντιπαραδειγμα;

καταρχας ειπα βλακεια το 1ο δεν ειναι λαθος ειναι σωστο (δεν το χω αποδειξει ακομα μαθηματικα αλλα i'm working on it )
το 2ο τωρα... λοιπον εχεις f(n) = 2²ⁿ αρα lgf(n)= 2n ομοια για g(n) βγαζεις οτι lgg(n)=n και ισχυει οτι 2n=Θ(n) ομως αμα δεις δεν ισχυει οτι 2²ⁿ=Θ(2ⁿ) (τσεκαρε ασκηση 6 κεφαλαιο 3 απο αυτες που εκανε ο Θεμης)

ναι αλλα στο αντιπαραδειγμα, σου λεει οτι πρεπει να ισχυει το 1ο και να μην ισχυει το 2ο.Δεν εχει διπλη συνεπαγωγη.
Τελοσπαντων,το 1ο συμφωνω οτι ειναι σωστο και το 2ο οτι ειναι λαθος.
Το αντιπαραδειγμα μου ειναι
f(n)=n² και g(n)=n

[SportBillyPap]

Στην προοδο 14Β στο θεμα 2 ποια ειναι η συναρτηση δυναμικου?