Γειά σου! Ονομάζομαι Alexander Georgievich και είμαι επαγγελματίας καθηγητής στη Μόσχα στην επιστήμη των υπολογιστών και στον προγραμματισμό. Έχετε συναντήσει κάποιο πρόβλημα που σχετίζεται με την κωδικοποίηση και έχετε μπερδευτεί σχετικά με τον αλγόριθμο για την επίλυσή του; Πρέπει επειγόντως να συναντηθείτεΚατάσταση Fanoκαι εγγραφείτε για ιδιαίτερα μαθήματα μαζί μου. Στα μαθήματά μου επικεντρώνομαι στην επίλυση θεματικών απλών και σύνθετων ασκήσεων.

Ποιο είναι το νόημα της άμεσης συνθήκης του Φάνου;

Κατάσταση Fanoπήρε το όνομά του από τον δημιουργό του, τον Ιταλοαμερικανό επιστήμονα Robert Fano. Η συνθήκη είναι απαραίτητη στη θεωρία κωδικοποίησης κατά την κατασκευή ενός αυτοτερματιζόμενου κώδικα. Δεδομένης της διαφορετικής ορολογίας, ένας τέτοιος κωδικός ονομάζεται κωδικός προθέματος.

Διατυπώ αυτή η συνθήκημπορεί να γίνει ως εξής: " κανένας μια κωδική λέξηδεν μπορεί να λειτουργήσει ως αρχή οποιασδήποτε άλλης κωδικής λέξης».

Από μαθηματική άποψη, η συνθήκη μπορεί να διατυπωθεί ως εξής: εάν ο κωδικός περιέχει τη λέξηB, μετά για οποιαδήποτε μη κενή συμβολοσειράΗ λέξη C BC δεν υπάρχει στον κώδικα».

Τι σημαίνει η αντίστροφη συνθήκη Fano;

Υπάρχει επίσης ένας αντίστροφος κανόνας Fano, η διατύπωση του οποίου είναι η εξής: καμία κωδική λέξη δεν μπορεί να λειτουργήσει ως το τέλος οποιασδήποτε άλλης κωδικής λέξης».

Από μαθηματική άποψη, η αντίστροφη συνθήκη μπορεί να διατυπωθεί ως εξής: εάν ο κωδικός περιέχει τη λέξη B, τότε για οποιαδήποτε μη κενή συμβολοσειρά C η λέξη CB δεν υπάρχει στον κωδικό».

Πρακτική εφαρμογή της συνθήκης Fano

Ας σκεφτούμε τηλεφωνικοί αριθμοί V παραδοσιακή τηλεφωνία. Εάν ο αριθμός "102" υπάρχει ήδη, τότε ο αριθμός "1029876" απλά δεν θα εκδοθεί. Εάν καλέσετε τα τρία πρώτα ψηφία, το PBX σταματά να αναγνωρίζει και να δέχεται όλα τα άλλα ψηφία, συνδέοντας τον συνδρομητή με τον αριθμό 102. Ωστόσο, αυτός ο κανόνας δεν ισχύει για τους χειριστές κινητές επικοινωνίες. Αυτό οφείλεται στο γεγονός ότι για να καλέσετε έναν αριθμό πρέπει να πατήσετε το αντίστοιχο πλήκτρο, το οποίο είναι κυρίως το πλήκτρο με την πράσινη εικόνα Ακουστικό. Για το λόγο αυτό, οι αριθμοί «102», «1020» και «1029876» μπορούν να υπάρχουν και να εκχωρηθούν σε διαφορετικούς παραλήπτες.

Το έργο:δίνεται μια ακολουθία που αποτελείται από τα γράμματα «Α», «Β», «Γ», «Δ» και «Ε». Για να κωδικοποιήσετε τη δεδομένη ακολουθία, μια ανομοιόμορφη δυάδικος κώδικας, με το οποίο μπορείτε να εφαρμόσετε ξεκάθαρη αποκωδικοποίηση.

Ερώτηση: Είναι δυνατόν ένα από τα σύμβολα να συντομεύσει το μήκος της κωδικής λέξης με τέτοιο τρόπο ώστε να διατηρηθεί η δυνατότητα ξεκάθαρης αποκωδικοποίησης; Σε αυτήν την περίπτωση, οι κωδικοί των υπολοίπων συμβόλων θα πρέπει να παραμείνουν αμετάβλητοι.

Λύση: για να διατηρηθεί η δυνατότητα αποκωδικοποίησης, αρκεί η συμμόρφωση με απευθείας ή αντίστροφηΣυνθήκες Fano. Ας πραγματοποιήσουμε έναν διαδοχικό έλεγχο των επιλογών 1, 3 και 4. Εάν καμία από τις επιλογές δεν είναι κατάλληλη, η σωστή απάντηση θα είναι η επιλογή 2 (δεν είναι δυνατή).

Επιλογή 1. Κωδικός: A - 00, B - 01, C - 011, D - 101 και E - 111. Απευθείας Κατάσταση Fanoδεν εκτελείται: ο κωδικός του χαρακτήρα "B" συμπίπτει με την αρχή του κωδικού του χαρακτήρα "C". Ο αντίστροφος κανόνας Fano δεν ισχύει: ο κωδικός του χαρακτήρα "B" συμπίπτει με το τέλος του κωδικού του χαρακτήρα "D". Η επιλογή δεν είναι κατάλληλη.

