Εξέταση επιστήμης υπολογιστών αριθμός 5 πώς να λύσετε. Για την κωδικοποίηση των γραμμάτων αποφασίσαμε να χρησιμοποιήσουμε μια δυαδική αναπαράσταση

Κατάλογος εργασιών.
Μεταφορά πληροφοριών. Επιλογή κωδικού

Ταξινόμηση Βασική Πρώτη απλή Πρώτη σύνθετη Δημοτικότητα Πρώτη νέα Πρώτη παλιά
Κάντε τεστ σε αυτές τις εργασίες
Επιστροφή στον κατάλογο εργασιών
Έκδοση για εκτύπωση και αντιγραφή σε MS Word

Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα K, L, M, N, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα που ικανοποιεί τη συνθήκη Fano. Για το γράμμα Η χρησιμοποιήσαμε την κωδική λέξη 0, για το γράμμα Κ χρησιμοποιήσαμε την κωδική λέξη 10. Ποιο είναι το μικρότερο δυνατό συνολικό μήκος και των τεσσάρων κωδικών λέξεων;

Σημείωση.

Λύση.

Ας βρούμε τις συντομότερες παραστάσεις για όλα τα γράμματα. Οι κωδικές λέξεις 01 και 00 δεν μπορούν να χρησιμοποιηθούν, αφού τότε παραβιάζεται η συνθήκη Fano. Για παράδειγμα, χρησιμοποιούμε την κωδική λέξη 11 για το γράμμα L. Στη συνέχεια για το τέταρτο γράμμα είναι αδύνατο να επιλέξετε μια κωδική λέξη χωρίς να παραβιαστεί η συνθήκη Fano. Επομένως, για τα υπόλοιπα δύο γράμματα, πρέπει να χρησιμοποιηθούν τριψήφιες κωδικές λέξεις. Ας κωδικοποιήσουμε τα γράμματα L και M με κωδικές λέξεις 110 και 111. Τότε το συνολικό μήκος και των τεσσάρων κωδικών λέξεων είναι 1 + 2 + 3 + 3 = 9.

Απάντηση: 9.

Απάντηση: 9

Για την κωδικοποίηση μιας συγκεκριμένης ακολουθίας που αποτελείται από τα γράμματα A, B, C, D και D, χρησιμοποιείται ένας μη ομοιόμορφος δυαδικός κώδικας, ο οποίος καθιστά δυνατή την αναμφισβήτητη αποκωδικοποίηση της προκύπτουσας δυαδικής ακολουθίας. Εδώ είναι ο κωδικός: A - 1; Β - 0100; Β - 000; G - 011; D - 0101. Απαιτείται η μείωση του μήκους της κωδικής λέξης για ένα από τα γράμματα, έτσι ώστε ο κωδικός να μπορεί να αποκωδικοποιηθεί με σαφήνεια. Οι κωδικοί των υπόλοιπων γραμμάτων δεν πρέπει να αλλάξουν. Ποια από τις παρακάτω μεθόδους μπορεί να γίνει αυτό;

1) για το γράμμα G - 11

2) για το γράμμα B - 00

3) για το γράμμα G - 01

4) Αυτό είναι αδύνατο

Λύση.

Για ξεκάθαρη αποκωδικοποίηση, η κωδική λέξη που προκύπτει δεν πρέπει να είναι η αρχή οποιασδήποτε άλλης. Η πρώτη επιλογή απάντησης δεν είναι κατάλληλη, καθώς ο κωδικός για το γράμμα Α είναι η αρχή του κωδικού για το γράμμα G. Η δεύτερη επιλογή απάντησης είναι κατάλληλη. Η τρίτη επιλογή απάντησης δεν είναι κατάλληλη, γιατί στην περίπτωση αυτή ο κωδικός για το γράμμα G είναι η αρχή του κωδικού για το γράμμα D.

Η σωστή απάντηση αναφέρεται στον αριθμό: 2.

Απάντηση: 2

Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα I, K, L, M, N, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα που ικανοποιεί τη συνθήκη Fano. Για το γράμμα Η χρησιμοποιήσαμε την κωδική λέξη 0, για το γράμμα Κ χρησιμοποιήσαμε την κωδική λέξη 10. Ποιο είναι το μικρότερο δυνατό συνολικό μήκος και των πέντε κωδικών λέξεων;

Σημείωση. Η συνθήκη Fano σημαίνει ότι καμία κωδική λέξη δεν είναι η αρχή μιας άλλης κωδικής λέξης. Αυτό καθιστά δυνατή την ξεκάθαρη αποκρυπτογράφηση κρυπτογραφημένων μηνυμάτων.

Λύση.

Δεν μπορούμε να χρησιμοποιήσουμε κωδικές λέξεις που ξεκινούν με 0 ή 10. Δεν μπορούμε επίσης να χρησιμοποιήσουμε 11, γιατί τότε δεν θα μπορούμε πλέον να λαμβάνουμε καμία άλλη κωδική λέξη και χρειαζόμαστε πέντε από αυτές. Επομένως, παίρνουμε το τριψήφιο 110. Και πάλι, δεν μπορούμε να χρησιμοποιήσουμε το 111, γιατί θα χρειαστούμε μια ακόμη κωδική λέξη και ταυτόχρονα δεν θα μείνουν άλλες δωρεάν. Τώρα μένει να πάρουμε μόνο δύο λέξεις και αυτές θα είναι 1110 και 1111. Συνολικά έχουμε 0, 10, 110, 1110 και 1111 - 14 χαρακτήρες.

Απάντηση: 14.

Απάντηση: 14

Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα I, K, L, M, N, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα που ικανοποιεί τη συνθήκη Fano. Για το γράμμα L χρησιμοποιήσαμε την κωδική λέξη 1, για το γράμμα Μ χρησιμοποιήσαμε την κωδική λέξη 01. Ποιο είναι το μικρότερο δυνατό συνολικό μήκος και των πέντε κωδικών λέξεων;

Σημείωση.Η συνθήκη Fano σημαίνει ότι καμία κωδική λέξη δεν είναι η αρχή μιας άλλης κωδικής λέξης. Αυτό καθιστά δυνατή την ξεκάθαρη αποκρυπτογράφηση κρυπτογραφημένων μηνυμάτων.

Λύση.

Συνθήκη Fano - καμία κωδική λέξη δεν μπορεί να είναι η αρχή μιας άλλης κωδικής λέξης. Εφόσον υπάρχει ήδη μια κωδική λέξη 1, τότε καμία άλλη δεν μπορεί να ξεκινήσει με 1. Μόνο με 0. Επίσης δεν μπορεί να ξεκινήσει με 01, αφού έχουμε ήδη 01. Δηλαδή, οποιαδήποτε νέα κωδική λέξη θα ξεκινά με 00. Αλλά αυτό δεν μπορεί να είναι 00, γιατί διαφορετικά δεν μπορούμε να πάρουμε άλλες κωδικές λέξεις, αφού όλες οι μεγαλύτερες λέξεις ξεκινούν είτε με 1, 00 είτε με 01. Μπορούμε να πάρουμε είτε 000 είτε 001. Αλλά όχι και τα δύο ταυτόχρονα, γιατί και σε αυτήν την περίπτωση, δεν θα μπορούμε πλέον να παίρνουμε οποιονδήποτε νέο κωδικό. Έπειτα ας πάρουμε το 001. Και αφού μας απομένουν μόνο δύο κωδικοί, μπορούμε να πάρουμε τους 0000 και 0001. Συνολικά έχουμε: 1, 01, 001, 0000, 0001. Συνολικά 14 χαρακτήρες.

