Διακριτά Μαθηματικά — Ιούνιος 2018¶
Μεταγραφή από το αρχείο exams_Jun_2018.pdf (κείμενο PDF).
exams_Jun_2018.pdf¶
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ ΠΟΛΥΤΕΧΝΙΚΗ ΣΧΟΛΗ ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΤΟΜΕΑΣ ΕΦΑΡΜΟΓΩΝ & ΘΕΜΕΛΙΩΣΕΩΝ ΤΗΣ ΕΠΙΣΤΗΜΗΣ ΤΩΝ ΥΠΟΛΟΓΙΣΤΩΝ¶
ΕΞΕΤΑΣΗ ΙΟΥΝΙΟΥ 2018¶
ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ Ι ΚΑΘΗΓΗΤΗΣ Χ. Ι. ΜΠΟΥΡΑΣ ΠΕΜΠΤΗ 7 ΙΟΥΝΙΟΥ 2018¶
ΘΕΜΑΤΑ¶
- Θέλουμε να στείλουμε ένα μήνυμα με 12 διαφορετικά σύμβολα πάνω από ένα τηλεπικοινωνιακό κανάλι. Επιπλέον των συμβόλων θέλουμε να στείλουμε και 45 κενά μεταξύ των συμβόλων, με τουλάχιστον 3 κενά μεταξύ διαφορετικών συμβόλων. Με πόσους διαφορετικούς τρόπους μπορούμε να μεταδώσουμε το μήνυμα;
ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε ΣΥΝΔΥΑΣΤΙΚΑ ΕΠΙΧΕΙΡΗΜΑΤΑ.
(35 μονάδες)
- Υπολογίστε τη γεννήτρια συνάρτηση της ακολουθίας: \(2, 7, 29, 133, \ldots, 2^n + 5^n, \ldots\) ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε ΓΕΝΝΗΤΡΙΕΣ ΣΥΝΑΡΤΗΣΕΙΣ.
(30 μονάδες)
- Με πόσους τρόπους μπορώ να χρωματίσω τις κορυφές ενός κύβου με 2 χρώματα; ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε το ΘΕΩΡΗΜΑ P´olya.
(35 μονάδες)
ΚΑΛΗ ΕΠΙΤΥΧΙΑ¶
Οι ενδεικτικές λύσεις και τα θέματα θα αναρτηθούν στο δικτυακό τόπο του μαθήματος, μετά το τέλος της εξέτασης.
Ενημερωθείτε για τα θέματα των Διπλωματικών Εργασιών για το 2017 − 18 στο http://ru6.cti.gr/ru6/bouras?language=el
Λύσεις (🟢 official)
Κατάσταση: 🟢 official Πηγή: ενδεικτικές λύσεις (αρχείο «solutions_Jun_2018.pdf» της συλλογής)
Λύσεις — Διακριτά Μαθηματικά — Ιούνιος 2018¶
solutions_Jun_2018.pdf¶
- Διαφορετικοί τρόποι για να μεταδώσω μόνο τα 12 διαφορετικά σύμβολα: \(12!\)
Για καθέναν από αυτούς τους τρόπους, σχηματίζονται 11 θέσεις μεταξύ των 12 συμβόλων, σε κάθε μία από τις οποίες πρέπει να βάλουμε τουλάχιστον 3 κενά: άρα χρησιμοποιούμε άλλους 33 από τους 45 κενούς χαρακτήρες. Μένουν 12 κενά.
12 κενά, που μένουν \(\Leftrightarrow\) 12 ίδια αντικείμενα, που θέλουμε να τοποθετήσουμε σε 11 διαφορετικά κουτιά \(\Leftrightarrow\) τις θέσεις, που είπαμε πριν. Αυτό μπορεί να γίνει με \(\binom{11+12-1}{12} = \binom{22}{12}\) διαφορετικούς τρόπους.
Επομένως, μπορούμε να μεταδώσουμε το μήνυμα με \(12! \cdot \binom{22}{12} = 3.097 \times 10^{14}\) διαφορετικούς τρόπους.
-
\(A(x) = 2^0 + 5^0 + (2^1 + 5^1)x + (2^2 + 5^2)x^2 + \ldots = (2^0 + 2x + 2^2x^2 + \ldots) + (5^0 + 5x + 5^2x^2 + \ldots) =\) $\([(2x)^0 + (2x)^1 + (2x)^2 + \ldots] + [(5x)^0 + (5x)^1 + (5x)^2 + \ldots] = \frac{1}{1-2x} + \frac{1}{1-5x} = \frac{1-5x+1-2x}{1-7x+10x^2} = \frac{2-7x}{1-7x+10x^2}\)$ $\(\cdot\, \frac{2+3x-6x^2}{1+2x} = -3x + 3 - \frac{1}{2x+1} = 3 - 3x - (1+2x)^{-1} = 3 - 3x - \sum_{k=0}^{\infty}\binom{-1}{k}2^k x^k =\)$ $\(= 3 - 3x - \sum_{k=0}^{\infty}(-1)^k 2^k x^k = 2 - x - 4x^2 + 8x^3 - 16x^4 + \ldots\)$
-
Θεωρούμε το σύνολο \(D\) των 8 κορυφών του κύβου, το σύνολο \(R = \{x, y\}\) των 2 χρωμάτων με \(w(x) = x\) και \(w(y) = y\). Αν \(G\) είναι η ομάδα μεταθέσεων, που αντιστοιχούν σε όλες τις δυνατές περιστροφές του κύβου, θα έχουμε \(|G| = 24\) μεταθέσεις, που είναι οι εξής:
- Η ταυτοτική μετάθεση με κυκλική αναπαράσταση \(x_1^8\).
- 3 μεταθέσεις που αντιστοιχούν σε περιστροφές \(180^\circ\) γύρω από άξονες που συνδέουν τα κέντρα απέναντι όψεων, με κυκλική αναπαράσταση \(x_2^4\).
- 6 μεταθέσεις που αντιστοιχούν σε περιστροφές \(90^\circ\) γύρω από άξονες που συνδέουν τα κέντρα απέναντι όψεων, με κυκλική αναπαράσταση \(x_4^2\).
- 6 μεταθέσεις που αντιστοιχούν σε περιστροφές γύρω από άξονες που ενώνουν τα μέσα απέναντι ακμών, με κυκλική αναπαράσταση \(x_2^4\).
- 8 μεταθέσεις που αντιστοιχούν σε περιστροφές \(120^\circ\) γύρω από άξονες που συνδέουν απέναντι κορυφές, με κυκλική αναπαράσταση \(x_1^2x_3^2\).
Συνεπώς, ο δείκτης κύκλων \(P_G\) της ομάδας \(G\) είναι: $\(P_G = \frac{1}{24}\left(x_1^8 + 9x_2^4 + 6x_4^2 + 8x_1^2x_3^2\right)\)$ και ο αριθμός εύρεσης σχηματισμών: $\(\frac{1}{24}\left[(x+y)^8 + 9(x^2+y^2)^4 + 6(x^4+y^4)^2 + 8(x+y)^2(x^3+y^3)^2\right]\)$
Θέτουμε \(x = y = 1\) και υπολογίζουμε τον αριθμό των διαφορετικών σχηματισμών $\(\frac{1}{24}\left(2^8 + 9 \cdot 2^4 + 6 \cdot 2^2 + 8 \cdot 2^2 \cdot 2^2\right) = 23\)$ που είναι ο ζητούμενος αριθμός.