Επιλογή 3. Κωδικός: A - 00, B - 010, C - 01, D - 101, και E - 111. Απευθείας Κατάσταση Fanoδεν εκτελείται: ο κωδικός του χαρακτήρα "C" συμπίπτει με την αρχή του κωδικού του χαρακτήρα "B". Η αντίστροφη συνθήκη επίσης δεν ικανοποιείται: ο κωδικός του χαρακτήρα "C" συμπίπτει με το τέλος του κωδικού του χαρακτήρα "D". Η επιλογή δεν είναι κατάλληλη.

Επιλογή 4. Κωδικός: A - 00, B - 010, C - 011, D - 01 και E - 111. Απευθείας Κατάσταση Fanoδεν εκτελείται: ο κωδικός του χαρακτήρα "D" συμπίπτει με την αρχή του κωδικού των χαρακτήρων "B" και "C". Ωστόσο, τηρείται ο αντίστροφος κανόνας Fano: ο κωδικός του χαρακτήρα "D" δεν συμπίπτει με το τέλος του κωδικού όλων των άλλων χαρακτήρων. Για το λόγο αυτό, η επιλογή είναι κατάλληλη.

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

Απάντηση: 4

Και τώρα προτείνω να εξοικειωθείτε με τη λύση πολυμέσων στο πρόβλημα που προτάθηκε στην δοκιμαστική έκδοση του Unified State Exam στην επιστήμη των υπολογιστών και στις ΤΠΕ. Παρεμπιπτόντως, αυτή η εργασίααναφέρεται στο είδος των προβλημάτων που επιλύονται χρησιμοποιώντας Συνθήκες Fano.

Έχετε ακόμα ερωτήσεις;

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

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

Συνθήκη Fano (Αγγλική συνθήκη Fano, προς τιμήν του Robert Fano) - στη θεωρία κωδικοποίησης απαραίτητη προϋπόθεσηκατασκευή ενός αυτοτερματιζόμενου κώδικα (σε άλλη ορολογία, κωδικός προθέματος). Η συνήθης διατύπωση αυτής της συνθήκης μοιάζει με αυτό:

Καμία κωδική λέξη δεν μπορεί να είναι η αρχή μιας άλλης κωδικής λέξης.
Πιο «μαθηματική» διατύπωση:

Εάν ο κωδικός περιλαμβάνει τη λέξη a, τότε για οποιαδήποτε μη κενή συμβολοσειρά b η λέξη ab δεν υπάρχει στον κώδικα.

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

Βασικές πληροφορίες
Η κωδικοποίηση Shannon-Fano είναι ένας ετερογενής αλγόριθμος κωδικοποίησης προθέματος. Αναφέρεται σε πιθανοτικές μεθόδους συμπίεσης (ακριβέστερα, μεθόδους μοντελοποίησης πλαισίου μηδενικής τάξης). Όπως ο αλγόριθμος Huffman, ο αλγόριθμος Shannon-Fano χρησιμοποιεί πλεονασμό μηνυμάτων που περιέχεται στην ανομοιόμορφη κατανομή συχνοτήτων των συμβόλων του (πρωτεύοντος) αλφαβήτου του, δηλαδή αντικαθιστά κωδικούς με περισσότερους συχνοί χαρακτήρεςσύντομες δυαδικές ακολουθίες και κώδικες σπανιότερων χαρακτήρων - μεγαλύτερες δυαδικές ακολουθίες.