Για να δείτε την παρουσίαση με εικόνες, σχέδιο και διαφάνειες, κατεβάστε το αρχείο του και ανοίξτε το στο PowerPointστον υπολογιστή σου.
Περιεχόμενο κειμένου των διαφανειών παρουσίασης: Προετοιμασία για την Ενιαία Κρατική Εξέταση Καθηγητής Πληροφορικής MBOU Γυμνάσιο Νο. 1, Azova Balamutova Irina Aleksandrovna 2015 Κωδικοποίηση και αποκωδικοποίηση πληροφοριών. (Εργασίες 5) Κωδικοποίηση δεδομένων, συνδυαστική, αριθμητικά συστήματα (Εργασίες 10) Περιεχόμενα του θέματος «Κωδικοποίηση και αποκωδικοποίηση πληροφοριών TheoryTask 1Task 2Task 3Task for trainingΘέμα: Κωδικοποίηση δεδομένων, συνδυαστική, συστήματα αριθμώνTheoryTask forumsTask 1Task 1. ΙΣΤΟΣΕΛΙΔΕΣ EFUL ΓΙΑ ΠΡΟΕΤΟΙΜΑΣΙΕΣ ΓΙΑ ΧΡΗΣΗ2 αποκωδικοποιείται από την αρχή εάν ικανοποιείται η συνθήκη Fano: καμία κωδική λέξη δεν είναι η αρχή μιας άλλης κωδικοποιημένης λέξης, ένα κωδικοποιημένο μήνυμα μπορεί να αποκωδικοποιηθεί ξεκάθαρα από το τέλος εάν ικανοποιείται η αντίστροφη συνθήκη Fano: καμία κωδική λέξη δεν είναι η τέλος μιας άλλης κωδικής λέξης η συνθήκη Fano είναι επαρκής, αλλά όχι απαραίτητη προϋπόθεση για τη σαφή θεωρία αποκωδικοποίησης3 Η κωδικοποίηση είναι η μετάφραση πληροφοριών από τη μια γλώσσα στην άλλη. Η κωδικοποίηση μπορεί να είναι ομοιόμορφη ή ανομοιόμορφη, όλα τα σύμβολα κωδικοποιούνται με κώδικες ίσου μήκους, με διαφορετικούς χαρακτήρες 16 γράμματα Α, 8 γράμματα Β, 4 γράμματα Γ και 4 γράμματα G (δεν υπάρχουν άλλα γράμματα στα μηνύματα). Κάθε γράμμα κωδικοποιείται ως δυαδική ακολουθία. Κατά την επιλογή ενός κωδικού, λήφθηκαν υπόψη δύο απαιτήσεις: α) η μια κωδική λέξη δεν είναι η αρχή μιας άλλης (αυτό είναι απαραίτητο για να επιτρέπει ο κώδικας ξεκάθαρη αποκωδικοποίηση). β) το συνολικό μήκος του κωδικοποιημένου μηνύματος πρέπει να είναι όσο το δυνατόν μικρότερο. D: 1112) A: 0, B:10, C:01, D:113) A:1, B:01, C:011, D:0014) A:00, B:01, C:10, D: 11Εργασία 15, επιλέξτε πρώτα τους κωδικούς, στους οποίους ούτε μία κωδική λέξη δεν συμπίπτει με την αρχή μιας άλλης (ονομάζω τέτοιους κωδικούς πρόθεμα για τον κωδικό 2, η συνθήκη "a" δεν ικανοποιείται, καθώς η κωδική λέξη του γράμματος Β (01) αρχίζει με την κωδική λέξη του γράμματος Α (0) για τον κωδικό 3, η συνθήκη «a» δεν πληρούται, αφού η κωδική λέξη του γράμματος Β (011) αρχίζει με την κωδική λέξη του γράμματος Β (). 01) για τους κωδικούς 1 και 4 η συνθήκη πληρούται, τους εξετάζουμε περαιτέρω, υπολογίζουμε τον συνολικό αριθμό των bit στο μήνυμα για τον κωδικό 1: 16∙1 + 8 2 + 4∙3 + 4∙3 = 56 bit συνολικός αριθμός bit στο μήνυμα για τον κωδικό 4: 16∙2 + 8 2 + 4∙2 + 4∙2 = 64 bit Ο κωδικός 1 δίνει το μικρότερο μήκος μηνύματος, επομένως επιλέξτε τοΑπάντηση: 1.6 Λύση Πρόβλημα 1 Για να κωδικοποιήσετε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα A, B, C, D, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα που ικανοποιεί τη συνθήκη Fano. Για το γράμμα Α χρησιμοποιήσαμε την κωδική λέξη 0, για το γράμμα Β χρησιμοποιήσαμε την κωδική λέξη 110. Ποιο είναι το μικρότερο δυνατό συνολικό μήκος και των τεσσάρων κωδικών λέξεων 1) 7 2) 8 3) 9 4) 107 Πρόβλημα 2 Λύση (μέθοδος 1); , εξαλείφοντας τις επιλογές): Η συνθήκη Fano σημαίνει ότι καμία κωδική λέξη δεν είναι ίδια με την αρχή μιας άλλης κωδικής λέξης, αφού υπάρχει ήδη μια κωδική λέξη 0, καμία άλλη κωδική λέξη δεν μπορεί να ξεκινά με 0, καθώς υπάρχει κωδικός 110, οι κωδικές λέξεις 1, 11 απαγορεύονται ; Επιπλέον, καμία άλλη κωδική λέξη δεν μπορεί να ξεκινά με 110, επομένως πρέπει να επιλέξετε δύο ακόμη κωδικές λέξεις για τις οποίες πληρούνται αυτοί οι περιορισμοί Υπάρχει μία έγκυρη κωδική λέξη με δύο χαρακτήρες: 10 εάν επιλέξετε την κωδική λέξη 10 για το γράμμα Β, τότε υπάρχει μία. αριστερά η επιτρεπόμενη κωδική λέξη τριών χαρακτήρων είναι 111, η οποία μπορεί να επιλεγεί για το γράμμα G8 Λύση στο πρόβλημα 2. Επιλέγοντας κωδικές λέξεις A – 0, B – 110, C – 10, D – 111, παίρνουμε το συνολικό μήκος. από τις κωδικές λέξεις 9 χαρακτήρες Εάν δεν επιλέξετε B – 10, δηλαδή τρεις έγκυρες κωδικές λέξεις: 100, 101 και 110. Όταν επιλέγουμε οποιαδήποτε δύο από αυτά για τα γράμματα B και G, παίρνουμε το συνολικό μήκος των κωδικών λέξεων 10, που είναι περισσότερο από 9. Επομένως, επιλέγουμε την επιλογή 3 (9 χαρακτήρες) Απάντηση: 3. Λύση στο πρόβλημα 2 (συνέχεια) 9 AB10100 Λύση (μέθοδος 2, κατασκευή δέντρου): Η συνθήκη του Fano σημαίνει ότι ούτε μια κωδική λέξη δεν συμπίπτει με την αρχή μιας άλλης κωδικής λέξης. Ταυτόχρονα, στο δέντρο κώδικα, όλες οι κωδικές λέξεις πρέπει να βρίσκονται στα φύλλα του δέντρου που δεν έχουν απογόνους, ας δημιουργήσουμε ένα δέντρο για τις δεδομένες κωδικές λέξεις A - 0 και B - 110:10 Εργασία 2, διακεκομμένες γραμμές. σημειώστε δύο «κενά» κλαδιά στα οποία μπορούν να «κολληθούν» φύλλα για κωδικές λέξεις των γραμμάτων B (10) και G (111)AB10100VG, έχοντας επιλέξει τις κωδικές λέξεις A – 0, B – 110, C – 10, D – 111, λαμβάνουμε το συνολικό μήκος των κωδικών λέξεων 9 χαρακτήρες Απάντηση: 3. Πρόβλημα 2 Μέθοδος 2, η κατασκευή δέντρου συνεχίζεται 11 Μηνύματα που περιέχουν μόνο 4 γράμματα P, O, S, T μεταδίδονται μέσω του καναλιού επικοινωνίας. Για τη μετάδοση, χρησιμοποιείται ένας δυαδικός κώδικας που επιτρέπει τη σαφή αποκωδικοποίηση. Για τα γράμματα T, O, P χρησιμοποιούνται οι ακόλουθες κωδικές λέξεις: T: 111, O: 0, P: 100. Καθορίστε τη συντομότερη κωδική λέξη για το γράμμα C, στην οποία ο κωδικός θα επιτρέπει σαφή αποκωδικοποίηση. Εάν υπάρχουν πολλοί τέτοιοι κωδικοί, υποδείξτε τον κωδικό με τη χαμηλότερη αριθμητική τιμή. 12Εργασία 3 OT101000P1Λύση (μέθοδος 2, κατασκευή δέντρου): Η συνθήκη του Fano σημαίνει ότι ούτε μια κωδική λέξη δεν συμπίπτει με την αρχή μιας άλλης κωδικής λέξης. Ταυτόχρονα, στο δέντρο κώδικα, όλες οι κωδικές λέξεις πρέπει να βρίσκονται στα φύλλα του δέντρου, δηλαδή σε κόμβους που δεν έχουν απογόνους, ας δημιουργήσουμε ένα δέντρο για τις δοσμένες κωδικές λέξεις O - 0, T - 111 και P - 100: 13 Λύση του προβλήματος 3 Οι διακεκομμένες γραμμές σημειώνουν δύο "κενούς" κλάδους στους οποίους μπορείτε να "επισυνάψετε" ένα φύλλο για την κωδική λέξη του γράμματος C: 101 ή 110. από αυτές, η ελάχιστη τιμή είναι ο κωδικός 101 Λύση του προβλήματος 3 (συνέχεια) 14 15 Οι διακεκομμένες γραμμές επισημαίνουν δύο "κενούς" κλάδους στους οποίους μπορείτε να "επισυνάψετε" ένα φύλλο για την κωδική λέξη του γράμματος C: 101 ή 110. από αυτά, η ελάχιστη τιμή είναι ο κωδικός 101. OT101000P1S Έχοντας επιλέξει κωδικές λέξεις A – 0, B – 110, C – 10, D – 111, λαμβάνουμε το συνολικό μήκος των κωδικών λέξεων 9 χαρακτήρες Απάντηση: 101. Λύση στο πρόβλημα 3 (συνέχεια) 15 Μια ασπρόμαυρη εικόνα ράστερ είναι κωδικοποιημένη γραμμή προς γραμμή, ξεκινώντας από την επάνω αριστερή γωνία και καταλήγοντας στην κάτω δεξιά γωνία. Κατά την κωδικοποίηση, το 1 αντιπροσωπεύει το μαύρο και το 0 το λευκό. BD9AA5 2) BDA9B5 3) BDA9D5 4)DB9DAB 16Εργασία 4 «επεκτείνετε» την εικόνα ράστερ σε μια αλυσίδα: πρώτα η πρώτη (επάνω) γραμμή, μετά η δεύτερη κ.λπ.: υπάρχουν 24 κελιά σε αυτή τη λωρίδα, γεμίστε τα μαύρα με ένα και συμπληρώστε τα λευκά με μηδενικά: αφού κάθε ψηφίο στο δεκαεξαδικό σύστημα αποσυντίθεται σε 4 ακριβώς δυαδικά ψηφία, θα διαιρέσουμε τη λωρίδα σε τετράδια - ομάδες τεσσάρων κελιών (σε αυτή την περίπτωση, δεν έχει σημασία πού να ξεκινήστε τη διαίρεση, αφού υπάρχει ένας ακέραιος αριθμός τετραδίων στη λωρίδα - 6): μετατρέποντας τα τετράδια στο δεκαεξαδικό σύστημα , παίρνουμε διαδοχικά τους αριθμούς B (11), D (13), A (10), 9, D (13) και 5, δηλαδή η αλυσίδα BDA9D5, άρα η σωστή απάντηση είναι 3.17 Λύση στο πρόβλημα 4 1 γραμμή 2 γραμμή 3 γραμμή 4 γραμμή 1011110110101001110101011 γραμμή 2 γραμμή 3 γραμμή 4 γραμμή 1011110101 101010101 ) Εργασία 5 Νο. 7746. Για την κωδικοποίηση μιας συγκεκριμένης ακολουθίας που αποτελείται από τα γράμματα A, B, C, D και D, χρησιμοποιείται ένας μη ομοιόμορφος δυαδικός κώδικας, ο οποίος καθιστά δυνατή την αναμφισβήτητη αποκωδικοποίηση της προκύπτουσας δυαδικής ακολουθίας. Εδώ είναι ο κωδικός: A - 1; Β - 0100; Β - 000; G - 011; D - 0101. Απαιτείται η μείωση του μήκους της κωδικής λέξης για ένα από τα γράμματα, έτσι ώστε ο κωδικός να μπορεί να αποκωδικοποιηθεί με σαφήνεια. Οι κωδικοί των υπόλοιπων γραμμάτων δεν πρέπει να αλλάξουν. Ποια από τις παρακάτω μεθόδους μπορεί να γίνει αυτό; 1) για το γράμμα G - 112) για το γράμμα B - 003) για το γράμμα G - 014) αυτό είναι αδύνατο Απάντηση: 19 προβλήματα για ανεξάρτητη λύση2
Εργασία 5 Νο. 1104. Για να κωδικοποιήσουμε τα γράμματα X, E, L, O, D, αποφασίσαμε να χρησιμοποιήσουμε τη δυαδική αναπαράσταση των αριθμών 0, 1, 2, 3 και 4, αντίστοιχα (με τη διατήρηση ενός ασήμαντου μηδενός σε περίπτωση μονοψήφιας παράστασης). Εάν κωδικοποιήσετε την ακολουθία των γραμμάτων ICE DRIVE με αυτόν τον τρόπο και γράψετε το αποτέλεσμα σε δεκαεξαδικό κωδικό, θα λάβετε 1) 999С2) 32541453) 123F 4) 2143034 Απάντηση: 20 απαντήσεις Εργασία 5 Αρ. 1104 HELOD001 Πρώτα πρέπει να παρουσιάσετε τα δεδομένα στην αριθμητική συνθήκη στον δυαδικό κώδικα: κωδικοποιήστε την ακολουθία των γραμμάτων: OD - 1001100110011100 Τώρα ας χωρίσουμε αυτήν την αναπαράσταση σε τέσσερα από τα δεξιά προς τα αριστερά και ας μετατρέψουμε το σύνολο αριθμών που προκύπτει πρώτα σε δεκαδικό κωδικό και μετά σε δεκαεξαδικό. 1001 1001 1001 1100 - 9 9 9 12 - 999C Η σωστή απάντηση υποδεικνύεται στον αριθμό 1.21 Εργασία 5 No. μήκος) χρησιμοποιείται κωδικός: A – 0; Β – 100; Ε – 101. Ποια κωδική λέξη θα πρέπει να χρησιμοποιηθεί για την κωδικοποίηση του συμβόλου G έτσι ώστε το μήκος του να είναι ελάχιστο και ο κώδικας να επιτρέπει μια ξεκάθαρη διαίρεση του κωδικοποιημένου μηνύματος σε σύμβολα; 1) 12) 113) 01 Λύση 4) 010 http://inf.reshuege.ru/test?theme=232 Απάντηση:222
Εργασία 5 Αρ. 9293.23 Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα I, K, L, M, N, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα που ικανοποιεί τη συνθήκη Fano. Για το γράμμα L χρησιμοποιήσαμε την κωδική λέξη 1, για το γράμμα M χρησιμοποιήσαμε την κωδική λέξη 01. Ποιο είναι το μικρότερο δυνατό συνολικό μήκος και των πέντε κωδικών λέξεων; Η συνθήκη Fano σημαίνει ότι καμία κωδική λέξη δεν είναι η αρχή μιας άλλης κωδικής λέξης. Αυτό καθιστά δυνατή την ξεκάθαρη αποκρυπτογράφηση κρυπτογραφημένων μηνυμάτων Απάντηση: 4 Λύση http://inf.reshuege.ru/test?theme=23123.
24Εργασίες για εκπαίδευση βίντεο σύνδεσμος μαθήματοςhttps://www.youtube.com/watch?v=BoBnzjwLsnU Θέμα: Κωδικοποίηση δεδομένων, συνδυαστική, αριθμητικά συστήματα (Εργασίες 10) 25 Τι πρέπει να γνωρίζετε: Αρχές ρωσικού αλφάβητου εργασίας με αριθμούς γραμμένους σε θέση συστήματα αριθμών εάν η λέξη αποτελείται από γράμματα L και υπάρχουν n1 επιλογές για την επιλογή του πρώτου γράμματος, n2 επιλογές για την επιλογή του δεύτερου γράμματος κ.λπ., τότε ο αριθμός των πιθανών λέξεων υπολογίζεται ως το γινόμενο N = n1 · n2 · … · nL εάν η λέξη αποτελείται από γράμματα L και κάθε γράμμα μπορεί να επιλέγεται με n τρόπους, τότε ο αριθμός των πιθανών λέξεων υπολογίζεται ως N = nL26 θεωρία Ο Vasya συνθέτει λέξεις 5 γραμμάτων που περιέχουν μόνο τα γράμματα S, L, O , N και το γράμμα S χρησιμοποιείται ακριβώς 1 φορά σε κάθε λέξη. Κάθε ένα από τα άλλα έγκυρα γράμματα μπορεί να εμφανίζεται σε μια λέξη πολλές φορές ή καθόλου. Μια λέξη είναι οποιαδήποτε έγκυρη ακολουθία γραμμάτων, που δεν έχει απαραίτητα νόημα. Πόσες λέξεις υπάρχουν που μπορεί να γράψει η Vasya;27Εργασία 1 Το γράμμα C μπορεί να εμφανιστεί σε ένα από τα πέντε σημεία: С****, *С***, **С**, ***С* και *** * C, όπου * δηλώνει οποιονδήποτε από τους υπόλοιπους τρεις χαρακτήρες σε κάθε περίπτωση στις υπόλοιπες τέσσερις θέσεις μπορεί να υπάρχει οποιοδήποτε από τα τρία γράμματα L, O, N, επομένως, με μια δεδομένη διάταξη του γράμματος C έχουμε 34 = 81 επιλογές , συνολικά 5 · 81 = 405 επιλογές Απάντηση: 405.28Λύση Πόσες διαφορετικές ακολουθίες χαρακτήρων μήκους 5 υπάρχουν σε ένα αλφάβητο τεσσάρων γραμμάτων (A, C, G, T), οι οποίες περιέχουν ακριβώς δύο γράμματα A;29Πρόβλημα 2. Λύση (επιλογή 1, αναζήτηση): εξετάστε διαφορετικές εκδοχές λέξεων με 5 γράμματα που περιέχουν δύο γράμματα A και ξεκινούν με A:AA*** A*A** A**A* A***ΑΕΕδώ ο αστερίσκος υποδηλώνει οποιονδήποτε χαρακτήρα από το σύνολο (C, G, T), δηλαδή έναν από τους τρεις χαρακτήρες. Άρα, σε κάθε πρότυπο υπάρχουν 3 θέσεις, καθεμία από τις οποίες μπορεί να συμπληρωθεί με τρεις τρόπους, άρα ο συνολικός αριθμός συνδυασμών (για κάθε πρότυπο!) είναι 33 = 27 συνολικά 4 πρότυπα, δίνουν 4 27 = 108 συνδυασμούς30λύση Τώρα εμείς εξετάστε τα πρότυπα όπου το πρώτο που μετράει, το γράμμα Α βρίσκεται στη δεύτερη θέση, υπάρχουν μόνο τρία από αυτά: *AA** *A*A* *A**Δίνουν 3 · 27 = 81 συνδυασμούς δύο μοτίβων, όπου το πρώτο γράμμα Α βρίσκεται στην τρίτη θέση: **ΑΑ* **Α*Και δίνουν 2 · 27 = 54 συνδυασμούς και ένα σχέδιο, όπου ο συνδυασμός ΑΑ είναι στο τέλος ***ΑΑ δίνουν 27 συνδυασμούς, συνολικά παίρνουμε (4 + 3 + 2 + 1) · 27 = 270 συνδυασμοί Απάντηση: 270 .Λύση (συνέχεια)31 Όλες οι τετραγράμματες λέξεις που αποτελούνται από τα γράμματα Κ, Λ, Ρ, Τ γράφονται με αλφαβητική σειρά και αριθμούνται. Εδώ είναι η αρχή της λίστας: KKKK2. ΚΚΚΛ3. KKKR4. ΚΚΚΤ......Γράψε τη λέξη που βρίσκεται στην 67η θέση από την αρχή της λίστας. 32Εργασία 3 Η απλούστερη λύση σε αυτό το πρόβλημα είναι η χρήση συστημάτων αριθμών. Πράγματι, εδώ η διάταξη των λέξεων σε αλφαβητική σειρά είναι ισοδύναμη με τη διάταξη σε αύξουσα σειρά αριθμών που είναι γραμμένοι στο τεταρτοταγές σύστημα αριθμών (η βάση του αριθμητικού συστήματος είναι ίση με τον αριθμό των γραμμάτων που χρησιμοποιήθηκαν). 0, L1, P2, T3; δεδομένου ότι η αρίθμηση των λέξεων ξεκινά με ένα και ο πρώτος αριθμός КККК0000 είναι 0, ο αριθμός 67 θα είναι ο αριθμός 66, ο οποίος πρέπει να μετατραπεί στο τεταρτοταγές σύστημα: 66 = 10024 Έχοντας κάνει την αντίστροφη αντικατάσταση (των αριθμών με γράμματα ), παίρνουμε τη λέξη ΛΚΚΡ Απάντηση: ΛΚΚΡ .33Λύση 34Εργασία 10 Αρ. 6777. Πόσες λέξεις μήκους 5 μπορούν να γίνουν από τα γράμματα Ε, Ζ, Ε; Κάθε γράμμα μπορεί να εμφανιστεί σε μια λέξη πολλές φορές. 35 Λύση Εάν υπάρχουν M χαρακτήρες στο αλφάβητο, τότε ο αριθμός όλων των πιθανών «λέξεων» (μηνυμάτων) μήκους N είναι ίσος με Q = MN. Στην περίπτωσή μας, N = 5, M = 3. Επομένως, Q = 35 = 243. Απάντηση: 243. 36Εργασία 5 Εργασία 10 Αρ. 4797. Υπάρχουν 32 μολύβια σε ένα κλειστό κουτί, μερικά από αυτά είναι μπλε. Ένα μολύβι βγαίνει τυχαία. Το μήνυμα "αυτό το μολύβι ΔΕΝ είναι μπλε" φέρει 4 bits πληροφοριών. Πόσα μπλε μολύβια υπάρχουν στο κουτί; 37 Ο τύπος του Shannon: όπου x είναι η ποσότητα πληροφοριών στο μήνυμα για το συμβάν P, το p είναι η πιθανότητα του γεγονότος P. η πιθανότητα ότι δεν έχουν μπλε χρώμα όπου είναι ο αριθμός των μπλε μολυβιών Χρησιμοποιώντας τον τύπο του Shannon, βρίσκουμε ότι Y = 30 Λύση 38 Εργασίες για εκπαίδευση αυτοπροετοιμασίας σύνδεσμος εκπαιδευτικού βίντεο https://www.youtube.com/watch?v=BoBnzjwLsnU ΑΝΑΦΟΡΕΣhttp://kpolyakov.narod.ru/ Krylov S.S., Churkina T.E. Ενιαία Κρατική Εξέταση 2015. Πληροφορική και ΤΠΕ. Τυπικές επιλογές εξετάσεων. - Μ.: «Εθνική Παιδεία», 2015. Leshchiner V.R. Ενιαία Κρατική Εξέταση 2015. Πληροφορική. Τυπικές δοκιμαστικές εργασίες. - Μ.: Εξέταση, 2015. Evich L.N., Kulabukhov S.Yu. Πληροφορική και ΤΠΕ. Προετοιμασία για την Ενιαία Κρατική Εξέταση 2015. - Rostov-on-Don: Legion, 2014. Ushakov D.M., Yakushkin P.A. Επιστήμη των υπολογιστών. Η πιο πλήρης έκδοση των τυπικών εκδόσεων των εργασιών Unified State Examination 2014 - M.: Astrel, 2014. Evich L.N., Kulabukhov S.Yu. Πληροφορική και ΤΠΕ. Προετοιμασία για την Ενιαία Κρατική Εξέταση 2015. - Rostov-on-Don: Legion, 2014. Ostrovskaya E.M., Samylkina N.N. Ενιαία Κρατική Εξέταση 2015. Πληροφορική. Ενοικιάζουμε χωρίς κανένα πρόβλημα! - Μ.: Eksmo, 2014. Samylkina N.N., Ostrovskaya E.M. Ενιαία Κρατική Εξέταση 2015. Πληροφορική. Θεματικές εργασίες εκπαίδευσης. - Μ.: Eksmo, 2014. Zorina E.M., Zorin M.V. Ενιαία Κρατική Εξέταση 2015. Πληροφορική. Συλλογή εργασιών. - M.: “Eksmo”, 2015.39 Χρήσιμοι ιστότοποι για την ΠΡΟΕΤΟΙΜΑΣΙΑ ΓΙΑ την Ενιαία Κρατική Εξέταση!40 Η επιστήμη των υπολογιστών είναι εύκολη http://easyinformatics.ru/Ανάλυση βίντεο της εργασίας Unified State Exam-2013 http://www.ageychev. rf/ege.htmlΕκπαιδευτική πύλη για την προετοιμασία για εξετάσεις http://inf.reshuege.ru/?redir=1ΧΡΗΣΗ στην επιστήμη των υπολογιστών 2013 http://infoegehelp.ru/40

