Aλγόριθμοι και Πολυπλοκότητα
Συντονιστές: markelos, Ryu, meleneemil, Nasia!
- Hengeo
- Δημοσιεύσεις: 1478
- Εγγραφή: Τρί Φεβ 20, 2007 1:57 pm
- Real Name: Γιώργος
- Gender: Male
- Facebook ID: 0
- Τοποθεσία: Η πιο γλυκιά πατρίδα είναι η καρδιά..
Re: Aλγόριθμοι και πολυπλοκότητα
Μήπως ξέρει κανείς πως λύνεται το 1ο θέμα της επαναληπτικής 2008 (υπάρχουν στο εργαλείο τα θέματα); Έχω σπάσει το κεφάλι μου 2 μέρες τώρα, έχω βρει αλγόριθμους με O(V*E) αλλά με O(V+E) που ζητάει δεν μου βγαίνει.
Ευχαριστώ εκ των προτέρων!
Ευχαριστώ εκ των προτέρων!
Άνθρωπε γνώρισε τον εαυτό σου και θα γνωρίσεις το σύμπαν και τους θεούς - Δελφικό ρητό
Re: Aλγόριθμοι και πολυπλοκότητα
Το μάθημα που χαθηκε σημερα και στο οποιο θα λύναμε ασκήσεις από το πρώτο φυλλάδιο,πήγε τη πέμπτη στις 14.30
- nightCrawler
- Δημοσιεύσεις: 80
- Εγγραφή: Τρί Φεβ 24, 2009 8:51 pm
- Real Name: ilias
- Gender: Male
- Facebook ID: 0
Re: Aλγόριθμοι και πολυπλοκότητα
(Λάθος! βλ. παρακάτω)
Χοντρικά, ψάχνεις για ένα κύκλο μήκους 3 (τρίγωνο). Επομένως, αν κάνεις μια DFS και φτάσεις σε ακμή που κοιτάει προς τα πίσω, ελέγχεις αν η διαφρορά των χρόνων άφιξης σε καθέναν από τους κόμβους είναι 2. Και το οποίο θα σήμαινε ότι σχηματίστηκε τρίγωνο. Δες Διάλεξη 4 , σελ. 4 το τέταρτο σχηματάκι (μαγικό το 4 ) , τη στιγμή που η γραμμή γίνεται διακεκομμένη, γίνεται back edge (προς τα πίσω ακμή). Και εκεί έχει ένα τριγωνάκι μιας και η διαφορά "βάθους" των δύο κόμβων είναι 2 (σκέψου το σα δέντρο αν σε βολεύει).
Τα παραπάνω με κάθε επιφύλαξη...
Χοντρικά, ψάχνεις για ένα κύκλο μήκους 3 (τρίγωνο). Επομένως, αν κάνεις μια DFS και φτάσεις σε ακμή που κοιτάει προς τα πίσω, ελέγχεις αν η διαφρορά των χρόνων άφιξης σε καθέναν από τους κόμβους είναι 2. Και το οποίο θα σήμαινε ότι σχηματίστηκε τρίγωνο. Δες Διάλεξη 4 , σελ. 4 το τέταρτο σχηματάκι (μαγικό το 4 ) , τη στιγμή που η γραμμή γίνεται διακεκομμένη, γίνεται back edge (προς τα πίσω ακμή). Και εκεί έχει ένα τριγωνάκι μιας και η διαφορά "βάθους" των δύο κόμβων είναι 2 (σκέψου το σα δέντρο αν σε βολεύει).
Τα παραπάνω με κάθε επιφύλαξη...
Τελευταία επεξεργασία από το μέλος nightCrawler την Τετ Ιαν 20, 2010 9:54 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Count on the unexpected.
The night shift
The night shift
- theos
- Δημοσιεύσεις: 762
- Εγγραφή: Κυρ Νοέμ 05, 2006 4:53 am
- Real Name: Αριστοτέλης-Εμμανουήλ Θάνος-Φίλης (Μάνος) ge04017
- Gender: Male
- Τοποθεσία: Alwaysland
Re: Aλγόριθμοι και πολυπλοκότητα
Δυστυχώς υπάρχει αντιπαράδειγμα που δεν ισχύει αυτό που λες nightCrowler. Όταν το είχε ποστάρει ο Hengeo, αυτήν την απάντηση είχα δώσει και εγώ μέσα σε 5 λεπτά, αλλά είδα ότι δεν ισχύει και το έσβησα...
Πάντως, το να βρεις κύκλο μονού μήκους γίνεται κάπως έτσι αριθμώντας τους κόμβους με 0 και 1 με έναν συγκεκριμένο τρόπο ταυτόχρονα με το τρέξιμο του dfs.
Πάντως, το να βρεις κύκλο μονού μήκους γίνεται κάπως έτσι αριθμώντας τους κόμβους με 0 και 1 με έναν συγκεκριμένο τρόπο ταυτόχρονα με το τρέξιμο του dfs.
Λογική είναι η τέχνη να κάνεις λάθος με αυτοπεποίθηση!!!
Re: Aλγόριθμοι και πολυπλοκότητα
Επειδή δεν το παρακολουθούσα μέσα στη χρονιά και δεν ξέρω που γίνεται το μάθημα, αύριο στις 14.30 σε ποιά αίθουσα θα γίνουν οι ασκήσεις??
- nightCrawler
- Δημοσιεύσεις: 80
- Εγγραφή: Τρί Φεβ 24, 2009 8:51 pm
- Real Name: ilias
- Gender: Male
- Facebook ID: 0
Re: Aλγόριθμοι και πολυπλοκότητα
Ναι, έχεις δίκιο theos, θα επανέλθω σ' αυτό. Σίγουρα αύριο είναι το μάθημα ασκήσεων? Το λέω γιατί κανονικά είναι Παρασκευή το μάθημα.
Count on the unexpected.
The night shift
The night shift
Re: Aλγόριθμοι και πολυπλοκότητα
Ippasos έγραψε:Το μάθημα που χαθηκε σημερα και στο οποιο θα λύναμε ασκήσεις από το πρώτο φυλλάδιο,πήγε τη πέμπτη στις 14.30
δεν ήμουν όταν το κανονίσανε! από εδώ το είδα και εγώ!
Re: Aλγόριθμοι και πολυπλοκότητα
Παιδιά το μάθημα της Παρασκευής θα γίνει κανονικά, απλα τη Πέμπτη στις 14.30 θα γίνει αναπλήρωση του μαθήματος της Τρίτης, αμφιθέατρο ή στο 2 ή στο 3 θα βρεθουμε
-
- Δημοσιεύσεις: 12
- Εγγραφή: Τρί Μάιος 06, 2008 12:30 pm
- Real Name: koukouroukou
- Gender: Female
- Facebook ID: 0
Re: Aλγόριθμοι και πολυπλοκότητα
paidia eleos....pote skopeyei n vgalei apotelesmata o symvwnhs. paei enas mhnas apo tote pou to dwsame to k@@@mathima!!!
Re: Aλγόριθμοι και πολυπλοκότητα
Pantws prin apo mia ebdomada pou ton rwtisa mou eipe oti tha ta vgalei telos tou mina (tou marti) !!!!
- Hengeo
- Δημοσιεύσεις: 1478
- Εγγραφή: Τρί Φεβ 20, 2007 1:57 pm
- Real Name: Γιώργος
- Gender: Male
- Facebook ID: 0
- Τοποθεσία: Η πιο γλυκιά πατρίδα είναι η καρδιά..
Re: Aλγόριθμοι και πολυπλοκότητα
Είπε γιατί τέτοια καθυστέρηση; Γενικά θυμάμαι ότι συνήθιζε να βγάζει γρήγορα τα αποτελέσματα..ian έγραψε:Pantws prin apo mia ebdomada pou ton rwtisa mou eipe oti tha ta vgalei telos tou mina (tou marti) !!!!
Άνθρωπε γνώρισε τον εαυτό σου και θα γνωρίσεις το σύμπαν και τους θεούς - Δελφικό ρητό
-
- Δημοσιεύσεις: 12
- Εγγραφή: Τρί Μάιος 06, 2008 12:30 pm
- Real Name: koukouroukou
- Gender: Female
- Facebook ID: 0
Re: Aλγόριθμοι και πολυπλοκότητα
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
- Δημοσιεύσεις: 95
- Εγγραφή: Δευ Δεκ 11, 2006 1:14 pm
- Real Name: Καραμανλής Μίλτος
- Gender: Male
- Τοποθεσία: Αθήνα
Re: Aλγόριθμοι και πολυπλοκότητα
ΣΟΣ!!! Η σελίδα του Συμβώνη δεν αποκρίνεται και δεν έχω τις σημειώσεις και τα φυλλάδια ασκήσεων όποιος τα έχει κατεβάσει ας κάνει την καλή να τα ανεβάσει στο site γιατί μόνο από το βιβλίο δεν βγάζει άκρη κανένας.
- kostas213
- Forum Administrator
- Δημοσιεύσεις: 1531
- Εγγραφή: Τρί Νοέμ 28, 2006 8:03 pm
- Real Name: Κωνσταντίνος
- Gender: Male
- Τοποθεσία: Zürich
Re: Aλγόριθμοι και πολυπλοκότητα
Επειδή βιαζόμουνα τραγικά, πέταξα ένα link στο μάθημα (στο εργαλείο) με όλες τις διαλέξεις. Θα το ανεβάσω κανονικά το βράδυ.
Οι διαλέξεις αυτές είναι από πέρυσι. Αν λείπει κάτι ή έχει γίνει κάποια αλλαγή ας με ενημερώσει κάποιος για να τις ανεβάσω σωστά.
Οι διαλέξεις αυτές είναι από πέρυσι. Αν λείπει κάτι ή έχει γίνει κάποια αλλαγή ας με ενημερώσει κάποιος για να τις ανεβάσω σωστά.
There's no place like ::1
- remilt
- Δημοσιεύσεις: 95
- Εγγραφή: Δευ Δεκ 11, 2006 1:14 pm
- Real Name: Καραμανλής Μίλτος
- Gender: Male
- Τοποθεσία: Αθήνα
Re: Aλγόριθμοι και πολυπλοκότητα
χίλια ευχαριστώ!!!