Ο αλγόριθμος αναπτύχθηκε ανεξάρτητα από τον Shannon (δημοσίευση " Μαθηματική θεωρίαεπικοινωνίες», 1948) και, αργότερα, ο Fano (δημοσιεύεται ως τεχνική έκθεση).

1. Βασικές έννοιες
Το να κωδικοποιήσεις ένα κείμενο σημαίνει να το συσχετίσεις με ένα άλλο κείμενο. Η κωδικοποίηση χρησιμοποιείται στη μετάδοση δεδομένων - προκειμένου να κρυπτογραφηθεί κείμενο από αγνώστους, να γίνει η μετάδοση δεδομένων πιο αξιόπιστη, επειδή το κανάλι δεδομένων μπορεί να μεταδώσει μόνο περιορισμένο σύνολοχαρακτήρες (για παράδειγμα - μόνο δύο χαρακτήρες, 0 και 1) και για άλλους λόγους.
Κατά την κωδικοποίηση, το αλφάβητο στο οποίο είναι γραμμένα τα κείμενα πηγής (πηγαίο αλφάβητο) και το αλφάβητο στο οποίο είναι γραμμένα τα κωδικοποιημένα κείμενα (κώδικες) προσδιορίζονται εκ των προτέρων αυτό το αλφάβητο ονομάζεται αλφάβητο κώδικα. Ένα δυαδικό αλφάβητο χρησιμοποιείται συχνά ως αλφάβητο κωδικών, που αποτελείται από δύο χαρακτήρες (bit) 0 και 1. Οι λέξεις στο δυαδικό αλφάβητο ονομάζονται μερικές φορές ακολουθίες bit.
2. Κωδικοποίηση γράμμα προς γράμμα
Η απλούστερη μέθοδος κωδικοποίησης είναι γράμμα προς γράμμα. Με την κωδικοποίηση γράμμα προς γράμμα, κάθε χαρακτήρας από το αρχικό αλφάβητο σχετίζεται με μια κωδική λέξη - μια λέξη στο αλφάβητο του κώδικα. Μερικές φορές αντί για «κωδικός γράμματος» λένε απλώς «κωδικός γράμματος». Κατά την κωδικοποίηση κειμένου γράμμα προς γράμμα, οι κωδικοί όλων των χαρακτήρων γράφονται σε μια σειρά, χωρίς οριοθέτες.
Παράδειγμα 1. Το αρχικό αλφάβητο είναι το αλφάβητο των ρωσικών γραμμάτων, πεζά και κεφαλαία γράμματαδεν διαφέρουν. Το μέγεθος του αλφαβήτου είναι 33 χαρακτήρες.
Κωδικό αλφάβητο - αλφάβητο δεκαδικά ψηφία. Το μέγεθος του αλφαβήτου είναι 10 χαρακτήρες.
Η κωδικοποίηση γράμμα προς γράμμα χρησιμοποιείται σύμφωνα με επόμενος κανόνας: ένα γράμμα κωδικοποιείται από τον αριθμό του στο αλφάβητο: ο κωδικός του γράμματος Α είναι 1. γράμματα I – 33, κ.λπ.
Τότε ο κωδικός για τη λέξη ABBA είναι 1221.
Προσοχή: Η ακολουθία 1221 μπορεί να σημαίνει όχι μόνο ABBA, αλλά και KU (το K είναι το 12ο γράμμα στο αλφάβητο και το U είναι το 21ο γράμμα). Λένε για τέτοιο κωδικό ότι ΔΕΝ επιτρέπει ξεκάθαρη αποκωδικοποίηση
Παράδειγμα 2. Το αρχικό αλφάβητο και το αλφάβητο του κωδικού είναι το ίδιο όπως στο παράδειγμα 1. Κάθε γράμμα κωδικοποιείται επίσης με τον δικό του αριθμό στο αλφάβητο, ΑΛΛΑ ο αριθμός γράφεται πάντα με δύο ψηφία: Το 0 προστίθεται στην εγγραφή μονοψήφιων αριθμών στα αριστερά Για παράδειγμα, ο κωδικός Α είναι 01, ο κωδικός Β είναι 02, κ.λπ.
Σε αυτήν την περίπτωση, ο κωδικός κειμένου ABBA θα είναι 01020201. Και αυτός ο κωδικός μπορεί να αποκρυπτογραφηθεί μόνο με έναν τρόπο. Για να το αποκρυπτογραφήσετε, απλώς αναλύστε το κείμενο κώδικα 01020201 για δύο: 01 02 02 01 και για κάθε δύο, καθορίστε το γράμμα που αντιστοιχεί σε αυτό.
Αυτή η μέθοδος κωδικοποίησης ονομάζεται ενιαία. Η ομοιόμορφη κωδικοποίηση επιτρέπει πάντα τη σαφή αποκωδικοποίηση.
Στη συνέχεια, εξετάζεται μόνο η κωδικοποίηση γράμμα προς γράμμα.
3. Ανομοιόμορφη κωδικοποίηση
Η ομοιόμορφη κωδικοποίηση είναι βολική για αποκωδικοποίηση. Ωστόσο, συχνά χρησιμοποιούνται και μη ομοιόμορφοι κωδικοί, π.χ. κωδικούς με διαφορετικά μήκη κωδικών λέξεων. Αυτό είναι χρήσιμο όταν κείμενο πηγήςδιαφορετικά γράμματα εμφανίζονται με διαφορετικές συχνότητες. Στη συνέχεια, οι χαρακτήρες που εμφανίζονται συχνά θα πρέπει να κωδικοποιούνται με μικρότερες λέξεις και οι σπάνιοι με μεγαλύτερες. Από το Παράδειγμα 1 είναι σαφές ότι (σε ​​αντίθεση με τους ομοιόμορφους κώδικες!) δεν επιτρέπουν όλοι οι μη ομοιόμορφοι κώδικες ξεκάθαρη αποκωδικοποίηση.
Υπάρχει μια απλή συνθήκη, υπό την οποία ένας μη ομοιόμορφος κώδικας επιτρέπει τη σαφή αποκωδικοποίηση.
Ένας κώδικας ονομάζεται πρόθεμα εάν δεν περιέχει μια κωδική λέξη που θα ήταν η αρχή (με επιστημονικούς όρους, ένα πρόθεμα) μιας άλλης κωδικής λέξης.

Θέλω όμως να δείξω πώς να αυτοματοποιηθεί αυτή η διαδικασία.
Θα δημοσιεύσω το βίντεο στο Διαδίκτυο
Θα δώσω ένα παράδειγμα από την προετοιμασία για την Ενιαία Κρατική Εξέταση στην επιστήμη των υπολογιστών (εταιρεία 1C - υλικά από το Κέντρο Πιστοποιημένης Εκπαίδευσης):
Για την κωδικοποίηση μιας ορισμένης ακολουθίας που αποτελείται από τα γράμματα C, T, P, O, K και A, χρησιμοποιείται ένας μη ομοιόμορφος δυαδικός κώδικας που ικανοποιεί τη συνθήκη Fano και επομένως επιτρέπει τη μοναδική αποκωδικοποίηση της προκύπτουσας δυαδικής ακολουθίας. Εδώ είναι ο κωδικός: S - 000, T - 001, P - 010, O - 100, K - 011, A - 11. Είναι δυνατόν να συντομεύσετε το μήκος της κωδικής λέξης για ένα από τα γράμματα έτσι ώστε ο κωδικός να εξακολουθεί να ικανοποιεί την συνθήκη Fano; Οι κωδικοί των υπόλοιπων γραμμάτων δεν πρέπει να αλλάξουν.

Επιλέγω σωστή επιλογήαπάντηση.

Πιθανές απαντήσεις:
1) για το γράμμα P - 01
2) για το γράμμα Ο - 10
3) για το γράμμα Α - 1
4) Αυτό είναι αδύνατο