Ανάλυση της εργασίας 5 της Ενιαίας Κρατικής Εξέτασης 2016 στην επιστήμη των υπολογιστών από την έκδοση επίδειξης. Αυτή είναι μια εργασία σχετικά με την ικανότητα κωδικοποίησης και αποκωδικοποίησης πληροφοριών (για να είναι δυνατή η ερμηνεία των αποτελεσμάτων που λαμβάνονται κατά τη μοντελοποίηση πραγματικών διεργασιών). Αυτή είναι μια εργασία βασικού επιπέδου δυσκολίας. Ο κατά προσέγγιση χρόνος για την ολοκλήρωση της εργασίας είναι 2 λεπτά.

Εργασία 5:

Μηνύματα που περιέχουν μόνο τέσσερα γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: P, O, S, T. Για τη μετάδοση, χρησιμοποιείται ένας δυαδικός κώδικας που επιτρέπει τη σαφή αποκωδικοποίηση. Για τα γράμματα T, O, P χρησιμοποιούνται οι ακόλουθες κωδικές λέξεις: T: 111, O: 0, P: 100.
Καθορίστε τη συντομότερη κωδική λέξη για το γράμμα C, στην οποία ο κωδικός θα επιτρέπει σαφή αποκωδικοποίηση. Εάν υπάρχουν πολλοί τέτοιοι κωδικοί, υποδείξτε τον κωδικό με τη χαμηλότερη αριθμητική τιμή.

