Αλγόριθμοι

Τα posts που έγιναν κατά την διάρκεια του Ακαδημαϊκού Έτους 2018-2019 για τα προπτυχιακά μαθήματα.
Locked
User avatar
leecher
Administrator
Posts: 140
Joined: Fri Jan 23, 2015 9:47 pm
Academic status: N>4
Gender:

Αλγόριθμοι

Post by leecher » Sat Apr 20, 2019 2:39 pm

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

Καλή αρχή! :D
User avatar
kwnstantinos.nikoloutsos
bit level
bit level
Posts: 18
Joined: Wed Sep 27, 2017 9:08 pm
Academic status: 1st year
Gender:

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

Post by kwnstantinos.nikoloutsos » Mon Jun 03, 2019 2:40 pm

Σε περίπτωση που δεν μπορέσουμε να βγάλουμε τα θέματα φωτο οριστε τι μπήκε στο περίπου:

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.
Once the professional was a beginner!
Locked

Return to “Ακαδημαϊκό Έτος 2018-2019”