Η σωστή επιλογή είναι 2
Λύση:
Η επιλογή 1) δεν είναι κατάλληλη - η συνθήκη Fano θα παραβιαστεί για τα γράμματα P και K
Η επιλογή 2) είναι κατάλληλη - η λέξη 10 δεν είναι η αρχή των κωδικών λέξεων για άλλα γράμματα
Η επιλογή 3) δεν είναι κατάλληλη - η συνθήκη Fano θα παραβιαστεί για τα γράμματα A και O
Η επιλογή 4) δεν είναι κατάλληλη - δείτε την επιλογή 2)

Ας δούμε τώρα τι θα παράγει το πρόγραμμα για την αυτοματοποιημένη επίλυση τέτοιων προβλημάτων και τον έλεγχο της γνώσης.
Η εργασία δεν καθορίζει τη συχνότητα ή την πιθανότητα εμφάνισης των γραμμάτων, επομένως στο πρόγραμμα θα το πάρουμε ίσο με 0,01 για όλα τα γράμματα.

Πιθανότητες:
0.01, 0.01, 0.01, 0.01, 0.01, 0.01

Αξίες:
Γ, Τ, Π, Ο, Κ, Α

Αποτέλεσμα:
C 000
T001
P01
Ο 100
Κ 101
Α 11

Είναι σαφές από τη λύση ότι μπορεί να υπάρχουν πολλές πιθανές λύσεις, αλλά όλες πληρούν την προϋπόθεση Fano.

το πιστεύω παρόμοια προγράμματαθα είναι χρήσιμο για την παρακολούθηση της γνώσης και η συμπερίληψη μιας τέτοιας συνάρτησης σε μια γλώσσα προγραμματισμού θα ενισχύσει τις δυνατότητες της γλώσσας, επομένως συμπεριλαμβάνω αυτή τη λειτουργίαστη γλώσσα SmartMath. Το ίδιο το πρόγραμμα καθορίζει τον αριθμό των συμβόλων για ανάλυση, τα ταξινομεί ανάλογα με τη συχνότητα και εκχωρεί κωδικούς σύμφωνα με τη συνθήκη Fano. Το πλεονέκτημα της αυτοματοποίησης της δημιουργίας κώδικα όταν πληρούται η προϋπόθεση του Fano είναι ότι μπορείτε να δημιουργήσετε γρήγορα λύσεις για οποιαδήποτε ακολουθία.
Δείτε τον σύνδεσμο.

Χρησιμοποιώ προεπισκόπησηπαρουσιάσεις δημιουργήστε έναν λογαριασμό ( λογαριασμός) Google και συνδεθείτε: https://accounts.google.com

Λεζάντες διαφάνειας:

Αδιαμφισβήτητη αποκωδικοποίηση Άμεση και αντίστροφη κατάσταση Fano Δάσκαλος επιστήμης υπολογιστών και ΤΠΕ MBOU δευτεροβάθμιο σχολείο No. 7 Okha, περιοχή Sakhalin Sergienko Tatyana Gennadievna

Εργασία 1 Αφήστε τον ακόλουθο κωδικό να επιλεγεί για να κωδικοποιήσει τη φράση "Καλημέρα": GOODBREUT Space 111 000 00 1 01 0 10 11

Οι κωδικοί γραμμάτων "συνενώνονται" σε μια συμβολοσειρά μόνο bit και μεταδίδονται, για παράδειγμα, μέσω του δικτύου: Καλημέρα → 11100000100001110101000 Στον προορισμό, προκύπτει ένα πρόβλημα - πώς να επαναφέρετε το αρχικό μήνυμα και εάν αυτό είναι δυνατό.

11100000100001110101000 Αποκωδικ αυτό το μήνυμαΜπορώ διαφορετικοί τρόποι. Ας υποθέσουμε επίσης ότι αποτελείται μόνο από τα γράμματα P – 1 και U – 0. Τότε παίρνουμε RRRUUUUURUURRRURRUUU, δηλ. ένα σύνολο γραμμάτων χωρίς νόημα.