Απάντηση: ________

Ανάλυση της εργασίας 5 της Ενιαίας Κρατικής Εξέτασης 2016:

Για να λύσετε αυτό το πρόβλημα πρέπει να γνωρίζετε την συνθήκη Fano.

Κατάσταση Fano:
Ένα κωδικοποιημένο μήνυμα μπορεί να αποκωδικοποιηθεί ξεκάθαρα εάν καμία κωδική λέξη δεν είναι το τέλος μιας άλλης κωδικής λέξης.

Αντίστροφη συνθήκη Fano:
Ένα κωδικοποιημένο μήνυμα μπορεί να αποκωδικοποιηθεί αναμφίβολα από το τέλος, εάν καμία κωδική λέξη δεν είναι το τέλος άλλης κωδικής λέξης.

Ας αρχίσουμε τον έλεγχο με τη σειρά:

0 - δεν μπορεί να είναι, αφού O-0 (επίσης, η κωδική λέξη δεν μπορεί να ξεκινά με 0, αφού η συνθήκη Fano δεν θα ικανοποιηθεί),

1 - δεν μπορεί να είναι, αφού τα T-111 και P-100 ξεκινούν με ένα,

10 - δεν μπορεί να είναι, αφού το P-100 ξεκινά με 10,

11 - δεν μπορεί να είναι, αφού το T-111 ξεκινά από 11,

