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

[Hengeo]

Μήπως ξέρει κανείς πως λύνεται το 1ο θέμα της επαναληπτικής 2008 (υπάρχουν στο εργαλείο τα θέματα); Έχω σπάσει το κεφάλι μου 2 μέρες τώρα, έχω βρει αλγόριθμους με O(V*E) αλλά με O(V+E) που ζητάει δεν μου βγαίνει.

Ευχαριστώ εκ των προτέρων!

[Ippasos]

Το μάθημα που χαθηκε σημερα και στο οποιο θα λύναμε ασκήσεις από το πρώτο φυλλάδιο,πήγε τη πέμπτη στις 14.30

[nightCrawler]

(Λάθος! βλ. παρακάτω)
Χοντρικά, ψάχνεις για ένα κύκλο μήκους 3 (τρίγωνο). Επομένως, αν κάνεις μια DFS και φτάσεις σε ακμή που κοιτάει προς τα πίσω, ελέγχεις αν η διαφρορά των χρόνων άφιξης σε καθέναν από τους κόμβους είναι 2. Και το οποίο θα σήμαινε ότι σχηματίστηκε τρίγωνο. Δες Διάλεξη 4 , σελ. 4 το τέταρτο σχηματάκι (μαγικό το 4 ) , τη στιγμή που η γραμμή γίνεται διακεκομμένη, γίνεται back edge (προς τα πίσω ακμή). Και εκεί έχει ένα τριγωνάκι μιας και η διαφορά "βάθους" των δύο κόμβων είναι 2 (σκέψου το σα δέντρο αν σε βολεύει).
Τα παραπάνω με κάθε επιφύλαξη...

[theos]

Δυστυχώς υπάρχει αντιπαράδειγμα που δεν ισχύει αυτό που λες nightCrowler. Όταν το είχε ποστάρει ο Hengeo, αυτήν την απάντηση είχα δώσει και εγώ μέσα σε 5 λεπτά, αλλά είδα ότι δεν ισχύει και το έσβησα...

Πάντως, το να βρεις κύκλο μονού μήκους γίνεται κάπως έτσι αριθμώντας τους κόμβους με 0 και 1 με έναν συγκεκριμένο τρόπο ταυτόχρονα με το τρέξιμο του dfs.

[semfe17]

Επειδή δεν το παρακολουθούσα μέσα στη χρονιά και δεν ξέρω που γίνεται το μάθημα, αύριο στις 14.30 σε ποιά αίθουσα θα γίνουν οι ασκήσεις??

[nightCrawler]

Ναι, έχεις δίκιο theos, θα επανέλθω σ' αυτό. Σίγουρα αύριο είναι το μάθημα ασκήσεων? Το λέω γιατί κανονικά είναι Παρασκευή το μάθημα.

[semfe17]

Το μάθημα που χαθηκε σημερα και στο οποιο θα λύναμε ασκήσεις από το πρώτο φυλλάδιο,πήγε τη πέμπτη στις 14.30

δεν ήμουν όταν το κανονίσανε! από εδώ το είδα και εγώ!

[Ippasos]

Παιδιά το μάθημα της Παρασκευής θα γίνει κανονικά, απλα τη Πέμπτη στις 14.30 θα γίνει αναπλήρωση του μαθήματος της Τρίτης, αμφιθέατρο ή στο 2 ή στο 3 θα βρεθουμε

[elta]

paidia eleos....pote skopeyei n vgalei apotelesmata o symvwnhs. paei enas mhnas apo tote pou to dwsame to k@@@mathima!!!

[ian]

Pantws prin apo mia ebdomada pou ton rwtisa mou eipe oti tha ta vgalei telos tou mina (tou marti) !!!!

[Hengeo]

Pantws prin apo mia ebdomada pou ton rwtisa mou eipe oti tha ta vgalei telos tou mina (tou marti) !!!!

Είπε γιατί τέτοια καθυστέρηση; Γενικά θυμάμαι ότι συνήθιζε να βγάζει γρήγορα τα αποτελέσματα..

[elta]

kai oxi tipote allo perimenoume toson kairo kai sto telos tha doume sthn katastash pali kanena 3!!! ti na paw as elpisw oti tha ta vgalei syntoma giati ta neyra mou einai sthhhhhnnn tsitaaaaaaaaaaa

[remilt]

ΣΟΣ!!! Η σελίδα του Συμβώνη δεν αποκρίνεται και δεν έχω τις σημειώσεις και τα φυλλάδια ασκήσεων όποιος τα έχει κατεβάσει ας κάνει την καλή να τα ανεβάσει στο site γιατί μόνο από το βιβλίο δεν βγάζει άκρη κανένας.

[kostas213]

Επειδή βιαζόμουνα τραγικά, πέταξα ένα link στο μάθημα (στο εργαλείο) με όλες τις διαλέξεις. Θα το ανεβάσω κανονικά το βράδυ.

Οι διαλέξεις αυτές είναι από πέρυσι. Αν λείπει κάτι ή έχει γίνει κάποια αλλαγή ας με ενημερώσει κάποιος για να τις ανεβάσω σωστά.

[remilt]

χίλια ευχαριστώ!!!