Ένας κωδικός ονομάζεται μοναδικά αποκωδικοποιήσιμος εάν μπορεί να αποκρυπτογραφηθεί οποιοδήποτε κωδικό μήνυμα ο μόνος τρόπος(οπωσδηποτε).

Αυτό σημαίνει ότι ο κωδικός δεν είναι μοναδικά αποκωδικοποιήσιμος.

Εργασία 2 Ενιαίοι κωδικοί. Για την ίδια φράση χρησιμοποιούμε τον ενιαίο κωδικό: D O R E U T Space 111 000 001 101 011 010 100 110

Οι ενιαίοι κωδικοί είναι αντιοικονομικοί - πολύ μεγαλύτεροι από τους μη ομοιόμορφους. Αυτό οδηγεί σε πιο περίπλοκη κωδικοποίηση, αλλά ταυτόχρονα αποκωδικοποιούνται ξεκάθαρα, γεγονός που κάνει φυσικά την εργασία ευκολότερη.

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

Χρησιμοποιούμε παρακάτω κώδικα: 01Αυτή η συμβολοσειρά bit αποκωδικοποιείται μοναδικά. D O B R E U T Space 01 00 1011 100 1010 1101 1110 1111

Το πρώτο γράμμα είναι D (κωδικός 01), γιατί καμία άλλη κωδική λέξη δεν αρχίζει με 01. Το δεύτερο γράμμα είναι O (κωδικός 00). Καμία άλλη λέξη δεν ξεκινά με 00. Αυτή η ίδια ιδιότητα, που ονομάζεται συνθήκη Fano, ισχύει για κωδικές λέξεις άλλων γραμμάτων.

ΚΑΤΑΣΤΑΣΗ FANO Καμία κωδική λέξη δεν συμπίπτει με την αρχή άλλης κωδικής λέξης. Τέτοιοι κωδικοί ονομάζονται πρόθεμα (αποκωδικοποιούνται από την αρχή του μηνύματος) και αποκωδικοποιούνται μοναδικά.

Εργασία 4 Ας εξετάσουμε έναν άλλο κωδικό: Δεν είναι πρόθεμα, γιατί ο κωδικός του γράμματος D (10) συμπίπτει με την αρχή του κωδικού του γράμματος B (1011), U (1000) και ο κωδικός του γράμματος O (00) συμπίπτει με την αρχή του κωδικού του γράμματος P ( 001). D O R E U T Space 10 00 1011 001 0101 1000 0111 1111

Ας κωδικοποιήσουμε το μήνυμά μας: ΚΑΛΗΜΕΡΑ → 10 00 1011 001 00 0101 1111 1000 0111 001 00 Ας ξεκινήσουμε την αποκωδικοποίηση από την αρχή. Το πρώτο είναι το D, ή το U, και μετά πηγαίνουν γενικά διαφορετικές παραλλαγές: Ρ ή Β... Δηλ. πρέπει να "κοιτάξετε" μπροστά, κάτι που είναι πολύ άβολο.

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

Οι κωδικοί για τους οποίους ικανοποιείται η αντίστροφη συνθήκη Fano ονομάζονται postfix.

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

Η συνθήκη Fano είναι επαρκής, αλλά όχι απαραίτητη προϋπόθεση για σαφή αποκωδικοποίηση. Αυτό σημαίνει ότι: - για αδιαμφισβήτητη αποκωδικοποίηση, αρκεί να πληρούται τουλάχιστον μία από τις δύο προϋποθέσεις - άμεση ή αντίστροφη. - μπορεί να υπάρχουν κώδικες για τους οποίους δεν ικανοποιείται ούτε η άμεση ούτε η αντίστροφη συνθήκη Fano, αλλά παρόλα αυτά παρέχει σαφή αποκωδικοποίηση, επειδή αλλιώς χάνεται το νόημα της έκφρασης.

Εργασία 5 Για την κωδικοποίηση μιας συγκεκριμένης ακολουθίας που αποτελείται από τα γράμματα A, B, C, D και D, χρησιμοποιείται ένας μη ομοιόμορφος δυαδικός κώδικας, ο οποίος καθιστά δυνατή την αναμφισβήτητη αποκωδικοποίηση της προκύπτουσας δυαδικής ακολουθίας. Εδώ είναι ο κωδικός: A – 00, B – 01, C – 100, D – 101, D – 110.

Είναι δυνατόν να συντομεύσετε το μήκος της κωδικής λέξης για ένα από τα γράμματα, έτσι ώστε ο κωδικός να μπορεί να αποκωδικοποιηθεί ακόμη χωρίς αμφιβολία; Οι κωδικοί των υπόλοιπων γραμμάτων δεν πρέπει να αλλάξουν. Επιλέξτε τη σωστή απάντηση: 1) για το γράμμα D -11 2) αυτό είναι αδύνατο 3) για το γράμμα G - 10 4) για το γράμμα D -10

ΛΥΣΗ: Πηγή– πρόθεμα. Για αυτό, η συνθήκη Fano ικανοποιείται - κανένας από τους κωδικούς τριών bit δεν ξεκινά ούτε με 00 (A) ούτε με 01 (B). (Σε αυτήν την περίπτωση, η αντίστροφη συνθήκη Fano δεν ικανοποιείται - ο κωδικός A (00) συμπίπτει με την κατάληξη B (100) και ο κωδικός B (01) συμπίπτει με την κατάληξη D (101).)