100 - δεν μπορεί να είναι, αφού P-100,

101 — ταιριάζει, εφόσον η συνθήκη Fano ικανοποιείται,

110 — ταιριάζει, αφού η συνθήκη Fano ικανοποιείται.

Σύμφωνα με τις συνθήκες του προβλήματος, εάν υπάρχουν πολλές λέξεις, πρέπει να επιλέξετε τον κωδικό με τη μικρότερη αριθμητική τιμή - έτσι επιλέγουμε 101 .

Για αποτελεσματική προετοιμασία στην επιστήμη των υπολογιστών, δίνεται σύντομο θεωρητικό υλικό για την ολοκλήρωση της εργασίας για κάθε εργασία. Έχουν επιλεγεί πάνω από 10 εκπαιδευτικές εργασίες με ανάλυση και απαντήσεις, που αναπτύχθηκαν με βάση την δοκιμαστική έκδοση των προηγούμενων ετών.

Δεν υπάρχουν αλλαγές στο Unified State Exam KIM 2020 στην επιστήμη των υπολογιστών και στις ΤΠΕ.

Τομείς στους οποίους θα ελεγχθούν οι γνώσεις:

• Προγραμματισμός;
• Αλγόριθμος;
• Εργαλεία ΤΠΕ.
• Δραστηριότητες ενημέρωσης;
• Πληροφοριακές διαδικασίες.

