Venus AUEB Forum

Το παρόν thread προορίζεται για το μάθημα "Αλγόριθμοι". Εδώ μπορείτε να συζητάτε για ό,τι σχετίζεται με το συγκεκριμένο μάθημα. Υπενθυμίζουμε ότι με βάση τους κανονισμούς λειτουργίας του forum απαγορεύονται τα greeklish, double posts και τα κεφαλαία. Για προηγούμενες συζητήσεις μπορείτε να ανατρέξετε εδώ.

Καλή αρχή!

Το πρώτο φροντιστήριο Αλγορίθμων https://www.dropbox.com/s/n0dnvdxlndn59 ... 1.pdf?dl=0

Καλημέρα συνάδελφοι :D , είναι εύκολο σε κάποιον να ανεβάσει τα φροντιστήρια που έχουν γίνει μέχρι τώρα?

Καλησπέρα παιδιά!! Μιας και θέλει ηλεκτρονικά τις απαντήσεις, που προτείνετε να τις γράψουμε?

Word?

Εχει κανεις τα φροντιστηρια ?

Σε ποια αίθουσα είναι σήμερα η πρόοδος?

Α, Δ21-22-23

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

Ευχαριστω

Καλησπέρα! Ξέρουμε αν στην τελική εξέταση επιτρέπεται κόλλα Α4?

xoxo never!

Καλησπέρα παιδιά!! Παίζει να πει κάποιος τι πρέπει να ξέρουμε για να είμαστε οσο το δυνατόν καλύτερα προετοιμασμένοι?

Καλησπερα παιδια!!
Υπαρχει κανεις που να θυμαται το θεμα με ΔΒ που ειχε πεσει στα θεματα ιουνιου?

Τα σημερινά θέματα ήταν:
1) Έχουμε ένα πίνακα με n στοιχεία διατεταγμένα σε αύξουσα σειρά και θέλουμε αλγόριθμο που να επιστρέφει αν υπάρχει ή όχι κάποιο στοιχείο Α = i
α) Πως θα μπορούσαμε να το λύσουμε σε χρόνο Ο(n)
β) Αλγόριθμο Δ&Β που να το λύνει σε χρόνο Ο(logn)

2) Έχουμε n στοιχεία σε αύξουσα σειρά w1 < w2 < w3 < ... <wn (διαφορετικές δυνάμεις του 2) Και να βρούμε άπληστο αλγόριθμο που να μασ απαντά αν υπάρχει (και ποιο) υποσύνολο που μπορούμε να χρησιμοποιήσουμε για αναπαραστήσουμε ένα θετικό ακέραιο Μ.
α) Να ορίσουμε την απληστη ιδέα β) ψευδοκώδικα και πολυπλοκότητα γ) ορθότητα

3) Έστω ότι έχουμε ένα βάτραχο οποίος στέκεται σε ένα νούφαρο i και θέλει να φτάσει σε ένα νούφαρο n με διαδοχικά άλματα. Το πόσα νούφερα μπορεί να προσπεράσει εξαρτάτε από το νούφαρο στο οποίο στέκεται. Θεωρήστε ένα πίνακα jump[i..n] που περιέχει το μέγιστο αριθμό απο νούφαρα που μπορεί να προσπεράσει.
πχ αν βρίσκεται στο νούφαρο 1 και το νούφαρο 1 του επιτρέπει να κινηθεί +3 θέσεις max θα μπορεί να πάει μέχρι το νούφαρο i+ jump => 1 + 3 =4
α) να δείξουμε με ένα παράδειγμα γιατί η άπληστη ιδέα να πηδά κάθε φορά κατά max δεν λειτουργεί
β) να ορίσουμε αυστηρά το υποπρόβλμα μας σε δυναμικό προγραμματισμό
γ) να γράψουμε την αναδρομική σχέση
δ) αλγόριθμο και πολυπλοκότητα

4) Να δείξουμε με τη μέθοδο του DFS ότι σε ένα G= (V,E) γράφημα με θετικά βάρη εάν υπάρχει μονοπάτι που να χρησιμοποιεί μόνο ακμές μικρότερες ή ίσες από ένα θετικό ακέραιο Μ.

5) Να δείξουμε με ένα παράδειγμα αν ο αλγόριθμος του Dijkstra λειτουργεί ή όχι σε γράφο με αρνητικά βάρη στης ακμές

6) Να αποδείξουμε ότι το πρόβλημα του να βρεθεί αν υπάρχει αντιστροφος πίνακας nxn ανήκει στη κλάση NP. (Καθαρά θεωριτική απάντηση χωρίς αλγόριθμους και λοιπά)

Υπάρχει και άλλη μια άσκηση με αναγωγή αλλα δυστυχώς αυτή τη στιγμή μου διαφεύγει αν θύμάται κανείς ας συμπληρώσει το Post

Η αναγωγη ηταν στο περιπου: εχουμε καποιους αριθμους που μπορουμε να τους χωρισουμε σε 2 συνολα με ιδιο αθροισμα με το PARTITION, να κανουμε αναγωγη απο το (κατι) αθροισμα στο PARTITION

στο πολυ περιπου, δε το εγραψα

Εφτιαξα ενα PDF με τα θεματα του σεπτεμβριου οπως τα θυμομουν. Τωρα είδα οτι το είχε κανει και το αλλο παιδι :P
https://www.dropbox.com/s/30lhvcvpsgrik ... p.pdf?dl=0