Τώρα ας ελέγξουμε τις απαντήσεις. Ας μειώσουμε το D σε 11. Εάν ο κωδικός που προκύπτει παραβιάζει την άμεση συνθήκη Fano, τότε θα παραβιαστεί η ιδιότητα της ξεκάθαρης αποκωδικοποίησης. Αλλά αυτό δεν συνέβη, δεν υπάρχουν άλλοι κωδικοί που να ξεκινούν με 11. Αυτό είναι η σωστή απόφαση. Ας ελέγξουμε τις άλλες επιλογές.

Δεν εξετάζουμε αμέσως την επιλογή 2 - βρήκαμε την απάντηση. Η επιλογή 3 παραβιάζει την άμεση συνθήκη του Fano - ο κωδικός του γράμματος B (101) αρχίζει με 10. Η επιλογή 4 παραβιάζει επίσης την άμεση συνθήκη του Fano. Εκείνοι. Η απάντηση είναι ξεκάθαρη, δεν υπάρχουν άλλες επιλογές.

Σας ευχαριστώ για την προσοχή σας!

3. Πολλαπλασιασμός των πιθανοτήτων ανεξάρτητων κοινών γεγονότων

4. Εύρεση του μέσου όρου για τις τιμές των τυχαίων ανεξάρτητων μεταβλητών

5. Η έννοια της υπό όρους πιθανότητας

6. Γενικός τύπος για την πιθανότητα να συμβούν γεγονότα

7. Γενικός τύπος για την πιθανότητα του αθροίσματος των γεγονότων

Διάλεξη 3. Η έννοια της εντροπίας

1. Η εντροπία ως μέτρο αβεβαιότητας

2. Ιδιότητες της εντροπίας

3. Εντροπία υπό όρους

Διάλεξη 4. Εντροπία και πληροφορίες

1. Ογκομετρική προσέγγιση για τη μέτρηση του όγκου των πληροφοριών

2. Προσέγγιση εντροπίας για τη μέτρηση του όγκου των πληροφοριών

Διάλεξη 5. Πληροφορίες και αλφάβητο

Διάλεξη 6. Δήλωση του προβλήματος κωδικοποίησης. Το πρώτο θεώρημα του Shannon.

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

1. Δήλωση του προβλήματος βελτιστοποίησης της ανομοιόμορφης κωδικοποίησης

2. Ανομοιόμορφος κωδικός με οριοθέτη

3. Κωδικοί χωρίς διαχωριστικό. Κατάσταση Fano

4. Κωδικός προθέματος Shannon–Fano

5. Κωδικός προθέματος Huffman

Διάλεξη 8. Μέθοδοι κατασκευής δυαδικών κωδίκων. Αλλες επιλογές

1. Ομοιόμορφη αλφαβητική δυαδική κωδικοποίηση. Κωδικός byte

2. Διεθνή συστήματα κωδικοποίησης byte για δεδομένα κειμένου. Καθολικό σύστημα κωδικοποίησης δεδομένων κειμένου

3. Αλφαβητική κωδικοποίηση με άνιση διάρκεια στοιχειωδών σημάτων. κώδικας Μορς

4. Αποκλεισμός δυαδικής κωδικοποίησης

5. Κωδικοποίηση γραφικών δεδομένων

6. Κωδικοποίηση ηχητικών πληροφοριών

Διάλεξη 9. Αριθμητικά συστήματα. Αναπαράσταση αριθμών σε διαφορετικά συστήματα αριθμών. Μέρος 1

1. Αριθμητικά συστήματα

2. Σύστημα δεκαδικών αριθμών

3. Δυαδικό σύστημα αριθμών

4. 8- και δεκαεξαδικά συστήματα αριθμών

5. Συστήματα μικτών αριθμών

6. Η έννοια της οικονομίας ενός συστήματος αριθμών

Διάλεξη 10. Αριθμητικά συστήματα. Αναπαράσταση αριθμών σε διαφορετικά συστήματα αριθμών. Μέρος 2ο.

1. Η εργασία μετατροπής ενός αριθμού από ένα σύστημα αριθμών σε άλλο

2. Μετατροπή q  p ακεραίων

3. Μετατροπή p  q ακεραίων

4. Μετατροπή p  q κλασμάτων

6. Μετατροπή αριθμών μεταξύ διψήφιων, 8ψήφιων και δεκαεξαδικών συστημάτων αριθμών

Διάλεξη 11. Κωδικοποίηση αριθμών σε υπολογιστή και λειτουργίες σε αυτούς

1. Κανονικοί αριθμοί

2. Μετατροπή ενός αριθμού από τη φυσική του μορφή στην κανονικοποιημένη του μορφή

3. Μετατροπή κανονικοποιημένων αριθμών

4. Κωδικοποίηση και επεξεργασία ανυπόγραφων ακεραίων

5. Κωδικοποίηση και επεξεργασία υπογεγραμμένων ακεραίων

6. Κωδικοποίηση και επεξεργασία πραγματικών αριθμών