Απαραίτητες ενέργειες όταν παρασκευή:

• Επανάληψη του θεωρητικού μαθήματος.
• Λύση δοκιμέςστην επιστήμη των υπολογιστών Σε σύνδεση;
• Γνώση γλωσσών προγραμματισμού;
• Βελτίωση των μαθηματικών και της μαθηματικής λογικής.
• Η χρήση ενός ευρύτερου φάσματος λογοτεχνίας - το σχολικό πρόγραμμα σπουδών για επιτυχία στις Ενιαίες Κρατικές Εξετάσεις - δεν αρκεί.

Δομή εξετάσεων

Η διάρκεια της εξέτασης είναι 3 ώρες 55 λεπτά (255 λεπτά), εκ των οποίων η μιάμιση ώρα συνιστάται να αφιερωθεί για την ολοκλήρωση των εργασιών του πρώτου μέρους των KIM.

Οι εργασίες στα εισιτήρια χωρίζονται σε μπλοκ:

• Μέρος 1- 23 εργασίες με σύντομη απάντηση.
• Μέρος 2ο- 4 εργασίες με αναλυτικές απαντήσεις.

Από τις προτεινόμενες 23 εργασίες του πρώτου μέρους της εξεταστικής εργασίας, οι 12 ανήκουν στο βασικό επίπεδο ελέγχου γνώσεων, οι 10 - σε αυξημένη πολυπλοκότητα, 1 - σε υψηλό επίπεδο πολυπλοκότητας. Τρεις εργασίες του δεύτερου μέρους είναι υψηλού επιπέδου πολυπλοκότητας, το ένα είναι υψηλότερου επιπέδου.

Κατά τη λήψη μιας απόφασης, είναι απαραίτητο να καταγράψετε μια λεπτομερή απάντηση (δωρεάν φόρμα).
Σε ορισμένες εργασίες, το κείμενο της συνθήκης παρουσιάζεται σε πέντε γλώσσες προγραμματισμού ταυτόχρονα - για τη διευκόλυνση των μαθητών.

Βαθμοί για εργασίες επιστήμης υπολογιστών

1 βαθμός - για 1-23 εργασίες
2 βαθμοί - 25.
3 βαθμοί - 24, 26.
4 βαθμοί - 27.
Σύνολο: 35 βαθμοί.

Για να εισέλθετε σε ένα τεχνικό πανεπιστήμιο μεσαίου επιπέδου, πρέπει να συγκεντρώσετε τουλάχιστον 62 πόντους. Για την είσοδο στο πανεπιστήμιο της πρωτεύουσας, ο αριθμός των μορίων πρέπει να αντιστοιχεί σε 85-95.

Για να γράψετε με επιτυχία μια εξεταστική εργασία, μια σαφής γνώση του θεωρίακαι σταθερό πρακτική στην επίλυσηκαθήκοντα.

Η συνταγή σου για την επιτυχία

Εργασία + εργασία σε λάθη + διαβάστε προσεκτικά την ερώτηση από την αρχή μέχρι το τέλος για να αποφύγετε λάθη = μέγιστη βαθμολογία στην Ενιαία Κρατική Εξέταση στην επιστήμη των υπολογιστών.

Το μάθημα είναι αφιερωμένο στον τρόπο επίλυσης της εργασίας 5 της Ενιαίας Κρατικής Εξέτασης στην επιστήμη των υπολογιστών

Το 5ο θέμα χαρακτηρίζεται ως εργασίες βασικού επιπέδου πολυπλοκότητας, χρόνος ολοκλήρωσης - περίπου 2 λεπτά, μέγιστη βαθμολογία - 1

• Κωδικοποίηση- είναι η παρουσίαση πληροφοριών σε μορφή κατάλληλη για την αποθήκευση, μετάδοση και επεξεργασία τους. Ο κανόνας για τη μετατροπή πληροφοριών σε μια τέτοια αναπαράσταση ονομάζεται κώδικας.
• Η κωδικοποίηση γίνεται στολήΚαι άνισος:
• με ομοιόμορφη κωδικοποίηση, όλα τα σύμβολα αντιστοιχούν σε κωδικούς του ίδιου μήκους.
• Με ανομοιόμορφη κωδικοποίηση, διαφορετικά σύμβολα αντιστοιχούν σε κωδικούς διαφορετικού μήκους, γεγονός που καθιστά την αποκωδικοποίηση δύσκολη.

Παράδειγμα:Ας κρυπτογραφήσουμε τα γράμματα A, B, C, D χρησιμοποιώντας δυαδική κωδικοποίηση με ενιαίο κωδικό και μετράμε τον αριθμό των πιθανών μηνυμάτων:

Έτσι πήραμε ενιαίος κωδικός, επειδή το μήκος κάθε κωδικής λέξης είναι το ίδιο για όλους τους κωδικούς (2).

Κωδικοποίηση και αποκρυπτογράφηση μηνυμάτων

