THMMY.gr

Ξέρεις κανείς ή έχει βρει κάποιο καλό υλικό ή κάποια σειρά ασκήσεων ,σχετικά με το στυλ  για το θέμα που θα πέσει για κώδικα ? Στο ethmmy μου φαίνεται έχει περιορισμένα πράγματα.( ή κάποια συμβουλή γενικά :P )

στον αλγοριθμο ταξινομησης εισαγωγης στις διαφαναειες. το πρωτο βημα που λεει ξεκινωντας απο το πρωτο στοιχειο του πινακα δεν ειναι λογικα λαθος; αφου μετα καλουμαι να συγκρινω με τα ΠΡΟΗΓΟΥΜΕΝΑ στοιχεια του πινακα; μαλιστα δεν μπορω καν να ξεκινησω απο το 2ο στοιχειο (i=1) αφου αν ο πρωτος ειναι μικροτερος απο τον δευτερο ο αλγοριθμος λεει μετακινουμε τα κλειδια απο a[k+1] μεχρι a[i-1] οπου το δευτερο προηγειται του πρωτου σε αυτην την περιπτωση. αρα ουσιαστικα (οπως και φαινεται στο παραδειγμα) ειμαστε αναγκασμενοι να ξεκιναμε απο το 3ο στοιχειο. κανω λαθος;

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

Στα AVL δεντρα υπαρχουν παραπανω απο 1 σωστες λυσεις?

Έλυσα ορισμένα θέματα της Β ομάδας και φαίνεται πως οι απαντήσεις του uploader εχουν αρκετά λάθη, οπότε μην τις εμπιστεύεσαι.

Ξερει κανεις αν θα ανεβει δειγμα εξετασης? Νομιζω κατι τετοιο ειχε ακουστει(δειγμα οπως τις προγραμματιστικες τεχνικες) ::)

Ελυσα καποια θεματα απο Φεβρουαριο 16 ομαδα Α

Θεμα 1ο : a)-B  β)-Β  γ)-C δ)-Ε

Θεμα 2o : Α) Τα βγαζω ιδια
                Β) Θελω βοηθεια παιδια για το πως βγαινει ολο αυτο

Θεμα 3ο : α) Βγαζω αλλο δεντρο (66,21,69,4,53,68,83,0,0,41,55,0,0,0,97)
                 β)Τα ιδια

Έχει καποιος να προτείνει βιντεο που να εξηγει quicksort? :D

https://www.youtube.com/watch?v=mN5ib1XasSA
https://www.youtube.com/watch?v=aQiWF4E8flQ

Το πρώτο βιντεάκι έχει και την προσέγγιση στην JAVA όμως το 2ο νομίζω θα σε βοηθήσει περισσότερο

Θέμα 1 , γ ερώτημα πως βγάζεις 4 τέσσερις κόμβους ? εγώ βγάζω τρεις  ,διότι όταν βγάζω το 3 συγχωνεύω τους κάτω κόμβους 1,5 , εσύ τι διαδικασία έκανες για να το βγάλεις αυτό ?

Νομιζω οτι οταν βγαζεις το 3,ανεβαινει στη ριζα το 5,ενω τα αλλα μενουν ως εχουν.Ο κομβος στη μεση συνεχιζει να υπαρχει λογω των τελειων,υπαρχουν δλδ και αλλοι αριθμοι.Οταν μετα βγαλεις το 14,θα ανεβει το 22,αρα εφοσον οι αριθμοι πριν ηταν μεταξυ 3-14 θα ειναι και μεταξυ 5-22

Α , οκ έτσι συμφωνώ απλά εγώ δεν τα είδα σαν διαστήματα , αλλά σαν κενά , γιατί δεν το αναφέρει η εκφώνηση , τεσπα , αα και μια μικρή διευκρίνιση αν μπορείς , γιατί δεν το βρίσκω πουθενά ... Στην αναζήτηση άλματος , αμα πείς έχουν άλμα 3 αυτό σημαίνει ότι από στοιχείο με δείκτη 0 , πηγαίνουμε σε στοιχείο με δείκτη 4 ή 3 ?

Αν μας δίνει συγκεκριμένους αριθμούς το δυαδικό δέντρο αναζήτησης που δημιουργείται είναι ένα και μοναδικό?

Μπορεί κανείς να μου εξηγήσει τι κάνουμε στο παρακάτω Β δέντρο, αν θέλουμε να διαγράψουμε το 409;

http://prntscr.com/ib1f0u (http://prntscr.com/ib1f0u)