Διάλεξη 12. Μετάδοση πληροφοριών μέσω γραμμών επικοινωνίας

1. Γενικό σχήμα μετάδοσης πληροφοριών σε γραμμή επικοινωνίας

2. Χαρακτηριστικά καναλιού επικοινωνίας

3. Επίδραση του θορύβου στη χωρητικότητα του καναλιού

Διάλεξη 13. Διασφάλιση της αξιοπιστίας της μεταφοράς πληροφοριών.

1. Δήλωση του προβλήματος της διασφάλισης της αξιοπιστίας μετάδοσης

2. Κωδικοί που εντοπίζουν ένα μόνο σφάλμα

3. Κωδικοί που διορθώνουν ένα μόνο λάθος

Διάλεξη 14. Μέθοδοι μετάδοσης πληροφοριών σε γραμμές επικοινωνίας υπολογιστή

1. Παράλληλη μεταφορά δεδομένων

2. Σειριακή μετάδοση δεδομένων

3. Επικοινωνία ηλεκτρονικών υπολογιστών μέσω τηλεφωνικών γραμμών

Διάλεξη 15. Ταξινόμηση δεδομένων. Αναπαράσταση δεδομένων στη μνήμη του υπολογιστή

1. Ταξινόμηση δεδομένων

2. Αναπαράσταση στοιχειωδών δεδομένων στη μνήμη RAM

Διάλεξη 16. Ταξινόμηση δομών δεδομένων

1. Ταξινόμηση και παραδείγματα δομών δεδομένων

2. Η έννοια της λογικής σημειογραφίας

Διάλεξη 17. Οργάνωση δομών δεδομένων σε RAM και σε εξωτερικά μέσα

1. Οργάνωση δομών δεδομένων στη μνήμη RAM

2. Ιεραρχία δομών δεδομένων σε εξωτερικά μέσα

3. Χαρακτηριστικά συσκευών αποθήκευσης

Ερωτήσεις ελέγχου

Βιβλιογραφία

3. Κωδικοί χωρίς διαχωριστικό. Κατάσταση Fano

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

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

Οι απλούστεροι και πιο συχνά χρησιμοποιούμενοι κωδικοί χωρίς διαχωριστικό είναι οι λεγόμενοι κωδικούς προθέματος, που πληρούν την ακόλουθη προϋπόθεση - Κατάσταση Fano:Ένα μήνυμα που κωδικοποιείται χρησιμοποιώντας έναν μη ομοιόμορφο κωδικό μπορεί να αποκωδικοποιηθεί ξεκάθαρα εάν κανένας από τους κωδικούς στο μήνυμα δεν ταιριάζει με το πρόθεμα * (αρχή) κάποιου άλλου μεγαλύτερου κώδικα.

Για παράδειγμα, εάν υπάρχει κωδικός 110, τότε οι κωδικοί 1, 11, 1101, 110101 κ.λπ. δεν μπορούν πλέον να χρησιμοποιηθούν.

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

Παράδειγμα 1. Οι κωδικοί παρουσιάζονται στον πίνακα; 4, πρόθεμα; Οι κωδικοί που παρουσιάζονται στον πίνακα. Τα 4 δεν είναι πρόθεμα. Δείτε, για παράδειγμα, τους κωδικούς των γραμμάτων «O» και «E», «A» και «N», «S» και «M», «D» και «Ch».

Παράδειγμα 2. Υπάρχει ένας πίνακας κωδικών προθεμάτων (Πίνακας 6). Πρέπει να αποκωδικοποιήσετε το ακόλουθο μήνυμα κωδικοποιημένο χρησιμοποιώντας αυτόν τον πίνακα κωδικών:

00100010000111010101110000110

Τραπέζι 6. Πίνακας κωδικών προθεμάτων

Η αποκωδικοποίηση πραγματοποιείται επαναλαμβάνοντας κυκλικά τα ακόλουθα βήματα:

«Κόψτε» το σύμβολο που βρίσκεται στο αριστερό μέρος από το τρέχον μήνυμα, επισυνάψτε το στα δεξιά στην τρέχουσα κωδική λέξη.

Συγκρίνετε την τρέχουσα κωδική λέξη με τον πίνακα κωδικών. εάν δεν υπάρχει αντιστοιχία, επιστρέψτε στο βήμα 1.

Χρησιμοποιώντας τον πίνακα κωδικών, αντιστοιχίστε την τρέχουσα κωδική λέξη με έναν χαρακτήρα του κύριου αλφαβήτου.

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

Εφαρμογή αυτού του αλγορίθμουστο κωδικοποιημένο μήνυμα που προτείνεται παραπάνω δίνει:

00100010000111010101110000110

Έτσι, έχοντας ολοκληρώσει τη διαδικασία αποκωδικοποίησης, μπορείτε να λάβετε το μήνυμα: «μητέρα του σαπουνιού πλαίσιο."

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

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

4. Κωδικός προθέματος Shannon–Fano

Ας εξετάσουμε την επιλογή κωδικοποίησης που προτάθηκε το 1948 - 1949. ανεξάρτητα από τους K. Shannon και R. Fano.

Ας εξετάσουμε το σχήμα κωδικοποίησης Shannon–Fano (πώς κατασκευάζεται) ως εξής: παράδειγμα .

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