Αποκωδικοποίηση (αποκωδικοποίηση)- αυτή είναι η επαναφορά ενός μηνύματος από μια ακολουθία κωδικών.

Για να λύσετε προβλήματα με την αποκωδικοποίηση, πρέπει να γνωρίζετε την συνθήκη Fano:

Κατάσταση Fano:καμία κωδική λέξη δεν πρέπει να είναι η αρχή μιας άλλης κωδικής λέξης (που διασφαλίζει ότι τα μηνύματα αποκωδικοποιούνται ξεκάθαρα από την αρχή)

Κωδικός προθέματοςείναι ένας κώδικας στον οποίο καμία κωδική λέξη δεν συμπίπτει με την αρχή μιας άλλης κωδικής λέξης. Τα μηνύματα που χρησιμοποιούν αυτόν τον κωδικό αποκωδικοποιούνται χωρίς αμφιβολία.

Παρέχεται σαφής αποκωδικοποίηση:

Επίλυση 5 εργασιών Ενιαίας Κρατικής Εξέτασης

Ενιαία Κρατική Εξέταση 5.1:Για να κωδικοποιήσουμε τα γράμματα O, B, D, P, A, αποφασίσαμε να χρησιμοποιήσουμε τη δυαδική αναπαράσταση των αριθμών 0, 1, 2, 3 και 4, αντίστοιχα (με τη διατήρηση ενός ασήμαντου μηδενός στην περίπτωση ενός αναπαράσταση ψηφίων).

Κωδικοποιήστε την ακολουθία των γραμμάτων WATERFALL με αυτόν τον τρόπο και γράψτε το αποτέλεσμα σε οκταδικό κώδικα.

✍ Λύση:

• Ας μετατρέψουμε τους αριθμούς σε δυαδικούς κωδικούς και ας τους αντιστοιχίσουμε με τα γράμματά μας:

O -> 0 -> 00 V -> 1 -> 01 D -> 2 -> 10 P -> 3 -> 11 A -> 4 -> 100

Τώρα ας κωδικοποιήσουμε την ακολουθία των γραμμάτων από τη λέξη WATERFALL:

010010001110010

Ας χωρίσουμε το αποτέλεσμα σε ομάδες των τριών χαρακτήρων από δεξιά προς τα αριστερά για να τους μετατρέψουμε στο οκταδικό σύστημα αριθμών:

010 010 001 110 010 ↓ ↓ ↓ ↓ ↓ 2 2 1 6 2

Αποτέλεσμα: 22162

Λύση Unified State Exam για αυτήν την εργασία επιστήμης υπολογιστών, βίντεο:

Ας δούμε την ανάλυση της εργασίας 5 της Ενιαίας Κρατικής Εξέτασης:

Ενιαία Κρατική Εξέταση 5.2:Για 5 γράμματα του λατινικού αλφαβήτου, καθορίζονται οι δυαδικοί κωδικοί τους (για μερικά γράμματα - από δύο bit, για μερικά - από τρία). Αυτοί οι κωδικοί παρουσιάζονται στον πίνακα:

ένα	σι	ντο	ρε	μι
000	110	01	001	10

Ποιο σύνολο γραμμάτων κωδικοποιείται από τη δυαδική συμβολοσειρά 1100000100110;

✍ Λύση:

• Αρχικά, ελέγχουμε τη συνθήκη Fano: καμία κωδική λέξη δεν είναι η αρχή μιας άλλης κωδικής λέξης. Η συνθήκη είναι αληθής.

✎ 1η λύση:

• Σπάμε τον κωδικό από αριστερά προς τα δεξιά σύμφωνα με τα δεδομένα που παρουσιάζονται στον πίνακα. Τότε ας το μεταφράσουμε σε γράμματα:

110 000 01 001 10 ↓ ↓ ↓ ↓ ↓ β α γ δ ε

Αποτέλεσμα:β α γ δ ε.

✎ 2η λύση:

110 000 01 001 10

Αποτέλεσμα:β α γ δ ε.

Επιπλέον, μπορείτε να παρακολουθήσετε ένα βίντεο της λύσης αυτής της εργασίας Ενιαίας Πολιτικής Εξέτασης στην επιστήμη των υπολογιστών:

Ας λύσουμε την παρακάτω 5η εργασία:

Εξέταση Ενιαίας Πολιτείας 5.3:
Για τη μετάδοση αριθμών μέσω ενός θορυβώδους καναλιού, χρησιμοποιείται ένας κωδικός ελέγχου ισοτιμίας. Κάθε ψηφίο του γράφεται σε δυαδική αναπαράσταση, με μηδενικά που προστίθενται στο μήκος 4 και το άθροισμα των στοιχείων του modulo 2 προστίθεται στην ακολουθία που προκύπτει (για παράδειγμα, αν μεταδώσουμε το 23, παίρνουμε την ακολουθία 0010100110).

Προσδιορίστε τον αριθμό που μεταδόθηκε μέσω του καναλιού με τη μορφή 01100010100100100110.

✍ Λύση:

• Ας σκεφτούμε παράδειγμααπό τη δήλωση προβλήματος:

Ήταν 23 10 Τώρα 0010100110 2

Πού είναι τα ψηφία του αρχικού αριθμού (τονίστε τα με κόκκινο):

0010 10011 0 (0010 - 2, 0011 - 3)

Προστέθηκε το πρώτο ψηφίο 1 μετά το δυαδικό δύο είναι έλεγχος ισοτιμίας (1 μονάδα in 0010 - σημαίνει περίεργο) 0 μετά το δυαδικό τριπλό είναι επίσης ένας έλεγχος περιττής ισοτιμίας (2 in 0011 , που σημαίνει ακόμη).

Με βάση την ανάλυση του παραδείγματος, λύνουμε το πρόβλημά μας ως εξής: αφού οι αριθμοί που «χρειαζόμαστε» σχηματίζονται από ομάδες 4 αριθμών η καθεμία συν έναν αριθμό για έλεγχο ισοτιμίας, θα χωρίσουμε το κωδικοποιημένο μήνυμα σε ομάδες των 5 και θα απορρίψουμε ο τελευταίος χαρακτήρας από κάθε ομάδα:

χωρίστε το σε 5s:

01100 01010 01001 00110

απορρίψτε τον τελευταίο χαρακτήρα από κάθε ομάδα:

0110 0101 0100 0011

Αποτέλεσμαμετατροπή σε δεκαδικό σύστημα:

0110 0101 0100 0011 ↓ ↓ ↓ ↓ 6 5 4 3

Απάντηση: 6 5 4 3

Μπορείτε να παρακολουθήσετε ένα βίντεο της λύσης αυτής της εργασίας Ενιαίας Πολιτικής Εξέτασης στην επιστήμη των υπολογιστών:

Εξέταση Ενιαίας Πολιτείας 5.4:

Για να κωδικοποιήσουν μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα K, L, M, N, αποφάσισαν να χρησιμοποιήσουν έναν μη ομοιόμορφο δυαδικό κώδικα που ικανοποιεί τη συνθήκη Fano. Η κωδική λέξη 0 χρησιμοποιήθηκε για το γράμμα Η και η κωδική λέξη 10 για το γράμμα Κ.

