forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 20 Σεπ 2017, 07:47

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 2 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Ασκήσεις Αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 20 Ιαν 2011, 01:23 
Χωρίς σύνδεση
Regular Forumer

Εγγραφή: 09 Μαρ 2006, 14:43
Δημοσ.: 2767
Τοποθεσια: White Hart Lane
Ανοίγω ένα θεματάκι με ασκήσεις αλγορίθμων και όποιος θέλει postάρει ασκήσεις.

Ξεκινάω από μία που είχαμε να παραδώσουμε:

5.24.(Algorithms, by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani)
Ένας δυαδικός (binary) δείκτης, ακαθόριστου μεγέθους υποστηρίζει δύο λειτουργίες: increment (αυξάνει την τιμή του δείκτη κατά ένα) και reset (θέτει την τιμή του δείκτη να είναι μηδέν). Να δείξετε ότι, αν ο δείκτης ξεκινάει από την τιμή μηδέν, κάθε ακολουθία n λειτουργιών από τις increment και reset παίρνει χρόνο εκτέλεσης O(n) - δηλαδή ότι ο χρόνος απόσβεσης κάθε πράξης είναι O(1).

Διευκρίνηση: η αύξηση ενός αριθμού κατά ένα γίνεται στο δυαδικό σύστημα και κάθε bit που αλλάζει θεωρείται ως ένα (χρονικό) βήμα.

Ελεύθερη μετάφραση από αυτό:
Spoiler:
A binary counter of unspecfied length supports two operations: increment (which increases its
value by one) and reset (which sets its value back to zero). Show that, starting from an initially
zero counter, any sequence of n increment and reset operations takes time O(n); that is, the
amortized time per operation is O(1).

_________________
Lab Radio


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Ασκήσεις Αλγορίθμων
ΔημοσίευσηΔημοσιεύτηκε: 21 Φεβ 2011, 03:48 
Χωρίς σύνδεση
Regular Forumer

Εγγραφή: 09 Μαρ 2006, 14:43
Δημοσ.: 2767
Τοποθεσια: White Hart Lane
Μερικές ακόμα από το παραπάνω βιβλίο, από το ίδιο κεφάλαιο (κάνω και μια ελεύθερη μετάφραση σε περίπτωση που κάποιος έχει πρόβλημα):

5.5 Θεωρούμε ένα μη κατευθυνόμενο γράφημα G=(V,E) με μη αρνητικά βάρη w_e \geq  0. Θεωρούμε πως έχουμε υπολογίσει το minimum spanning tree* και ότι έχουμε υπολογίσει τα συντομότερα μονοπάτια προς όλες τις κορυφές για μια συγκεκριμένη κορυφή s\in V(G). Αν υποθέσουμε ότι το βάρος κάθε ακμής αυξάνεται κατά 1, δηλαδή τα νέα βάρη είναι w'_e = w_e + 1:

(a) Αλλάζει το minimum spanning tree; Δώστε ένα αντιπαράδειγμα ή αποδείξτε ότι δεν αλλάζει.

(b) Αλλάζουν τα συντομότερα μονοπάτια; Δώστε ένα αντιπαράδειγμα ή αποδείξτε ότι δεν αλλάζουν.

*Spanning tree είναι ένα υπογράφημα ενός γραφήματος που είναι δέντρο και περιέχει όλες τις κορυφές του. Minimum spanning tree είναι ένα spanning tree ελαχίστου βάρους.

Spoiler:
5.5. Consider an undirected graph G = (V,E) with nonnegative edge weights w_e \geq  0. Suppose that you have computed a minimum spanning tree of G, and that you have also computed shortest
paths to all nodes from a particular node s \in V(G). Now suppose each edge weight is increased by 1: the new weights are w'_e = w_e + 1.
(a) Does the minimum spanning tree change? Give an example where it changes or prove it
cannot change.
(b) Do the shortest paths change? Give an example where they change or prove they cannot
change.



5.20 Δώστε ένα αλγόριθμο γραμμικού χρόνου που δέχεται ως είσοδο ένα δέντρο και υπολογίζει αν έχει τέλειο ταίριασμα, δηλαδή ένα σύνολο ακμών που ακουμπάει κάθε κορυφή ακριβώς μία φορά.
Ένα σύνολο ακμών ανατροφοδότησης (feedback edge set) ενός μη κατευθυνόμενου γραφήματος είναι ένα υποσύνολο των ακμών του, E' \subseteq E, που τέμνει κάθε κύκλο του γραφήματος. Άρα αν αφαιρέσουμε τις ακμές του E' το γράφημα θα γίνει άκυκλο.
Δώστε έναν αποτελεσματικό (χρονικά) αλγόριθμο για το παρακάτω πρόβλημα:
Είσοδος: Μη κατευθυνόμενο γράφημα G=(V,E) με θετικά βάρη w_e στις ακμές του.
Έξοδος: Ένα σύνολο ακμών ανατροφοδότησης E' \subseteq E με ελάχιστο συνολικό βάρος \sum_{e\in E'} w_e.

Spoiler:
5.20. Give a linear-time algorithm that takes as input a tree and determines whether it has a perfect
matching: a set of edges that touches each node exactly once.
A feedback edge set of an undirected graph G = (V,E) is a subset of edges E' \subseteq E that intersects every cycle of the graph. Thus, removing the edges E' will render the graph acyclic.
Give an effcient algorithm for the following problem:
Input: Undirected graph G = (V,E) with positive edge weights w_e
Output: A feedback edge set E' \subseteq E of minimum total weight \sum_{e\in E'} w_e.



5.27 Η Αλίκη θέλει να κάνει ένα (αποκριάτικο) party και προσπαθεί να αποφασίσει ποιους να καλέσει. Έχει να διαλέξει από n ανθρώπους και έχει κάνει μια λίστα από ζευγάρια ανθρώπων που γνωρίζονται μεταξύ τους. Θέλει να διαλέξει όσα περισσότερα άτομα μπορεί με βάση δύο περιορισμούς: στο πάρτι, κάθε άτομο θα πρέπει να έχει τουλάχιστον πέντε άτομα που ξέρει και πέντε άτομα που δεν ξέρει. Δώστε έναν αποτελεσματικό αλγόριθμο που δέχεται ως είσοδο τη λίστα με τα n άτομα και τη λίστα από τα ζευγάρια που γνωρίζονται μεταξύ τους και επιστρέφει την καλύτερη επιλογή από καλεσμένους. Δώστε τον χρόνο εκτέλεσης του αλγορίθμου ως προς το n.


Spoiler:
5.27. Alice wants to throw a party and is deciding whom to call. She has n people to choose from, and
she has made up a list of which pairs of these people know each other. She wants to pick as many
people as possible, subject to two constraints: at the party, each person should have at least five
other people whom they know and five other people whom they don't know.
Give an effcient algorithm that takes as input the list of n people and the list of pairs who know
each other and outputs the best choice of party invitees. Give the running time in terms of n.

_________________
Lab Radio


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 2 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group