Αλγόριθμοι

Τα υποχρεωτικά μαθήματα του 2ου έτους
User avatar
leecher
Administrator
Posts: 129
Joined: Fri Jan 23, 2015 9:47 pm
Academic status: N>4
Gender:

Αλγόριθμοι

Postby 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: Αλγόριθμοι

Postby 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!

Return to “2ο έτος”

Who is online

Users browsing this forum: No registered users and 1 guest