Ας χωρίσουμε τα ζώδια σε δύο ομάδες έτσι ώστε τα αθροίσματα των πιθανοτήτων σε καθεμία από αυτές τις δύο ομάδες να είναι περίπου ίσα. Στην περίπτωση αυτή, η 1η ομάδα θα περιλαμβάνει Και , και τα υπόλοιπα - στη 2η ομάδα. Σημάδια Ας αντιστοιχίσουμε το πρώτο αριστερό ψηφίο των κωδικών τους στην πρώτη ομάδα ως «0» και ας είναι το πρώτο αριστερό ψηφίο των κωδικών συμβόλων της δεύτερης ομάδας «1».

Ας συνεχίσουμε να διαιρούμε κάθε μία από τις προκύπτουσες ομάδες σε υποομάδες σύμφωνα με το ίδιο σχήμα, δηλαδή, έτσι ώστε τα αθροίσματα των πιθανοτήτων σε κάθε βήμα και στις δύο υποομάδες της διαχωριστικής ομάδας να είναι όσο το δυνατόν πιο κοντά. Έτσι, θα λάβουμε τα ακόλουθα bits κωδικών χαρακτήρων ένα προς ένα . Θα αντιστοιχίσουμε αυτά τα επόμενα ψηφία στα δεξιά στα υπάρχοντα.

Ολόκληρη αυτή η διαδικασία μπορεί να απεικονιστεί σχηματικά στον Πίνακα 7.

Τραπέζι 7. Κατασκευή του κώδικα Shannon-Fano

Σημάδι		Κωδικοί αριθμοί

Μπορεί να φανεί ότι οι κατασκευασμένοι κωδικοί χαρακτήρων ικανοποιεί τη συνθήκη Fano, επομένως, αυτή η κωδικοποίηση είναι πρόθεμα.

Ας βρούμε το μέσο μήκος του κώδικα που προκύπτει χρησιμοποιώντας τον τύπο

,

Οπου – τον ​​αριθμό των bit (χαρακτήρων) στον κωδικό που αντιστοιχεί στο σύμβολο .

Από τον πίνακα είναι ξεκάθαρο ότι
,
,
.

Έτσι παίρνουμε:

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

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

.

Ας βρούμε τον πλεονασμό του δυαδικού κώδικα που προκύπτει:

,

δηλαδή ο πλεονασμός είναι περίπου 2,5.

Ας μάθουμε αν ο κώδικας που προκύπτει είναι ο βέλτιστος. Υπάρχουν 6 μηδενικά στους κωδικούς που ελήφθησαν και 11 ένα. Έτσι, οι πιθανότητες εμφάνισης του 0 και του 1 απέχουν πολύ από το να είναι ίσες. Επομένως, ο κώδικας που προκύπτει δεν μπορεί να θεωρηθεί βέλτιστος.

Το μάθημα είναι αφιερωμένο στον τρόπο επίλυσης της εργασίας 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

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

Ας δούμε μια άλλη ανάλυση 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

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

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

Г, στο οποίο ο κωδικός θα επιτρέπει σαφή αποκωδικοποίηση. το μικρότεροαριθμητική αξία.

✍ Λύση:

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

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

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:

Unified State Examination in Informatics 5 task 2017 FIPI option 17 (Krylov S.S., Churkina T.E.):

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

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

✍ Λύση:

1 - ακατάλληλο (όλα τα γράμματα εκτός από το Α ξεκινούν με 1) 10 - ακατάλληλο (αντιστοιχεί στον κωδικό D) 11 - ακατάλληλο (η αρχή των κωδικών B, C και D) 100 - ακατάλληλο (κωδικός D - 10 - είναι το αρχή αυτού του κωδικού) 101 - ακατάλληλο (κωδικός D - 10 - είναι η αρχή αυτού του κωδικού) 110 - ακατάλληλο (η αρχή του κωδικού Β και Δ) 111 - ακατάλληλο (αντιστοιχεί στον κωδικό Β) 1000 - ακατάλληλο ( κωδικός D - 10 - είναι η αρχή αυτού του κωδικού) 1001 - ακατάλληλο (κωδικός D - 10 - είναι η αρχή αυτού του κωδικού) 1010 - ακατάλληλο (κωδικός D - 10 - είναι η αρχή αυτού του κωδικού) 1011 - ακατάλληλο (κωδικός D - 10 - είναι η αρχή αυτού του κωδικού) 1100 - ακατάλληλο (αρχή κωδικού Β και Δ) 1101 - κατάλληλο

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

Περισσότερο αναλυτική λύσηΑυτή η εργασία παρουσιάζεται στο εκπαιδευτικό βίντεο:

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

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

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

✍ Λύση:

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

Για μια λεπτομερή λύση σε αυτήν την 5η εργασία από την έκδοση επίδειξης του Unified State Exam 2018, δείτε το βίντεο:

Εργασία 5_9. Πρότυπες επιλογές εξετάσεων 2017. Επιλογή 4 (Krylov S.S., Churkina T.E.):

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

A: 00011 B: 111 C: 1010

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

✍ Λύση:

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

Εργασία 5_10. Επιλογή προπόνησης Νο. 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

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