Θα ανεβασεις το 377 πανω και το 345, θα κατεβει διπλα απο το 333.
Ομως τοτε θα εχεις 2 κλειδια, με 2 παιδια (αδυνατο, πρεπει να ειναι 2+1).
Ετσι για να κανεις τα 2 κλειδια 1, θα κατεβασεις το 377 διπλα απο το 345.
Τωρα εχεις αλλο προβλημα, εχεις κομβο με 1 κλειδι (Αδυνατο), ανεβαζεις το 299 πανω στο 210.
Ετσι, απο την μια μερια εχεις βαθος 3, απο την αλλη 2 (αδυνατο) , αρα ανεβαζεις  και το 21 112 πανω μαζι με  210 299

Χαμός :P
Ευχαριστώ πάντως κατάλαβα τι παίζει.

Αμα διαβασω θεωρια μετα απο java τι βαζουνε? Τι να διαβασω για να μπορω να γραψω κατι ?(δεν παω για βαθμαρα)

νομιζω πας στο 3

Παιδια μια βοηθεια για το θεμα 2β,δε ξερω πως λυνεται!!!!

Σε αυτο το παραδειγμα, γιατι το 72 παει στον μεσαιο κομβο?

Σε ποιο παραδειγμα;  :P

"Ποια είναι η συνάρτηση αποτυχίας του αλγορίθμου KMP για το [SALALAA];

α.[0012345]
β.[0001234]
γ.[0012341]
δ.[0012340]"

Εγώ δεν βγάζω κανένα από αυτά γιατί ουσιαστικά το P[0] (σύμφωνα με τις διαφάνειες) δεν είναι ποτέ ίσο με κανένα P. Μήπως έχει κανείς καμιά ιδέα;

Φεβρ 16 ομαδα Α θεμα 2β,εστω τη λογικη ρε παιδια!!!!!!!!!!!!

Και μένα έτσι μου φαίνεται...

Θα υποθεσω οτι επρεπε να ειναι LALALAA

Όπως το βλέπω εγώ: έχεις ένα δυαδικό δέντρο αναζήτησης στο οποίο προσθέτεις τιμές από την στοίβα και την ουρά.Πχ κοιτάς τις 4 πρώτες "εντολές" οπότε στην στοίβα έχεις (10,2) και (9,21) και στην ουρά λόγω του enqueue(pop()) έχεις την τιμή (10,2). Στην εντολή 4 κάνεις insert στο δυαδικό δέντρο την τιμή (16,21). Και κάπως έτσι συνεχίζει η άσκηση απλώς πρέπει να έχεις στο νου σου τι τιμές υπάρχουν στην στοίβα και στην ουρά και από που θα τις πάρεις (LIFO για τη στοίβα και FIFO για την ουρά)


Πιθανόν

Xxαχχαχαχα ξεχασα μια μικρη λεπτομέρεια

Δε θα μπορουσε να παει και αλλου,γενικα σε καθε εισαγωγη πρωτα βαζεις το κλειδι στο αντιστοιχο κομβο-φυλλο και μετα αν δε τηρηται καποια προϋποθεση κανεις τις αλλαγες που απαιτουνται

Στην εντολη add τι κανουμε?

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


Βάζεις ένα στοιχείο στην priority queue

Εκεί νομίζω παίζει ρόλο το δεύτερο νούμερο η προτεραιότητα δλδ

Νομιζω το καταλαβα,αλλα βγαζω αλλο δεντρο(βαζω μονο τα κλειδια)

16,8,26,4,9,19,46,0,0,0,0,0,20,38,0

Ακυρο το καταλαβα σιγουρα τωρα

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

το ιδιο εβγαλα με τη διαφορα οτι το 12 το εβαλα δεξι παιδι του 10

Αυτό δεν ξέρω με ποιο κριτήριο το επιλέγεις αλλά δεν νομίζω να παίζει ρόλο. Τώρα δεν ξέρω κατά πόσο είναι σωστό, αν μπορεί να μας πει κάποιος άλλος

Βασικα ειναι δυαδικο δεντρο αναζητησης,απο τη θεωρια τα στοιχεια αριστερα καθε κομβου πρεπει να ειναι μικροτερα του και τα δεξια μεγαλυτερα

Και πάλι όμως ικανοποιείται αυτό το κριτήριο

Αφου το 12 ειναι μικροτερο του 16 ρε  ;)

Και γω αυτό έβγαλα. Απλά ναι το 12 πρέπει να είναι στο αριστερό υποδέντρο, δεξιά του 10.

2016 ομάδα β θέμα 3 β έχει καταλάβει κανείς τι ζητάει στο 3βα ? και γενικα πως λύνεται?

και γω οποτε λογικα αυτη ειναι σωστη απαντηση

Για το 3βα, θα φτιάξεις έναν σωρό ελαχίστων με τα στοιχεία που δίνει, και ζητάει την τελική μορφή του σε μονοδιάστατο πίνακα. Αυτό σημαίνει βάζεις τα στοιχεία από το σωρό σε έναν πίνακα όπως τα διαβάζεις, από πάνω προς τα κάτω και από αριστερά προς τα δεξιά, ξεκινώντας από τη θέση 1 του πίνακα (όχι την 0).

