Αλγόριθμοι και Δομές Δεδομένων [2020-21]: Μάθημα

[pefraimi]

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

[pefraimi]

... στο παράδειγμα που δώσατε με τα αγόρια κ τα κορίτσια, ασταθές ζευγάρι ονομάζουμε τελικά αυτό που θα ήταν καλύτερα μαζι αλλά δεν είναι τώρα ή αυτο που είναι μαζί τώρα αλλά ένας ή και οι δύο δεν είναι ικανοποιημένοι;
Εννοώ σε αυτό το παράδειγμα είναι ασταθές η Βίκυ κ ο Φώτης ή η Βίκυ κ ο Χάρης; ...

Είναι θέμα ορισμού:
Λέμε ότι το ζευγάρι Φώτης - Βίκυ είναι μια "αστάθεια", διότι προτιμούν ο ένας τον άλλο σε σχέση
με το ταίρι που έχει ο καθένας από το ταίριασμα της διαφάνειας 6. 'Ομοια, αστάθεια είναι και το
ζευγάρι Φώτης - Άννα.

[pefraimi]

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

Οι προϋποθέσεις για τη συμμετοχή στην τελική εξέταση περιγράφονται αναλυτικά στο αρχείο
"ΑλγΔΔ 2020-21 - Περιγραφή και Απαιτήσεις.pdf"
που υπάρχει στο eclass του μαθήματος.

[pefraimi]

Θα ήθελα να ρωτήσω,στο παράδειγμα της διαφάνειας 7 στο αρχείο "DSAlg04 mst",ο αλγόριθμος του prim, θα μπορούσε αφού φτάσει στην ακμή 5 να πάει πρώτα στην ακμή 6 ,έπειτα στην 4 και τέλος στην 8 ή είναι λάθος?Σας κάνω αυτήν την ερώτηση επειδή ο αλγόριθμος διαλέγει πάντα την ακμή με το μικρότερο βάρος.

Στον αλγόριθμο Prim, σε κάθε βήμα προσθέτουμε στο T την ακμή e με το μικρότερο βάρος από όσες ακμές έχουν ακριβώς ένα άκρο στο T. Επομένως, η σειρά επιλογής των ακμών επηρεάζεται από το ποια θα είναι η κορυφή εκκίνησης και είναι πολύ πιθανό να συμβεί να επιλεγεί μια ακμή μικρότερου βάρους μετά από μία ακμή μεγαλύτερου βάρους.

[pefraimi]

Έστω ότι μας μας βάζετε μια άσκηση ... . Είναι απαραίτητο να κάνουμε την αναλυτική διαδικασία επίλυσης όπως στις διαφάνειες ή μπορούμε να γράψουμε κατευθείαν το αποτέλεσμα ώστε να γλυτώσουμε χρόνο;

Θα πρέπει να απαντήσετε με βάση τα ζητούμενα της εκφώνησης. Εάν ζητάει μόνο το αποτέλεσμα ή κάτι άλλο συγκεκριμένο, αρκεί να γράψετε μόνο αυτό που ζητάει. Εάν όμως ζητάει να δικαιολογήσετε την απάντησή σας θα πρέπει να δώσετε περισσότερα στοιχεία για τη λύση που θα παρουσιάσετε, δεν θα αρκεί μόνο ένα αποτέλεσμα.

[pefraimi]

... Στη συγκεκριμένη άσκηση που έχω επισυνάψει η λύση για τη BFS είναι 0-2-3-4-5-1-6-7-8-9 ή 0-2-3-4-5-1-7-6-8-9 ; Σας ρωτάω, καθώς θυμάμαι ότι στα μαθήματα είχαμε πει πως σε τέτοιες περιπτώσεις προτιμάμε τον μικρότερο κόμβο να εξερευνήσουμε πρώτα, αλλά στον ψευτοκώδικα που έχει στις διαφάνειες λέει να εξερευνήσουμε πρώτα τους κόμβους που έχουμε βρει πρώτους, στη προκείμενη περίπτωση το 5 που το βρήκαμε πριν το 1. Πως θα πρέπει να το κάνουμε τελικά ;
Σας ευχαριστώ εκ των προτέρων, ...

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

Στον συγκεκριμένο γράφο η BFS από τον κόμβο 0 δίνει την ακολουθία: 0-2-3-4-5-1-7-6-8-9
Ο κόμβος 5 θα μπει στην ουρά FIFO πριν από τον κόμβο 1 και επομένως ο κόμβος 7 θα μπει και αυτός πριν από τον κόμβο 6.

[pefraimi]

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

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

[pefraimi]

θα ήθελα να σας κάνω μια ερώτηση. Όσον αφορά την εύρεση του minimun spanning tree με τη μέθοδο Kruskal, υπάρχει πιθανότητα ο δοσμένος γράφος να έχει έναν ή περισσότερους κόμβους οι οποίοι δεν είναι συνδεδεμένοι με άλλους;

Συνήθως αναφερόμαστε σε συνεκτικό γράφο όταν μελετούμε το πρόβλημα MST. Αν δεν είναι συνεκτικός δεν μπορεί να υπάρξει δέντρο που να εκτείνεται σε όλο το γράφο.