Page 1 of 1

Αλγόριθμοι

Posted: Sat Apr 20, 2019 2:39 pm
by leecher
Το παρόν thread προορίζεται για το μάθημα "Αλγόριθμοι". Εδώ μπορείτε να συζητάτε για ό,τι σχετίζεται με το συγκεκριμένο μάθημα. Υπενθυμίζουμε ότι με βάση τους κανονισμούς λειτουργίας του forum απαγορεύονται τα greeklish, double posts και τα κεφαλαία. Για προηγούμενες συζητήσεις μπορείτε να ανατρέξετε εδώ.

Καλή αρχή! :D

Re: Αλγόριθμοι

Posted: Mon Jun 03, 2019 2:40 pm
by kwnstantinos.nikoloutsos
Σε περίπτωση που δεν μπορέσουμε να βγάλουμε τα θέματα φωτο οριστε τι μπήκε στο περίπου:

1 θεμα)
divide and conquer
Σας δίνεται ενα array ταξινομημενο σε αυξουσα σειρα
και ενα στοιχειο και πρεπει να βρειτε ποσες φορες εμφανιζεται αυτο στο array
α) Να δειξεται οτι μπορει να γίνει σε Ο(n)
b) Να εξηγησετε πως γινεται να το κανουμε σε O(logn), περιγραψτε τον αλγοριθμο
c) Να γραψετε την αναδρομικη του εξισωση και να λυσετε με master theorem

2 θέμα)
Άπληστος αλγόριθμος
Έχουμε πολλα μαθήματα που ξεκινανε απο καποιον χρονο και τελειώνουν σε καποιο χρόνο. Απο ολα αυτα θα πρέπει να επιλέξουμε οσο τον δυνατόν περισσότερα μπορούμε σε ενα χρονικο διάστημα χωρις να εχουμε Overlap. (Τα μαθήματα δίνονται αταξινομιτα)
α)Τι επιλογή πρεπει να κανει ο αλγοριθμος αυτος;;
β)Αποδείξτε οτι ειναι βέλτιστος
γ)Ποιά ειναι η πολυπλοκότητα του αλγορίθμου αυτού

3 θέμα)
Δυναμικός προγραμματισμος και άπληστος
0/1 knapsack
Γιατι ο greedy δινει λαθος λύση;;
α)Σε ποιο κελί θα πάρουμε την απάντηση οτι με αυτα τα αντικέιμενα μπορουμε να χωρέσουμε ακριβώς W;;
β)Να κάνετε αναπαράσταση ενός παραδείγματος που έδινε
γ)Τι πολυπλοκότητα εχει ο αλγόριθμος αυτος του δυναμικου;;

4 θέμα)
Γράφοι
α)Πως μπορούμε να βρούμε κύκλο με το DFS. και πως να βρουμε το συντομότερο μονοπατι με BFS.
β)Να βρείτε τι μονοπάτι θα έδινε ο dijkstra πανω σε εναν συγκεκριμένο γράφο.
γ)Μας έδινε εναν γραφο και ελεγε να βρούμε το minimum spanning tree.
δ)Πως μπορούμε να βρουμε τον μικρότερο κύκλο ενος γράφου να πειτε πολυπλοκότητα.

5 θεμα)
NP-complete, NP. P
α) Δείξτε οτι το Subset-sum ανηκει στην κλαση NP
β) Αν το ντετερμινιστικοποιήσουμε το Subset-sum γιατι πάιρνει εκθετικο χρόνο;, αιτιολογία...
γ) Τι σημαίνει για την δυσκολία του Α οτι το Β(το οποιο ειναι np-complete) αναγεται στο A
δ) Δείξτε οτι η κλίκα ανηκει στο np-complete.