Στο 3ββ σου λέει να τα εξάγεις ένα ένα από το σωρό ελαχίστων (νομίζω δε χρειάζεται να κάνεις αναλυτικά την εξαγωγή, απλά τα παίρνεις με αύξουσα σειρά), και με αυτή τη σειρά να τα εισάγεις στο σωρό. Το κάθε στοιχείο θα το εισάγεις στην πρώτη διαθέσιμη (πιο αριστερά) θέση του τελευταίου επιπέδου, και θα κάνεις τα απαραίτητα swaps με τους γονείς ώστε ο σωρός να είναι μεγίστων (δηλαδή αν το στοιχείο είναι μεγαλύτερο από το γονιό του θα τα κάνεις swap, και ελέγχεις το γονιό του γονιού, κοκ. μέχρι να φτάσεις στη ρίζα).

Δική μου ερώτηση: στο 3βα, τον σωρό θα τον φτιάξουμε "από κάτω προς τα πάνω", όπως δείχνει στη διαφάνεια ταξινόμησης σελ. 31, ή εισάγοντας ένα ένα τα στοιχεία, όπως στο 3ββ; Ή δεν έχει σημασία;

Δεν ισχύει γενικά ότι μπορούμε να φτιάξουμε πολλούς διαφορετικούς σωρούς ελαχίστων ή μεγίστων αντίστοιχα ? πχ εγώ έφτιαξα
ελαχίστων { 4, 21 , 41, 53, 66 ,68,55 , 83 , 97, 69 }  και μεγίστων { 97, 83 , 68 , 53 , 69 , 41 , 55 , 21 ,4 , 66 }

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

τελικα στο θεμα 3ββ,εισαγω τα στοιχεια με την σειρα που εχει  ο μονοδιαστατος πινακας η με αυξουσα σειρα(προκυπτει απο την διαγραφη στοιχειων του σωρου)?
Σε καθε περιπτωση μου βγαινει διαφορετικο αποτελεσμα απο αυτο που εχει λυσει το παιδι που εχει ανεβασει τα θεματα.

Τα εισάγεις με την σειρά που τα βγάζεις από τον σωρό ελαχίστων, δηλαδή σε αύξουσα σειρά.

Σε ευχαριστω

Στον κατακερματισμο με τετραγωνικη αναζητηση,το index παραμενει σταθερο και προστιθεται καθε φορα το νεο c*i^2?

οταν απο double hashing οδηγηθουμε σε τιμη μεγαλυτερη απο τη διασταση του πινακα γνωριζει καποιος τι γινεται? (π.χ. θεματα 2016 ομαδα Α θεμα2ο-Α-α)

Αν προκύπτει η θέση k και ο πίνακας χωράει n στοιχεία, τότε η νέα θέση είναι η k mod n.


Ναι, ουσιαστικά κοιτάς στις θέσεις index + c*1, index + c*4 κοκ

Update: Έμαθα πριν λίγο από φίλους μου που πήγαιναν στα μαθήματα ότι ο Χρυσόπουλος έκανε άσκηση που κάθε φορά πρόσθετε τον όρο c*i^2 στη προηγούμενη θέση. Για παράδειγμα αν η πρώτη hash function επιστρέψει τη θέση δύο και αυτή είναι κατειλλημένη, τότε θα κοιτάξουμε με τη σειρά τις θέσεις 2+1, 2+1+4, 2+1+9 κοκ (θεωρώ c=1)

και εγω ετσι το εβγαλα βλεποντας τον αλγοριθμο που δινει + οτι το ειδα ετσι και στις σημειωσεις απο downloads,αλλα βρηκα στο ιντερνετ οτι το σωστο ειναι κρατωντας σταθερο το index.....

Ακριβώς γιαυτό σου απάντησα έτσι την πρώτη φορά. Πάντως αύριο σκοπεύω να ακολουθήσω αυτό που έκανε στην τάξη.

Στις διαφάνειες δείχνει ότι κρατάει σταθερό το index. Αν μας δώσει τον αλγόριθμο θα κάνουμε αυτό που λέει και ας έρχεται σε αντιδιαστολή με τα αλλα. Γενικά έχω εντοπίσει αρκετά πράγματα που είτε δεν ταιριάζουν είτε δεν δουλεύουν στις διαφάνειες.

Για το θεμα με την quickshort και τα swaps, μετραμε swaps μονο για την πρώτη κλήση της partition η μέχρι να ταξινομηθεί πλήρως ο πίνακας;

Οταν λεμε <<1η κληση της partition>> εννουμε τον πρωτο διαμερισμο του πινακα?