Ποιο είναι το μικρότερο δυνατό συνολικό μήκος και των τεσσάρων κωδικών λέξεων;

✍ Λύση:

✎ 1 λύσημε βάση λογικά συμπεράσματα:

• Ας βρούμε τις συντομότερες δυνατές κωδικές λέξεις για όλα τα γράμματα.
• Κωδικές λέξεις 01 Και 00 δεν μπορεί να χρησιμοποιηθεί, αφού τότε η συνθήκη Fano παραβιάζεται (ξεκινούν από 0 και 0 - Αυτό Ν).
• Ας ξεκινήσουμε με διψήφιες κωδικές λέξεις. Ας πάρουμε το γράμμα μεγάλομια κωδική λέξη 11 . Τότε είναι αδύνατο να επιλέξετε μια κωδική λέξη για το τέταρτο γράμμα χωρίς να παραβιάσετε τη συνθήκη Fano (αν στη συνέχεια πάρετε 110 ή 111, τότε αρχίζουν με 11).
• Αυτό σημαίνει ότι πρέπει να χρησιμοποιούνται τριψήφιες κωδικές λέξεις. Ας κωδικοποιήσουμε τα γράμματα μεγάλοΚαι Μκωδικές λέξεις 110 Και 111 . Η συνθήκη Fano ικανοποιείται.

(Ν)1 + (Κ)2 + (L)3 + (Μ)3 = 9

✎ Επιλογή 2:

(N) -> 0 -> 1 χαρακτήρας (K) -> 10 -> 2 χαρακτήρες (L) -> 110 -> 3 χαρακτήρες (M) -> 111 -> 3 χαρακτήρες

Το συνολικό μήκος και των τεσσάρων κωδικών λέξεων είναι:

(Ν)1 + (Κ)2 + (L)3 + (Μ)3 = 9

Απάντηση: 9

5.5: Unified State Exam in Informatics 5 task 2017 FIPI option 2 (επιμέλεια Krylov S.S., Churkina T.E.):

Τα μηνύματα που περιέχουν μόνο 4 γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: A, B, C, D. Για τη μετάδοση, χρησιμοποιείται ένας δυαδικός κώδικας που επιτρέπει τη σαφή αποκωδικοποίηση. Για τα γράμματα Α Β ΓΧρησιμοποιούνται οι παρακάτω κωδικές λέξεις:

A: 101010, B: 011011, C: 01000

Καθορίστε τη συντομότερη κωδική λέξη για το γράμμα G, στην οποία ο κωδικός θα επιτρέπει σαφή αποκωδικοποίηση. το μικρότεροαριθμητική αξία.

✍ Λύση:

• Οι μικρότεροι κωδικοί θα μπορούσαν να μοιάζουν 0 Και 1 (μονοψήφιο). Αλλά αυτό δεν θα ικανοποιούσε τη συνθήκη Fano ( ΕΝΑξεκινά με ένα - 101010 , σιξεκινά από το μηδέν - 011011 ).
• Ο επόμενος μικρότερος κωδικός θα ήταν μια λέξη δύο γραμμάτων 00 . Εφόσον δεν είναι πρόθεμα καμίας από τις παρουσιαζόμενες κωδικές λέξεις, τότε G = 00.

Αποτέλεσμα: 00

5.6: Unified State Examination in Informatics 5 task 2017 FIPI option 16 (επιμέλεια Krylov S.S., Churkina T.E.):

Για να κωδικοποιήσουμε μια συγκεκριμένη ακολουθία που αποτελείται από τα γράμματα A, B, C, D και D, αποφασίσαμε να χρησιμοποιήσουμε έναν μη ομοιόμορφο δυαδικό κώδικα, ο οποίος μας επιτρέπει να αποκωδικοποιήσουμε ξεκάθαρα τη δυαδική ακολουθία που εμφανίζεται στην πλευρά λήψης του καναλιού επικοινωνίας. Κωδικός που χρησιμοποιείται:

A - 01 B - 00 C - 11 D - 100

Υποδείξτε με ποια κωδική λέξη πρέπει να κωδικοποιείται το γράμμα D. Μήκοςαυτή η κωδική λέξη πρέπει να είναι ελάχιστααπό όλα τα δυνατά. Ο κωδικός πρέπει να ικανοποιεί την ιδιότητα της ξεκάθαρης αποκωδικοποίησης. Εάν υπάρχουν πολλοί τέτοιοι κωδικοί, υποδείξτε τον κωδικό με τη χαμηλότερη αριθμητική τιμή.

✍ Λύση:

Αποτέλεσμα: 101

Μια πιο λεπτομερής ανάλυση του μαθήματος μπορείτε να δείτε στο βίντεο της Ενιαίας Κρατικής Εξέτασης στην Επιστήμη Υπολογιστών 2017:

5.7: Εργασία 5. Έκδοση επίδειξης του Unified State Exam 2018 Computer Science (FIPI):

Τα κρυπτογραφημένα μηνύματα που περιέχουν μόνο δέκα γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: A, B, E, I, K, L, R, S, T, U. Χρησιμοποιείται ένας ανομοιόμορφος δυαδικός κώδικας για μετάδοση. Οι κωδικές λέξεις χρησιμοποιούνται για εννέα γράμματα.

Τα κρυπτογραφημένα μηνύματα που περιέχουν μόνο τέσσερα γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: A, B, C, D. Για τη μετάδοση, χρησιμοποιείται ένας δυαδικός κώδικας που επιτρέπει τη σαφή αποκωδικοποίηση. Για τα γράμματα ΕΝΑ, σι, ΣΕχρησιμοποιημένες κωδικές λέξεις:

A: 00011 B: 111 C: 1010

Καθορίστε τη συντομότερη κωδική λέξη για το γράμμα σολ, στο οποίο ο κώδικας θα επιτρέπει τη σαφή αποκωδικοποίηση.Εάν υπάρχουν πολλοί τέτοιοι κωδικοί, υποδείξτε τον κωδικό με το μικρότεροαριθμητική αξία.

✍ Λύση:

Αποτέλεσμα: 00

5.9: Επιλογή προπόνησης Νο. 3 από 10/01/2018 (FIPI):

Τα μηνύματα που περιέχουν μόνο γράμματα μεταδίδονται μέσω του καναλιού επικοινωνίας: Α, Ε, Δ, Κ, Μ, Ρ; Για τη μετάδοση, χρησιμοποιείται ένας δυαδικός κώδικας που ικανοποιεί τη συνθήκη Fano. Οι ακόλουθοι κωδικοί είναι γνωστό ότι χρησιμοποιούνται:

E – 000 D – 10 K – 111

Καθορίστε το μικρότερο δυνατό μήκος κωδικοποιημένου μηνύματος DEDMAKAR.
Στην απάντησή σας, γράψτε έναν αριθμό - τον αριθμό των bit.

✍ Λύση:

D E D M A K A R 10.000 10.001 01.111 01.110

Ας μετρήσουμε τον αριθμό των ψηφίων στον τελικό κωδικό και πάρουμε 20 .

Αποτέλεσμα: 20

Δείτε τη λύση στην εργασία: