Aλγόριθμοι και Πολυπλοκότητα

[BO]

Μπορεί να ανεβάσει κανείς τα θέματα της επαναληπτικής;

Eυχαριστώ!

[theos]

Απάντηση στο γρίφο με τις 12 μπάλες που βρίσκεται στην εισαγωγή των διαλέξεων του μαθήματος:


Χωρίζουμε τις μπάλες σε 3 ομάδες των τεσσάρων έστω Α,Β,Γ.

1ο Ζύγισμα: Α στη μία πλευρά και Β στην άλλη

Έχουμε 3 περιπτώσεις :

• Α=Β, τότε κάποια από τις Γ1,Γ2,Γ3,Γ4 είναι διαφορετική οπότε:
  
  2ο ζύγισμα Γ1 και Γ2 στην μία πλευρά και Γ3 και Α1 στην άλλη πλευρά
  
  -Αν Γ1Γ2 = Γ3Α1 τότε διαφορετική είναι η Γ4 και
  3ο ζύγισμα Γ4 στη μία πλευρά και Α1 στην άλλη πλευρά για να δούμε αν η Γ4 είναι βαρύτερη ή ελαφρύτερη
  
  - Αν Γ1Γ2 > Γ3Α1 τότε
  ή Γ1 βαρύτερη ή Γ2 βαρύτερη ή Γ3 ελαφρύτερη και
  3ο ζύγισμα Γ1 στη μία πλευρά και Γ2 στην άλλη
  Αν Γ1 = Γ2 τότε Γ3 ελαφρύτερη  
  Αν Γ1 > Γ2 τότε Γ1 βαρύτερη
  Αν Γ1 < Γ2 τότε Γ2 βαρύτερη
  
  - Αν Γ1Γ2 < Γ3Α1 τότε
  ή Γ1 ελαφρύτερη ή Γ2 ελαφρύτερη ή Γ3 βαρύτερη και
  3ο ζύγισμα Γ1 στη μία πλευρά και Γ2 στην άλλη
  Αν Γ1 = Γ2 τότε Γ3 βαρύτερη  
  Αν Γ1 > Γ2 τότε Γ1 ελαφρύτερη
  Αν Γ1<Γ2 τότε Γ2 ελαφρύτερη
• Αν Α > Β τότε ξέρουμε ότι ή Α1 βαρύτερη ή Α2 βαρύτερη ή Α3 βαρύτερη ή Α4 βαρύτερη ή Β1 ελαφρύτερη ή Β2 ελαφρύτερη ή Β3 ελαφρύτερη ή Β4 ελαφρύτερη.
  2ο ζύγισμα Α1Α2Β1 στη μία πλευρά και Α3Β2Γ1 στην άλλη πλευρά
  
  -Αν Α1Α2Β1 = Α3Β2Γ1 τότε ή Α4 βαρύτερη ή Β3 ελαφρύτερη ή Β4 ελαφρύτερη και
  3ο ζύγισμα Β3 από τη μία πλευρά και Β4 από την άλλη
  Αν Β3 = Β4 τότε Α4 βαρύτερη
  Αν Β3 > Β4 τότε Β4 ελαφρύτερη
  Αν Β3 < Β4 τότε Β3 ελαφρύτερη
  
  -Αν Α1Α2Β1 > Α3Β2Γ1 τότε ή Α1 βαρύτερη ή Α2 βαρύτερη ή Β2 ελαφρύτερη και
  3ο ζύγισμα Α1 στη μία πλευρά και Α2 στην άλλη πλευρά
  Αν Α1 = Α2 τότε Β3 ελαφρύτερη  
  Αν Α1 > Α2 τότε Α1 βαρύτερη  
  Αν Α1 < Α2 τότε Α2 βαρύτερη  
  
  -Αν Α1Α2Β1 < Α3Β2Γ1 τότε ή Β1 ελαφρύτερη ή η Α3 βαρύτερη και
  3ο ζύγισμα Β1 στην μία πλευρά και Γ1 στην άλλη
  Αν Β1 = Γ1 τότε Α3 βαρύτερη
  Αν Β1 < Γ1 τότε Β1 ελαφρύτερη
• Αν Α<Β τότε κάνουμε ακριβώς τα ίδια της προηγούμενης περίπτωσης αλλά όπου έχουμε Α βάζουμε Β και όπου έχουμε Β βάζουμε Α.

Τελικά με 3 ζυγίσματα βρίσκουμε και την διαφορετική μπάλα και αν είναι ελαφρύτερη ή βαρύτερη

[O_Xamenos]

πες και την εκφωνηση στα παιδια που ισως να θελουν να εδεφτουν...
επρεπε για ξεκαρφωμα να το βαλεις στους γριφους

[theos]

Η εκφώνηση είναι: Έχουμε 12 μπάλες εκ των οποίων η μία είναι ελαφρότερη ή βαρύτερη. Πως μπορούμε με τρία ζυγίσματα να βρούμε ποιά είναι η διαφορετική μπάλα και αν είναι ελαφρότερη ή βαρύτερη

Επειδή είναι απάντηση ερωτήματος μέσα από τις διαλέξεις του μαθήματος το έβαλα εδώ...

[msl]

Έχει ανέβει στη σελίδα του Συμβώνη η πρώτη προγραμματιστική άσκηση.

Ημερομηνία παράδοσης: Τρίτη 4 Δεκεμβρίου 2007.

[theos]

Ο Συμβώνης ανέβασε στο site του την πρώτη γραπτή άσκηση με ημερομηνία παράδοσης 16/1/2008

[BO]

Όποιος παρέδωσε την πρώτη προγραμματιστική άσκηση μπορεί να την ανεβάσει τώρα που πέρασε η προθεσμία;

[pao132003]

Καταιγισμός εργασιών!

Νέα εργασία -προγραμματιστική αυτή τη φορά- ανέβηκε στο σάιτ του κ.Συμβώνη με ημερομηνία παράδοσης 12/2

[ntouzos]

Εχει μηπως κανενας τις λυσεις ή εστω ασχοληθει με την 2η εργασια που εβαλε.Εαν ναι θα μπορουσε να στειλει σε mail;Δυστυχως δεν ειχα χρονο να ασχοληθω και θεωρω οτι μετρανε πολυ στην περαιτερω κατανοηση του μαθηματος.Και πιθανον λαθος να ειναι δεν με ενδιαφερει απλα να παρω μια ιδεα.Αν δεν κανω λαθος εληξε σημερα η προθεσμια.Οποιος μπορει να βοηθησει ας μου στειλει pm.ευχαριστω προκαταβολικα!


p.s:Και οι περσινες να ειναι(οι αντιστοιχα γραπτες μη προγραμματιστικες) θα μπορουσαν να βοηθησουν

[pao132003]

Ανέβηκε και το 2ο φυλλάδιο γραπτών ασκήσεων στο σάιτ του μαθήματος με ίδια ημερομηνία παράδοσης: 12/2

[ntouzos]

παιδια,ειπε τιποτα στο τελευταιο μαθημα για το τι να προσεξουμε και τα λοι πα,Επισης ασχοληθηκε κανεις με τις γραπτες ασκησεις που εχει βαλει στο site του μαθηματος.δεν βγαζω ακρη με μερικα ερωτηματα ειδικα με τα προβληματα που αναφερονται σε στις σημειωσεις του ζαχου,Γενικα αν το εχει δωσει κανεις μπορει να μου πει που να εστιασω;

[pao132003]

Η διδακτέα ύλη
Από το βιβλίο (κεφάλαια):
1,2,3,4, 8,12
15 (εκτός 15.5)
16 (εκτός 16.4, 16.5)
22, 23, 24, 25 (εκτός 25.3)

Από τις σημειώσεις (κεφάλαια):
10
11 (εκτός απόδειξη θεωρήματος 11.6.6 (Cook)
12 (εκτός 12.6, 12.7, 12.8, 12.11, 12.12)
13


Η εξεταστέα ύλη:
Η διδακτέα ύλη.
Υλικό διαλέξεων.

[ntouzos]

παιδια εχει μηπως καμια σημειωση απο το μαθημα;Καμια ασκηση που εκανε στο μαθημα κ.τ.λ;

Off Topic

να με συμπαθατε που εμμενω αλλα θελω να το περασω ειναι τελευταιο που χρωσταω της ροης

[ntouzos]

κοιταξε κανεις τα θεματα που ειναι στο site;εχει κανεις καμια ιδεα για τα 3 τελευταια θεματα;Καμια συμβουλη κ.τ.λ;
Επισης εχει κανεις λυμενες τις ασκησεις(τις γραπτες) που εχει αναρτησει στο site;

[theos]

Ntouzos, για το θέμα 3: Έστω ότι έχεις τρείς κόμβους Α,Β,Γ με βάρη (Α,Β)=-1 (Β,Γ)=-3 (Α,Γ)=-2

Είναι προφανές ότι αυτό το γράγημα δεν έχει αρνητικό κύκλο και επίσης είναι προφανές ότι το συντομότερο μονοπάτι από το Α στο Γ, είναι μέσο του Β συνολικού βάρους -4.
Αν εφαρμόσεις τη μέθοδο που σου λέει, αλλάζει το συντομότερο μονοπάτι και δεν περνάει μέσω του Β. Πηγαίνει κατευθείαν από το Α στο Γ. Άρα η μέθοδος δεν είναι σωστή αφού βρήκαμε αντιπαράδειγμα

Για το θέμα 4 που είναι και ολόιδιο με μία από τις ασκήσεις που είχαμε να παραδώσουμε:

Το πρώτο είναι πολύ εύκολο. Απλώς τρέχεις όλα τα στοιχεία του πίνακα γειτνίασης και αν μία γραμμή τα έχει όλα 0 με την αντίστοιχη στήλη να τα έχει όλα 1 (εκτός του στοιχείου i,i) τότε ο κόμβος είναι ολική καταβόθρα.

Το δεύτερο είναι περίεργο, καθώς δεν σου επιτρέπει να κοιτάξεις όλα τα στοιχεία του πίνακα.
Αν τα κοιτάξεις όλα θέλεις nxn "κοιτάγματα" δηλαδή VxV, δηλαδή Ο(V^2)

Σε αυτό το ερώτημα εκμεταλλευόμαστε μία ιδιότητα. Ας πάρουμε το στοιχείο (1,2) του πίνακα γειτνίασης. Αν είναι 0 τότε δεν υπάρχει ακμή από τον κόμβο 1 στον κόμβο 2. Άρα ο κόμβος 2 δεν μπορεί να έχει indegree ίσο με V-1, άρα αποκλείουμε τον 2 από καταβόθρα. Ανάποδα, αν το στοιχείο (1,2) είναι 1 τότε υπάρχει ακμή από τον κόμβο 1 στον κόμβο 2. Άρα το outdegree του κόμβου 1 δεν είναι 0 και άρα ο κόμβος 1 δεν είναι καταβόθρα.

Με αυτό το τρικ χρειαζόμαστε V-1 στοιχεία του πίνακα για να αποκλείσουμε τους V-1 κόμβους. Για τον τελευταίο κόμβο που θα μας μείνει κοιτάζουμε την γραμμή και τις στήλη του πίνακα που έχει να κάνει με αυτόν τον κόμβο. Δηλαδή χρειαστήκαμε O(V) χρόνο.

Το θέμα 5 θα το κοιτάξω αύριο