Ναι

Μπορεί κάποιος να ανεβάσει τις ασκήσεις που έγιναν στο μάθημα από την αναζήτηση και μετά; ::)

Μηπως κάποιος θα μπορούσε να μου εξηγήσει με απλά λόγια πως καταλαμβαίνουμε ότι η χρονική πολυπολοκότητα ενος προγράμματος είναι λογαριθμική ? :D

Για αυτά που υπάρχουν στο μάθημα έχεις δύο περιπτώσεις:

• Η πρώτη είναι να θές να ψάξεις κάτι σε ένα AVL δέντρο ή σε παρόμοια δομή με βάθος logn. Τότε για να βρεις ένα στοιχείο, ή για να αποτύχει η αναζήτηση θες το πολύ logn ελέγχους καθώς τόσο είναι το βάθος και ψάχνεις πάντα από τη ρίζα προς τα φύλλα
• Η άλλη περίπτωση είναι όταν έχεις μια for της μορφής for(int i = 0; i < N; i*=2)  Εδώ στην ουσία διπλασσιάζει κάθε φορά το δείκτη σου. Αν πάρεις Ν = 256 θα δεις ότι χρειάζεσαι 8 επαναλήψεις για να βγεις από τη for, και log₂256 = 8.

Ελπίζω να σε κάλυψα  ::)

Ναι, ευχαριστώ πολύ!

Στις σημειώσεις του Χρυσόπουλου για την ταξινόμηση αναφέρει οτι στην ταξινόμηση φυσαλίδας ξεκινούμε απο το δεύτερο στοιχείο. Παρ'ολα αυτά όσα παραδείγματα βλέπω ξεκινούν απο το πρώτο στοιχείο. Τελικά τι απο τα δύο ισχυεί? ::)

Τα λέει λίγο περίεργα, στην ίδια διαφάνεια λέει το αντίθετο πράγμα:

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

Αν το ζευγάρι που ελέγχεις είναι το (j, j+1), θα ξεκινήσεις από το 0, αν είναι το (j-1, j) θα ξεκινήσεις από το 1.

Μπορείς να το σκεφτείς και ως εξής: αν ξεκινούσες από το δεύτερο στοιχείο και δεν έλεγχες το πρώτο, μπορεί το πρώτο να μην ήταν το ελάχιστο.

Off topic:
Μια περίπτωση όπου έχει νόημα να ξεκινήσεις από το 2ο είναι στο insertion sort, επειδή το 1ο στοιχείο όταν "εισάγεται" δεν μπορεί να πάει αριστερότερα, και αν υπάρχει κάποιο μικρότερό του θα μπει στη σωστή θέση όταν έρθει η σειρά του να "εισαχθεί".

Οντως ναί έτσι είναι όπως τα λές. Ευχαριστώ!

Οι λύσεις που υπαρχουν για τα θεματα του '11 νομιζω εχουν λαθη.
Στο θεμα 3.α) οταν μπαινει το στοιχειο [8,21] χρειαζεται ανακατανομη και περιστροφες γτ η ριζα απο αριστερα εχει βαθος 3 και απο δεξια βαθος 1, τελικα εγω βρηκα
[9,13  6,6  12,81  4,11  8,21  11,4  16,7  3,5] (το οποιο μπορει να ειναι και λαθος, αλλα νομιζω η ανεβασμενη λυση ειναι σιγουρα λαθος).

θυμαστε ποια ειχε πει ο χρυσοπουλος οτι ειναι η συμβαση για τα ονοματα κλασεων μεταβλητων πακετων συναρτησεων? κεφαλαια πεζα κλπ?

κανονικές μεταβλητές, συναρτήσεις, πακέτα: το πρώτο μικρό, camelCase
static final μεταβλητές: όλα κεφάλαια, ΚΑΤΩ_ΠΑΥΛΑ
κλάσεις: το πρώτο κεφαλαίο, CamelCase

τηνχχχχ  :D

Ξέρει κανείς την απάντηση του πρώτου ερωτήματος από τα θέματα Ιουνίου 2018 που είναι  ανεβασμένα στα downloads???

http://prntscr.com/kzho7w

μπορει να μου πει καποιος οταν διαγραφω το 409 γιατι να μην ανεβασω  το 377 και να κατεβασω κατω το 345 και να το κανω merge με το φυλλο κατω? (δλδ να εχω 301 303  345)

κατι τετοιο δλδ:
http://prntscr.com/kzhp9j

Γιατι ενας κομβος με k κλειδιά ( σε αυτην την περιπτωση ο (299 377) εχει 2 κλειδια) πρεπει να εχει k+1 παιδια ( δηλαδη οι 2 κομβοι (231 283) και (301 333 345) δεν φτανουν).