Διακριτά Μαθηματικά — Φεβρουάριος 2019¶
Μεταγραφή από το αρχείο examsFeb2019.pdf (κείμενο PDF).
examsFeb2019.pdf¶
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ ΠΟΛΥΤΕΧΝΙΚΗ ΣΧΟΛΗ¶
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ¶
ΤΟΜΕΑΣ ΕΦΑΡΜΟΓΩΝ & ΘΕΜΕΛΙΩΣΕΩΝ ΤΗΣ ΕΠΙΣΤΗΜΗΣ ΤΩΝ ΥΠΟΛΟΓΙΣΤΩΝ
ΕΞΕΤΑΣΗ ΧΕΙΜΕΡΙΝΟΥ ΕΞΑΜΗΝΟΥ 2019
ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ ΚΑΘΗΓΗΤΗΣ Χ. Ι. ΜΠΟΥΡΑΣ¶
ΤΡΙΤΗ 5 ΦΕΒΡΟΥΑΡΙΟΥ 2019
ΘΕΜΑΤΑ¶
- Χρησιμοποιώντας ΣΧΕΣΕΙΣ ΑΝΑΔΡΟΜΗΣ, να λυθεί η \(T(n) = 2T\left(\frac{n}{2}\right) + n\), \(T(1)=1\).
( 2.5 ΜΟΝΑΔΕΣ )
- Χρησιμοποιώντας την ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ - ΑΠΟΚΛΕΙΣΜΟΥ, να υπολογίσετε πόσες τοποθετήσεις των ψηφίων \(0,1,2,\ldots,9\) υπάρχουν, στις οποίες το πρώτο ψηφίο να είναι μεγαλύτερο του 4 και το τελευταίο ψηφίο να είναι μικρότερο του 7.
( 2.5 ΜΟΝΑΔΕΣ )
- Έστω μία γλώσσα που αποτελείται από διακεκριμένα σύμβολα και το κενό σύμβολο. Έχουμε \(n\) θέσεις στην σειρά και θέλουμε να τοποθετήσουμε \(k\) σύμβολα για να δημιουργηθεί μία πρόταση με την προυπόθεση ότι πάντα αναμεσα από δύο σύμβολα θα περιέχονται τουλάχιστον δύο κενά. Θεωρείστε ότι δεν χρειάζεται πριν το πρώτο σύμβολο και μετά το τελευταίο να τοποθετηθούν κενά. Κάθε σύμβολο μπορεί να χρησιμοποιηθεί μόνο μία φορά, ενώ το κενό πρέπει να χρησιμοποιηθεί \(3k\) φορές. Με πόσους διαφορετικούς τρόπους μπορούμε να το κάνουμε;
( 2.5 ΜΟΝΑΔΕΣ )
- Χρησιμοποιώντας ΓΕΝΝΗΤΡΙΕΣ ΣΥΝΑΡΤΗΣΕΙΣ, υπολογίστε με πόσους τρόπους μπορούν να μοιραστούν τα 52 (διακεκριμένα) χαρτιά μιας τράπουλας σε 4 (διακεκριμένους) παίκτες, αν κάθε παίκτης πρέπει να πάρει τουλάχιστον ένα χαρτί.
( 2.5 ΜΟΝΑΔΕΣ )
ΚΑΛΗ ΕΠΙΤΥΧΙΑ¶
Οι ενδεικτικές λύσεις και τα θέματα θα αναρτηθούν στο δικτυακό τόπο του
μαθήματος, μετά το τέλος της εξέτασης.
Ενημερωθείτε για τα θέματα των Διπλωματικών Εργασιών για το 2018 – 19 στο http://ru6.cti.gr/ru6/bouras?language=el
Λύσεις (🟢 official)
Κατάσταση: 🟢 official Πηγή: ενδεικτικές λύσεις (αρχείο «solutionsFeb2019.pdf» της συλλογής)
Λύσεις — Διακριτά Μαθηματικά — Φεβρουάριος 2019¶
solutionsFeb2019.pdf¶
- Χρησιμοποιώντας ΣΧΕΣΕΙΣ ΑΝΑΔΡΟΜΗΣ, να λυθεί η \(T(n) = 2T\left(\frac{n}{2}\right) + n\), \(T(1) = 1\).
Ορίζουμε στην σχέση \(T(n) = 2T\left(\frac{n}{2}\right) + n\) ως σχέση (1) και θέτω όπου \(n\) το \(\frac{n}{2}\). Έτσι προκύπτει: $\(T(n) = 2T\left(\frac{n}{2}\right) + n = 2\left[2T\left(\frac{n}{2^2}\right) + \frac{n}{2}\right] + n = 2^2 T\left(\frac{n}{2^2}\right) + 2n.\)$
Ορίζω την παραπάνω σχέση ως σχέση (2).
Στην σχέση (1) θέτω όπου \(n\) το \(\frac{n}{2^2}\) για να πάρω το \(T\left(\frac{n}{2^2}\right)\), και στην συνέχεια το αντικαθιστώ στην σχέση (2). Δρώντας αντίστοιχα καταλήγω ότι η \(T(n)\) δίνεται από την σχέση: $\(T(n) = 2^i T\left(\frac{n}{2^i}\right) + in\)$
Αν θέσουμε όπου \(2^i\) το \(n\), έχουμε ότι \(T(n) = n + n\log n\).
- Χρησιμοποιώντας την ΑΡΧΗ ΕΓΚΛΕΙΣΜΟΥ - ΑΠΟΚΛΕΙΣΜΟΥ, να υπολογίσετε πόσες τοποθετήσεις των ψηφίων \(0,1,2,\ldots,9\) υπάρχουν, στις οποίες το πρώτο ψηφίο να είναι μεγαλύτερο του 4 και το τελευταίο ψηφίο να είναι μικρότερο του 7.
Έστω \(S\) το σύνολο όλων των πιθανών μεταθέσεων των στοιχείων \(0,1,2,\ldots,9\). Το πλήθος \(N\) των στοιχείων του \(S\) είναι \(10!\) (\(|S| = N = 10!\)). Ορίζουμε στο σύνολο μας τις παρακάτω ιδιότητες:
\(c_1\): Το πρώτο ψηφίο μιας μετάθεσης να είναι μικρότερο ή ίσο με το 4
\(c_2\): Το τελευταίο ψηφίο μιας μετάθεσης να είναι μεγαλύτερο ή ίσο με 7
Ο πληθικός αριθμός των συνόλων που ικανοποιούν τις παραπάνω ιδιότητες είναι: $\(N(c_1) = 5 \cdot 9!\)$ $\(N(c_2) = 3 \cdot 9!\)$
Αυτό που ζητάμε είναι η τιμή: $\(N(\overline{c_1}\,\overline{c_2}) = N - N(c_1) - N(c_2) + N(c_1c_2) = 10! - 5 \cdot 9! - 3 \cdot 9! + 15 \cdot 8!\)$
- Έστω μία γλώσσα που αποτελείται από διακεκριμένα σύμβολα και το κενό σύμβολο. Έχουμε \(n\) θέσεις στην σειρά και θέλουμε να τοποθετήσουμε \(k\) σύμβολα ώστε να δημιουργηθεί μία πρόταση με την προυπόθεση ότι πάντα ανάμεσα από δύο σύμβολα θα περιέχονται τουλάχιστον δύο κενά. Θεωρείστε ότι δεν χρειάζεται πριν το πρώτο σύμβολο και μετά το τελευταίο να τοποθετηθούν κενά. Κάθε σύμβολο μπορεί να χρησιμοποιηθεί μόνο μία φορά ενώ το κενό πρέπει να χρησιμοποιηθεί \(3k\) φορές. Με πόσους διαφορετικούς τρόπους μπορώ να το κάνω;
Θα χρησιμοποιηθεί στοιχειώδης συνδυαστική για την επίλυση του ερωτήματος. Από την εκφώνηση ορίζεται ότι τα σύμβολα είναι διακεκριμένα και μοναδικά, οπότε υπάρχουν \(k!\) τρόποι να τα διατάξω. Αφού τα διατάξω, ανάμεσα από κάθε σύμβολο τοποθετώ 2 κενά, οπότε χρησιμοποιώ \(2k - 2\) κενά καθώς ορίζονται \(k - 1\) υποδοχές. Σαν αποτέλεσμα μου απομένουν \(3k - (2k - 2)\) κενά, ή αλλιώς \(k + 2\) κενά τα οποία θα πρέπει να τοποθετήσω ανάμεσα από σύμβολα.
Τα κενά είναι ίδια οπότε, μοιράζω τα \(k + 2\) κενά σε \(k - 1\) υποδοχές με: $\(\binom{k - 1 + k + 2 - 1}{k + 2} = \binom{2k}{k + 2} \text{ τρόπους.}\)$
Άρα συνολικά υπάρχουν \(k! \cdot \binom{2k}{k+2}\) τρόποι.
- Χρησιμοποιώντας ΓΕΝΝΗΤΡΙΕΣ ΣΥΝΑΡΤΗΣΕΙΣ, υπολογίστε με πόσους τρόπους μπορούν να μοιραστούν τα 52 (διακεκριμένα) χαρτιά μιας τράπουλας σε 4 (διακεκριμένους) παίκτες, αν κάθε παίκτης πρέπει να πάρει τουλάχιστον ένα χαρτί.
Τα χαρτιά είναι διαφορετικά οπότε μας ενδιαφέρει η σειρά με την οποία μοιράζονται στους παίκτες καθώς επιβάλλει μία διάταξη στους παίκτες. Εφόσον τα χαρτιά που χρησιμοποιούνται είναι διαφορετικά και οι παίκτες διακεκριμένοι θα χρησιμοποιηθούν εκθετικές γεννήτριες συναρτήσεις.
Η ΕΓΣ για κάθε παίκτη είναι \(\frac{x^1}{1!} + \frac{x^2}{2!} + \ldots = e^x - 1\). Κάθε παράγοντας στο γινόμενο εκφράζει τη δυνατότητα μοιράσματος ενός, δύο ή περισσοτέρων χαρτιών σε κάθε παίκτη. Σύνολο έχουμε 4 παίκτες άρα και για τους 4 παίκτες, η ΕΓΣ είναι: \((e^x - 1)^4 = e^{4x} - 4e^{3x} + 6e^{2x} - 4e^x + 1\).
Επειδή τα χαρτιά είναι 52 και ο κάθε παίκτης θα πρέπει να πάρει τουλάχιστον 1 χαρτί και κανένας παίκτης δεν μπορεί να πάρει περισσότερα από 49 χαρτιά, θα έπρεπε να σταματήσουμε το παραπάνω άθροισμα στον όρο \(\frac{x^{49}}{49!}\). Τότε όμως το άθροισμα δεν θα ισούται με \(e^x - 1\). Επεκτείνοντας το άθροισμα στο άπειρο δεν επηρεάζει το αποτέλεσμα επειδή οι μεγαλύτερες δυνάμεις του \(x\) δεν επηρεάζουν το ζητούμενο συντελεστή. Η απάντηση στην ερώτηση δίνεται από το συντελεστή του όρου \(\frac{x^{52}}{52!}\), που είναι \(4^{52} - 4 \cdot 3^{52} + 6 \cdot 2^{52} - 4\).