Đề thi tin học số 5 cách giải. Quyết định sử dụng biểu diễn nhị phân để mã hóa các chữ cái
Thư mục công việc.
Chuyển giao thông tin. Lựa chọn mã
Làm bài kiểm tra cho các nhiệm vụ này
Quay lại danh mục công việc
Phiên bản để in và sao chép trong MS Word
Để mã hóa một chuỗi nhất định bao gồm các chữ cái K, L, M, N, chúng tôi quyết định sử dụng một mã nhị phân không đồng nhất thỏa mãn điều kiện Fano. Đối với chữ H, từ mã 0 được sử dụng, đối với chữ K, từ mã 10. Tổng độ dài nhỏ nhất có thể có của cả bốn từ mã là bao nhiêu?
Ghi chú.
Dung dịch.
Hãy tìm cách biểu diễn ngắn nhất cho tất cả các chữ cái. Các từ mã 01 và 00 không được sử dụng, do đó điều kiện Fano bị vi phạm. Ví dụ, chúng ta hãy sử dụng từ mã 11 cho chữ L. Sau đó, đối với chữ cái thứ tư, không thể tìm thấy từ mã nào mà không vi phạm điều kiện Fano. Do đó, đối với hai chữ cái còn lại, các từ mã có ba chữ số phải được sử dụng. Ta mã hóa các chữ cái L và M bằng các từ mã 110 và 111. Khi đó tổng độ dài của cả bốn từ mã là 1 + 2 + 3 + 3 = 9.
Trả lời: 9.
Trả lời: 9
Để mã hóa một chuỗi nhất định bao gồm các chữ cái A, B, C, D và D, một mã nhị phân không đồng nhất được sử dụng để có thể giải mã duy nhất chuỗi nhị phân thu được. Đây là mã: A - 1; B - 0100; B - 000; G - 011; D - 0101. Cần phải giảm độ dài của từ mã cho một trong các chữ cái để mã vẫn có thể được giải mã một cách rõ ràng. Mã của các chữ cái còn lại không được thay đổi. Cách nào sau đây có thể thực hiện được?
1) cho chữ cái G - 11
2) cho chữ B - 00
3) cho chữ cái G - 01
4) không thể
Dung dịch.
Để giải mã rõ ràng, từ mã thu được không được là đầu của bất kỳ từ mã nào khác. Câu trả lời đầu tiên không phù hợp, vì mã cho chữ A là phần đầu của mã cho chữ G. Câu trả lời thứ hai là phù hợp. Câu trả lời thứ ba là không phù hợp, bởi vì trong trường hợp này, mã cho chữ G là đầu mã cho chữ D.
Câu trả lời đúng được đánh số: 2.
Trả lời: 2
Để mã hóa một chuỗi nhất định bao gồm các chữ cái I, K, L, M, N, chúng tôi quyết định sử dụng một mã nhị phân không đồng nhất thỏa mãn điều kiện Fano. Đối với chữ H, từ mã 0 được sử dụng, đối với chữ K, từ mã 10. Tổng độ dài nhỏ nhất có thể có của tất cả năm từ mã là bao nhiêu?
Ghi chú. Điều kiện Fano có nghĩa là không có từ mã nào là đầu của từ mã khác. Điều này cho phép giải mã rõ ràng các tin nhắn được mã hóa.
Dung dịch.
Bạn không thể sử dụng các từ mã bắt đầu bằng 0 hoặc 10. Chúng tôi cũng không thể sử dụng 11, vì khi đó chúng tôi không thể sử dụng bất kỳ từ mã nào khác nữa và chúng tôi cần năm từ mã đó. Do đó, chúng tôi lấy ba chữ số 110. Một lần nữa, chúng tôi không thể sử dụng 111, bởi vì chúng tôi cần thêm một từ mã, đồng thời sẽ không còn những từ miễn phí nữa. Bây giờ chỉ cần hai từ là 1110 và 1111. Tổng cộng chúng ta có 0, 10, 110, 1110 và 1111 - 14 ký tự.
Trả lời: 14.
Trả lời: 14
Để mã hóa một chuỗi nhất định bao gồm các chữ cái I, K, L, M, N, chúng tôi quyết định sử dụng một mã nhị phân không đồng nhất thỏa mãn điều kiện Fano. Đối với chữ cái L, từ mã 1 đã được sử dụng, đối với chữ M, từ mã 01. Tổng độ dài nhỏ nhất có thể có của tất cả năm từ mã là bao nhiêu?
Ghi chú.Điều kiện Fano có nghĩa là không có từ mã nào là đầu của từ mã khác. Điều này cho phép giải mã rõ ràng các tin nhắn được mã hóa.
Dung dịch.
Điều kiện của Fano - không từ mã nào có thể là đầu của từ mã khác. Vì đã có từ mã 1 nên không có từ mã nào khác có thể bắt đầu bằng 1. Chỉ với 0. Cũng không thể bắt đầu bằng 01, vì chúng ta đã có 01. Tức là bất kỳ từ mã mới nào cũng sẽ bắt đầu bằng 00. Nhưng đây không thể là 00, vì nếu không, chúng ta không thể sử dụng bất kỳ từ mã nào nữa, vì tất cả các từ dài hơn đều bắt đầu bằng 1 hoặc bằng 00 hoặc bằng 01. Chúng ta có thể lấy 000 hoặc 001. Nhưng không phải cả hai cùng một lúc, vì một lần nữa trong trường hợp này, chúng ta sẽ không còn có thể lấy bất kỳ mã mới nào. Sau đó, chúng ta lấy 001. Và vì chúng ta chỉ còn lại hai mã, chúng ta có thể lấy 0000 và 0001. Tổng cộng chúng ta có: 1, 01, 001, 0000, 0001. Tổng cộng có 14 ký tự.
Để xem bản trình bày có hình ảnh, thiết kế và trang trình bày, tải xuống tệp của nó và mở nó trong PowerPoint trên máy tính của bạn.
Nội dung văn bản của slide thuyết trình: Luyện thi Giáo viên khoa học máy tính Kinh tế Nhà nước Thống nhất, trường THCS số 1 MBOU, Azova Balamutova Irina Alexandrovna 2015 Mã hóa và giải mã thông tin. (Nhiệm vụ 5) Mã hóa dữ liệu, tổ hợp, hệ thống số (Nhiệm vụ 10) Nội dung của chủ đề “Mã hóa và giải mã thông tin.” USE2 giải mã từ đầu nếu thỏa mãn điều kiện Fano: không có từ mã nào là đầu của từ mã khác; thông điệp được mã hóa có thể được giải mã rõ ràng từ cuối nếu đáp ứng điều kiện nghịch đảo Fano: không có từ mã nào là kết thúc của từ mã khác; điều kiện Fano là đủ, nhưng không phải là điều kiện cần thiết cho lý thuyết giải mã rõ ràng3 Mã hóa là bản dịch thông tin từ ngôn ngữ này sang ngôn ngữ khác. Mã hóa có thể đồng nhất và không thống nhất. Với mã hóa đồng nhất, tất cả các ký tự được mã hóa bằng các mã có độ dài bằng nhau. Với mã hóa không đồng nhất, các ký tự khác nhau có thể được mã hóa bằng các mã có độ dài khác nhau và 4 chữ cái G (không có chữ cái nào khác trong tin nhắn). Mỗi chữ cái được mã hóa dưới dạng một chuỗi nhị phân. Khi chọn mã, hai yêu cầu đã được tính đến: a) không có từ mã nào là đầu của từ mã khác (điều này là cần thiết để mã cho phép giải mã rõ ràng); b) tổng độ dài của thông điệp được mã hóa phải càng ngắn càng tốt. Nên chọn mã nào trong số các mã sau để mã hóa các chữ cái A, B, C và D? 555551) A: 0, B: 10, C: 110, D: 1112) A: 0, B: 10, V: 01, D: 113) A: 1, B: 01, V: 011, D: 0014) A: 00, B: 01, V: 10, D: 11 trong đó không có từ mã nào trùng với phần đầu của mã khác (tôi gọi là tiền tố mã như vậy) cho mã 2, điều kiện “a” không được đáp ứng, vì từ mã của chữ cái B (01) bắt đầu bằng từ mã của chữ A (0) cho mã 3, điều kiện “a” không được đáp ứng, vì từ mã của chữ B (011) bắt đầu bằng từ mã của chữ B (01) cho mã 1 và 4, điều kiện là gặp, chúng tôi xem xét chúng thêm, chúng tôi tính tổng số bit trong thông báo cho mã 1: 16 ∙ 1 + 8 2 + 4 ∙ 3 + 4 ∙ 3 = 56 bit đếm tổng số bit trong thông báo cho mã 4: 16 ∙ 2 + 8 2 + 4 ∙ 2 + 4 ∙ 2 = 64 bitcode 1 cho độ dài thông điệp nhỏ nhất, vì vậy hãy chọn nó Trả lời: 1.6 Bài toán giải 1 Để mã hóa một số chuỗi bao gồm các chữ cái A, B, C, D, quyết định sử dụng mã nhị phân không đồng nhất thỏa mãn điều kiện Fano. Từ mã 0 được sử dụng cho chữ A, từ mã 110 được sử dụng cho chữ B. Tổng độ dài nhỏ nhất có thể có của tất cả bốn từ mã là bao nhiêu? 1) 7 2) 8 3) 9 4) 107 có nghĩa là không có từ mã nào là giống như phần đầu của từ mã khác, vì đã có từ mã 0, không từ mã nào khác có thể bắt đầu bằng 0, vì có mã 110, các từ mã 1, 11 bị cấm; Ngoài ra, không có từ mã nào khác có thể bắt đầu bằng 110, vì vậy phải chọn thêm hai từ mã khác mà các hạn chế này giữ. Có một từ mã hợp lệ gồm hai ký tự: 10 nếu bạn chọn từ mã 10 cho chữ B, thì một từ vẫn còn là ba -từ mã ký tự là 111, có thể chọn ký tự G8 Giải bài toán 2 bằng cách chọn các từ mã A - 0, B - 110, C - 10, G - 111, ta được tổng độ dài của các từ mã là 9 ký tự. Nếu bạn không chọn C - 10, nghĩa là ba từ mã ba ký tự hợp lệ: 100, 101 và 110; khi chọn bất kỳ hai chữ cái nào trong số chúng cho các chữ cái C và G, chúng ta nhận được tổng độ dài của các từ mã là 10, lớn hơn 9; do đó ta chọn phương án 3 (9 ký tự) Đáp số: 3. Lời giải bài toán 2 (tiếp theo) 9 Đồng thời, trong cây mã, tất cả các từ mã phải được đặt trong các lá của cây không có con cháu; hãy xây dựng một cây cho các từ mã đã cho A - 0 và B - 110: 10 Nhiệm vụ 2, hai “ các nhánh trống ”được đánh dấu bằng các đường đứt nét, trên đó bạn có thể“ đính kèm ”các lá cho các từ mã của các chữ cái C (10) và G (111) AB10100VG, chọn các từ mã A - 0, B - 110, C - 10 , G - 111, ta thu được tổng độ dài của các từ mã là 9 ký tự Trả lời: 3. Nhiệm vụ 2, phương pháp 2, xây dựng cây tiếp tục11 Tin nhắn chỉ chứa 4 chữ cái P, O, C, T được truyền qua kênh liên lạc; để truyền, mã nhị phân được sử dụng cho phép giải mã rõ ràng. Các từ mã sau đây được sử dụng cho các chữ cái T, O, P: T: 111, O: 0, P: 100. Chỉ định từ mã ngắn nhất cho chữ C, tại đó mã sẽ cho phép giải mã rõ ràng. Nếu có một số mã như vậy, hãy chỉ ra mã có giá trị số nhỏ nhất. 12Task 3 OT101000P1Solution (phương pháp 2, xây dựng cây): điều kiện Fano có nghĩa là không có từ mã nào trùng với phần đầu của từ mã khác; đồng thời, trong cây mã, tất cả các từ mã phải được đặt trong các lá của cây, nghĩa là, trong các nút không có con cháu; chúng tôi sẽ xây dựng một cây cho các từ mã đã cho là O - 0, T - 111 và P - 100: 13 Lời giải của bài toán 3 Các nét đứt đánh dấu hai nhánh "trống", trên đó bạn có thể "đính kèm" một trang tính cho từ mã của ký tự C: 101 hoặc 110; trong số này, mã 101 có giá trị nhỏ nhất Lời giải của bài toán 3 (tiếp theo) 14 15 Đường đứt nét đánh dấu hai nhánh “trống”, trên đó bạn có thể “đính kèm” một trang tính cho từ mã của chữ C: 101 hoặc 110; trong số này, mã 101 có giá trị nhỏ nhất. OT101000P1Chọn các từ mã A - 0, B - 110, C - 10, G - 111, ta được tổng độ dài của các từ mã là 9 ký hiệu Đáp số: 101. Lời giải bài toán 3 (tiếp theo) 15 Một hình raster đen trắng là được mã hóa từng dòng, bắt đầu từ góc trên bên trái và kết thúc ở góc dưới bên phải. Khi được mã hóa, 1 biểu thị màu đen và 0 biểu thị màu trắng. BD9AA5 2) BDA9B5 3) BDA9D5 4) DB9DAB 16Task 4 "kéo dài" bitmap thành một chuỗi: đầu tiên là dòng đầu tiên (trên cùng), sau đó đến dòng thứ hai, v.v.: có 24 ô trong dải này, các ô màu đen sẽ được lấp đầy đơn vị và đơn vị màu trắng - số không: vì mỗi chữ số trong hệ thập lục phân được phân tách thành chính xác 4 chữ số nhị phân, chúng tôi sẽ chia dải thành bốn chữ số - nhóm bốn ô (trong trường hợp này, không quan trọng việc bắt đầu phân tích ở đâu , vì có một số nguyên các tứ phân trong dải - 6): chuyển đổi tứ phân sang hệ thập lục phân, ta nhận được tuần tự các số B (11), D (13), A (10), 9, D (13) và 5, đó là chuỗi BDA9D5, do đó, câu trả lời đúng là 3,17 Bài giải 4 4 (tiếp theo) Bài tập 5 Số 7746. Để mã hóa một chuỗi nhất định bao gồm các chữ cái A, B, C, D và E, a non -mã nhị phân đồng nhất được sử dụng cho phép giải mã rõ ràng đã ăn chuỗi nhị phân kết quả. Đây là mã: A - 1; B - 0100; B - 000; G - 011; D - 0101. Cần phải giảm độ dài của từ mã cho một trong các chữ cái để mã vẫn có thể được giải mã một cách rõ ràng. Mã của các chữ cái còn lại không được thay đổi. Cách nào sau đây có thể thực hiện được? 1) đối với ký tự G - 112) đối với ký tự B - 003) đối với ký tự G - 014) điều này là không thể Đáp án: 19 nhiệm vụ cho giải pháp độc lập2
Nhiệm vụ 5 số 1104. Để mã hóa các chữ cái X, E, L, O, D, chúng tôi quyết định sử dụng biểu diễn nhị phân của các số 0, 1, 2, 3 và 4 tương ứng (với sự bảo toàn của một số 0 không đáng kể trong trường hợp biểu diễn một chữ số). Nếu bạn mã hóa chuỗi các chữ cái ICE DRIFT theo cách này và viết kết quả dưới dạng mã thập lục phân, bạn sẽ nhận được 1) 999С2) 32541453) 123F 4) 2143034 Đáp án: 20 câu trả lời Nhiệm vụ 5 Số 1104HELOD0123400011011100 Bây giờ chúng ta hãy chia biểu diễn này thành bốn từ bên phải sang trái và dịch tập hợp số kết quả trước tiên thành mã thập phân, sau đó sang thập lục phân. 1001 1001 1001 1100 - 9 9 9 12 - 999C. Câu trả lời đúng được chỉ ra dưới số 1.21 Nhiệm vụ 5 Số 7193 Để truyền tin nhắn qua một kênh liên lạc chỉ bao gồm các ký tự A, B, C và D, một ký tự không đồng đều ( theo chiều dài) mã được sử dụng: A - 0; B - 100; C - 101. Nên sử dụng từ mã nào để mã hóa ký hiệu Г sao cho độ dài của nó là nhỏ nhất, đồng thời mã cho phép tách thông điệp được mã hóa thành các ký hiệu một cách rõ ràng? 1) 12) 113) 01 Lời giải 4) 010 http://inf.reshuege.ru/test?theme=232 Đáp án: 222
Nhiệm vụ 5 số 9293.23 Để mã hóa một dãy gồm các chữ cái I, K, L, M, N, chúng tôi quyết định sử dụng một mã nhị phân không đồng nhất thỏa mãn điều kiện Fano. Đối với chữ cái L, từ mã 1 đã được sử dụng, cho chữ M, từ mã 01. Tổng độ dài nhỏ nhất có thể có của tất cả năm từ mã là bao nhiêu? Điều kiện Fano có nghĩa là không có từ mã nào là đầu của từ mã khác. Điều này cung cấp khả năng giải mã rõ ràng các tin nhắn được mã hóa. Trả lời: 4 Giải pháp http://inf.reshuege.ru/test?theme=23123
24 Nhiệm vụ cho video luyện tập Link bài học https://www.youtube.com/watch?v=BoBnzjwLsnU Chủ đề: Mã hóa dữ liệu, tổ hợp, hệ thống số (Nhiệm vụ 10) 25 Những điều bạn cần biết: bảng chữ cái tiếng Nga của các chữ cái L, và có n1 tùy chọn để chọn chữ cái đầu tiên, n2 tùy chọn để chọn chữ cái thứ hai, v.v., sau đó số từ có thể được tính là tích N = n1 n2 ... nL nếu từ bao gồm L chữ cái, và mỗi Chữ cái có thể được chọn trong n cách, sau đó số từ có thể được tính là N = nL26 Lý thuyết của Vasya là các từ gồm 5 chữ cái, trong đó chỉ có các chữ cái C, L, O, N và chữ C được sử dụng trong mỗi từ đúng 1 lần. Mỗi chữ cái hợp lệ khác có thể xuất hiện bất kỳ số lần nào trong từ hoặc hoàn toàn không. Một từ là bất kỳ chuỗi chữ cái hợp lệ nào, không nhất thiết phải có nghĩa. Có bao nhiêu từ như vậy mà Vasya có thể viết? C, trong đó * biểu thị bất kỳ ký tự nào trong số ba ký tự còn lại trong mỗi trường hợp, trong bốn vị trí còn lại có thể có bất kỳ ký tự nào trong ba chữ cái L, O, N, do đó, vị trí của chữ C, ta có 34 = 81 cách chọn trong tổng số 5 81 = 405. Đáp số: 405,28Có bao nhiêu dãy ký tự khác nhau có độ dài 5 trong bảng chữ cái gồm bốn chữ cái (A, C, G, T) chứa chính xác là hai chữ cái A? các chữ cái A và bắt đầu bằng A: AA *** A * A ** A ** A * A *** AZ ở đây dấu hoa thị là viết tắt của bất kỳ ký tự nào từ tập hợp (C, G, T), nghĩa là một trong ba ký tự. Vì vậy, trong mỗi mẫu có 3 vị trí, mỗi vị trí có thể được điền bằng ba cách, do đó tổng số tổ hợp (cho mỗi mẫu!) Là 33 = 27 trong tổng số 4 mẫu, chúng cho 4 27 = 108 tổ hợp 30 là chữ A ở vị trí thứ hai, chỉ có ba trong số họ: * AA ** * A * A * * A ** A họ cho 3 27 = 81 kết hợp của hai mẫu, trong đó chữ A đầu tiên ở vị trí thứ ba : ** AA * ** A * A họ đưa ra 2 27 = 54 kết hợp và một mẫu trong đó kết hợp AA ở cuối *** AA họ cho tổng cộng 27 kết hợp mà chúng ta nhận được (4 + 3 + 2 + 1) 27 = 270 tổ hợp Đáp số: 270 .Bài giải (tiếp theo) 31 Tất cả các từ gồm 4 chữ cái gồm các chữ cái K, L, R, T đều được viết theo thứ tự bảng chữ cái và được đánh số. Đây là phần đầu của danh sách: KKKK2. KKKL3. KKKR4. KKKT …… Hãy ghi lại từ đứng thứ 67 kể từ đầu danh sách. 32 Nhiệm vụ 3 Cách dễ nhất để giải quyết vấn đề này là sử dụng các hệ thống số; thực sự, ở đây sự sắp xếp các từ theo thứ tự bảng chữ cái tương đương với sự sắp xếp theo thứ tự tăng dần của các số được viết trong hệ thống số bậc bốn (cơ số của hệ thống số bằng số chữ cái được sử dụng). vì đánh số của các từ bắt đầu từ một và số đầu tiên KKKK0000 là 0, số 67 sẽ là số 66, phải chuyển sang hệ tứ: 66 = 10024 Sau khi thực hiện phép thay thế ngược lại (số cho các chữ cái) , ta được từ LKKR Đáp án: LKKR .33 Bài giải 34Câu 4 Nhiệm vụ 10 Số 6777. Từ các chữ cái E, G, E có thể tạo được bao nhiêu từ có độ dài 5? Mỗi chữ cái có thể xuất hiện trong một từ nhiều lần. 35 Bài giải Nếu có M ký tự trong bảng chữ cái, thì số tất cả các "từ" (tin nhắn) có thể có độ dài N bằng Q = MN. Ta có N = 5, M = 3. Do đó Q = 35 = 243. Đáp số: 243. 36Bài tập số 5 Bài 10 số 4797. Có 32 bút chì trong một hộp kín, một số bút chì màu xanh. Một cây bút chì được vẽ ngẫu nhiên. Thông báo "bút chì này KHÔNG có màu xanh lam" mang 4 bit thông tin. Có bao nhiêu bút chì màu xanh trong hộp? 37 Công thức của Shanonne: trong đó x là lượng thông tin trong thông báo về sự kiện P, p là xác suất của sự kiện P. xác suất mà chúng KHÔNG nhận được màu xanh lam trong đó là số lượng bút chì màu xanh lam. Sử dụng công thức Shanonne, chúng tôi nhận được đó là Y \ u003d 30 /www.youtube.com/watch?v=BoBnzjwLsnU DANH SÁCH TÀI LIỆUhttp: //kpolyakov.narod.ru/ Krylov S.S., Churkina T.E. SỬ DỤNG 2015. Tin học và CNTT-TT. Các phương án thi tiêu chuẩn. - M.: "Giáo dục quốc gia", 2015. Leshchiner V.R. SỬ DỤNG 2015. Tin học. Các nhiệm vụ kiểm tra điển hình. - M.: Thi, 2015. Evich L.N., Kulabukhov S.Yu. Tin học và CNTT. Chuẩn bị cho kỳ thi-2015. - Rostov-on-Don: Legion, 2014. Ushakov D.M., Yakushkin P.A. Tin học. Ấn bản đầy đủ nhất về các lựa chọn điển hình cho các nhiệm vụ của Kỳ thi Trạng thái Thống nhất năm 2014. - M .: Astrel, 2014. Evitch L.N., Kulabukhov S.Yu. Tin học và CNTT. Chuẩn bị cho kỳ thi-2015. - Rostov-on-Don: Legion, 2014. Ostrovskaya E.M., Samylkina N.N. SỬ DỤNG 2015. Tin học. Chúng tôi thuê mà không có vấn đề! - M.: Eksmo, 2014. Samylkina N.N., Ostrovskaya E.M. SỬ DỤNG 2015. Tin học. Các nhiệm vụ đào tạo theo chuyên đề. - M.: Eksmo, 2014. Zorina E.M., Zorin M.V. SỬ DỤNG 2015. Tin học. Bộ sưu tập các nhiệm vụ. - M.: "Eksmo", 2015.39 Các trang web hữu ích để CHUẨN BỊ CHO VIỆC SỬ DỤNG! 40 Khoa học máy tính thật dễ dàng http://easyinformatics.ru/Video phân tích các bài kiểm tra nhiệm vụ USE-2013 http://inf.reshuege.ru/?redir = 1 Đề thi Trạng thái Thống nhất môn Tin học 2013 http://infoegehelp.ru/40
Phân tích nhiệm vụ 5 của USE 2016 trong tin học từ bản demo. Đây là nhiệm vụ cho khả năng mã hóa và giải mã thông tin (để có thể diễn giải các kết quả thu được trong quá trình mô phỏng các quy trình thực). Đây là một nhiệm vụ cấp độ cơ bản. Thời gian dự kiến hoàn thành nhiệm vụ là 2 phút.
Nhiệm vụ 5:
Tin nhắn chỉ chứa bốn chữ cái được truyền qua kênh liên lạc: P, O, S, T; để truyền, mã nhị phân được sử dụng cho phép giải mã rõ ràng. Đối với các chữ cái T, O, P, các từ mã sau được sử dụng: T: 111, O: 0, P: 100.
Chỉ định từ mã ngắn nhất cho chữ C, tại đó mã sẽ cho phép giải mã rõ ràng. Nếu có một số mã như vậy, hãy chỉ ra mã có giá trị số nhỏ nhất.
Câu trả lời: ________
Phân tích nhiệm vụ 5 của USE 2016:
Để giải quyết công việc này, bạn cần biết điều kiện Fano.
Điều kiện Fano:
Một thông điệp được mã hóa có thể được giải mã rõ ràng nếu không có từ mã nào là phần cuối của một từ mã khác.
Điều kiện Fano nghịch đảo:
Một thông điệp được mã hóa có thể được giải mã rõ ràng từ phần cuối nếu không có từ mã nào là phần cuối của một từ mã khác.
Hãy bắt đầu kiểm tra theo thứ tự:
0 - không thể, vì O-0 (cũng có thể, từ mã không thể bắt đầu bằng 0, vì điều kiện Fano sẽ không được đáp ứng),
1 - không thể như vậy, vì T-111 và P-100 bắt đầu bằng một,
10 - không thể như vậy, vì P-100 bắt đầu bằng 10,
11 - không thể được, vì T-111 bắt đầu bằng 11,
100 - không thể như vậy, vì P-100,
101 — vừa vặn, vì điều kiện Fano được thỏa mãn,
110 — vừa vặn, vì điều kiện Fano được thỏa mãn.
Theo điều kiện của bài toán, nếu có nhiều từ, bạn cần chọn mã có giá trị số nhỏ nhất - do đó, chúng tôi chọn 101 .
Để đào tạo hiệu quả về khoa học máy tính cho mỗi nhiệm vụ, một tài liệu lý thuyết ngắn gọn được cung cấp để hoàn thành nhiệm vụ. Hơn 10 nhiệm vụ đào tạo với phân tích và câu trả lời đã được lựa chọn, phát triển trên cơ sở phiên bản demo của những năm trước.
Không có thay đổi nào trong KIM USE 2020 trong lĩnh vực tin học và công nghệ thông tin.
Các lĩnh vực sẽ thực hiện bài kiểm tra kiến thức:
- Lập trình;
- Thuật toán hóa;
- Công cụ CNTT-TT;
- Hoạt động thông tin;
- Các quy trình thông tin.
Các hành động cần thiết khi chuẩn bị:
- Sự lặp lại của khóa học lý thuyết;
- Dung dịch bài kiểm tra trong tin học Trực tuyến;
- Kiến thức về ngôn ngữ lập trình;
- Kéo lên toán học và logic toán học;
- Sử dụng nhiều loại tài liệu hơn - chương trình giảng dạy ở trường để thành công trong kỳ thi là chưa đủ.
Cấu trúc bài thi
Thời gian của kỳ thi là 3 giờ 55 phút (255 phút), trong đó một giờ rưỡi được khuyến nghị dành để hoàn thành các nhiệm vụ của phần đầu tiên của KIMs.
Nhiệm vụ trong vé được chia thành các khối:
- Phần 1- 23 nhiệm vụ với một câu trả lời ngắn gọn.
- Phần 2- 4 nhiệm vụ với một câu trả lời chi tiết.
Trong số 23 nhiệm vụ được đề xuất của phần đầu tiên của đề thi, 12 thuộc về mức độ kiểm tra kiến thức cơ bản, 10 - mức độ phức tạp tăng lên, 1 - mức độ phức tạp cao. Ba nhiệm vụ của phần thứ hai có mức độ phức tạp cao, một - một nhiệm vụ tăng lên.
Khi giải bắt buộc phải ghi đáp án chi tiết (dạng tùy ý).
Trong một số tác vụ, văn bản của điều kiện được gửi ngay lập tức bằng năm ngôn ngữ lập trình - để thuận tiện cho học sinh.
Điểm cho các nhiệm vụ trong khoa học máy tính
1 điểm - cho 1-23 nhiệm vụ
2 điểm - 25.
3 điểm - 24, 26.
4 điểm - 27.
Tổng: 35 điểm.
Để vào đại học kỹ thuật hệ trung cấp, bạn phải đạt từ 62 điểm trở lên. Để vào trường đại học thủ đô, số điểm phải tương ứng với 85-95.
Để viết thành công một bài kiểm tra, bạn cần có một lệnh rõ ràng về học thuyết và không đổi thực hành trong việc giải quyết các nhiệm vụ.
Công thức thành công của bạn
Làm việc + sửa lỗi + đọc kỹ câu hỏi từ đầu đến cuối để tránh mắc lỗi = điểm tối đa bài thi môn tin học.
Bài làm hướng dẫn cách giải bài tập số 5 ôn thi môn tin học
Chủ đề thứ 5 có đặc điểm là các nhiệm vụ có mức độ phức tạp cơ bản, thời gian thực hiện khoảng 2 phút, điểm tối đa là 1
- Mã hóa- đây là cách trình bày thông tin dưới dạng thuận tiện cho việc lưu trữ, truyền tải và xử lý thông tin. Quy tắc để chuyển đổi thông tin thành một biểu diễn như vậy được gọi là mã số.
- Mã hóa xảy ra đồng phục và không đồng đều:
- với mã hóa thống nhất, tất cả các ký tự tương ứng với các mã có cùng độ dài;
- với mã hóa không đồng nhất, các ký tự khác nhau tương ứng với các mã có độ dài khác nhau, điều này gây khó khăn cho việc giải mã.
Thí dụ: Chúng tôi mã hóa các chữ cái A, B, C, D bằng cách sử dụng mã nhị phân với một mã thống nhất và đếm số lượng tin nhắn có thể có:
Vì vậy, chúng tôi có mã thống nhất, tại vì độ dài của mỗi từ mã là như nhau cho tất cả các mã (2).
Mã hóa và giải mã tin nhắn
Giải mã (giải mã) là việc khôi phục một thông điệp từ một chuỗi mã.
Để giải quyết các vấn đề với giải mã, bạn cần biết điều kiện Fano:
Điều kiện Fano: không có từ mã nào phải là đầu của một từ mã khác (đảm bảo giải mã rõ ràng các thông điệp ngay từ đầu)
Mã tiền tố là mã trong đó không có từ mã nào trùng với đầu của từ mã khác. Tin nhắn sử dụng mã như vậy được giải mã rõ ràng.
Giải mã rõ ràng được cung cấp:
Giải pháp của 5 nhiệm vụ của kỳ thi
SỬ DỤNG 5.1:Để mã hóa các chữ cái O, B, D, P, A, chúng tôi quyết định sử dụng biểu diễn nhị phân của các số 0, 1, 2, 3 và 4 tương ứng (với một số 0 không đáng kể được giữ nguyên trong trường hợp biểu diễn một chữ số ).
Mã hóa chuỗi các chữ cái WATERFALL theo cách này và viết kết quả dưới dạng mã bát phân.
✍ Giải pháp:
- Hãy dịch các số thành mã nhị phân và đặt chúng thẳng hàng với các chữ cái của chúng ta:
Kết quả: 22162
Quyết định của kỳ thi nhiệm vụ này trong khoa học máy tính, video:
Hãy xem xét một phân tích khác về 5 nhiệm vụ của kỳ thi:
SỬ DỤNG 5.2:Đối với 5 chữ cái của bảng chữ cái Latinh, mã nhị phân của chúng được đưa ra (đối với một số chữ cái - từ hai bit, đối với một số - từ ba). Các mã này được trình bày trong bảng:
| một | b | c | d | e |
|---|---|---|---|---|
| 000 | 110 | 01 | 001 | 10 |
Bộ chữ cái nào được mã hóa bởi chuỗi nhị phân 1100000100110?
✍ Giải pháp:
- Đầu tiên, chúng tôi kiểm tra điều kiện Fano: không có từ mã nào là đầu của từ mã khác. Điều kiện là chính xác.
- Chúng tôi ngắt mã từ trái sang phải theo dữ liệu được trình bày trong bảng. Sau đó, chúng tôi dịch nó thành các chữ cái:
✎ 1 giải pháp:
Kết quả: b a c d e.
✎ Giải pháp 2:
110
000 01
001 10
Kết quả: b a c d e.
Ngoài ra, các bạn có thể xem video giải bài tập SỬ DỤNG này trong khoa học máy tính:
Hãy giải quyết 5 nhiệm vụ sau:
SỬ DỤNG 5.3:
Để truyền số qua kênh nhiễu, mã chẵn lẻ được sử dụng. Mỗi chữ số của nó được viết dưới dạng biểu diễn nhị phân, với các số 0 ở đầu được thêm vào có độ dài là 4 và tổng các phần tử của nó modulo 2 được thêm vào dãy kết quả (ví dụ: nếu chúng ta vượt qua 23, chúng ta nhận được dãy 0010100110) .
Xác định số đã được truyền qua kênh có dạng 01100010100100100110.
✍ Giải pháp:
- Xem xét thí dụ từ báo cáo vấn đề:
Câu trả lời: 6 5 4 3
Bạn có thể xem video về giải pháp cho nhiệm vụ SỬ DỤNG này trong khoa học máy tính:
SỬ DỤNG 5.4:
Để mã hóa một chuỗi nhất định bao gồm các chữ cái K, L, M, H, chúng tôi quyết định sử dụng một mã nhị phân không đồng nhất thỏa mãn điều kiện Fano. Từ mã 0 được sử dụng cho chữ H và từ mã 10 được sử dụng cho chữ K.
Tổng độ dài nhỏ nhất có thể có của cả bốn từ mã là bao nhiêu?
✍ Giải pháp:
✎ 1 giải pháp dựa trên suy luận logic:
- Hãy tìm các từ mã ngắn nhất có thể cho tất cả các chữ cái.
- từ mã 01 và 00 không thể được sử dụng, vì điều kiện Fano bị vi phạm (chúng bắt đầu từ 0, và 0 - đây là H).
- Hãy bắt đầu với các từ mã gồm hai chữ số. Hãy lấy bức thư L từ mã 11 . Sau đó, đối với chữ cái thứ tư, không thể chọn một từ mã mà không vi phạm điều kiện Fano (nếu sau đó bạn lấy 110 hoặc 111, thì chúng bắt đầu bằng 11).
- Vì vậy, bạn cần sử dụng các từ mã gồm ba chữ số. Hãy mã hóa các chữ cái L và M từ mã 110 và 111 . Điều kiện Fano được đáp ứng.
✎ Giải pháp 2:
(N) -> 0 -> 1 ký tự (K) -> 10 -> 2 ký tự (L) -> 110 -> 3 ký tự (M) -> 111 -> 3 ký tự Câu trả lời: 9
5.5: SỬ DỤNG TRONG TIN HỌC 5 task 2017 FIPI option 2 (Krylov S.S., Churkina T.E. biên tập):
Tin nhắn chỉ chứa 4 chữ cái được truyền qua kênh liên lạc: A, B, C, D; để truyền, mã nhị phân được sử dụng cho phép giải mã rõ ràng. Đối với các bức thư A B C các từ mã sau được sử dụng:
A: 101010, B: 011011, C: 01000
Chỉ định từ mã ngắn nhất cho chữ G, theo đó mã sẽ cho phép giải mã rõ ràng. ít nhất giá trị số.
✍ Giải pháp:
- Các mã nhỏ nhất có thể trông giống như 0 và 1 (bit đơn). Nhưng điều này sẽ không thỏa mãn điều kiện Fano ( NHƯNG bắt đầu từ một 101010 , B bắt đầu lại từ đầu - 011011 ).
- Mã nhỏ nhất tiếp theo sẽ là một từ gồm hai chữ cái 00 . Vì nó không phải là tiền tố của bất kỳ từ mã nào được trình bày, nên G = 00.
Kết quả: 00
5.6: SỬ DỤNG TRONG TIN HỌC 5 task 2017 FIPI option 16 (Krylov S.S., Churkina T.E. biên tập):
Để mã hóa một chuỗi nhất định bao gồm các chữ cái A, B, C, D và E, chúng tôi quyết định sử dụng mã nhị phân không đồng nhất cho phép bạn giải mã duy nhất chuỗi nhị phân xuất hiện ở phía nhận của kênh liên lạc. Mã đã sử dụng:
A - 01 B - 00 C - 11 D - 100
Chỉ định từ mã nào mà chữ D sẽ được mã hóa. Chiều dài từ mã này phải là ít nhất trong số tất cả có thể. Mã phải thỏa mãn thuộc tính giải mã rõ ràng. Nếu có một số mã như vậy, hãy chỉ ra mã có giá trị số nhỏ nhất.
✍ Giải pháp:
Kết quả: 101
Bài phân tích chi tiết hơn các em có thể xem trên Video Đề thi Thống nhất môn Tin học năm 2017:
5.7: 5 nhiệm vụ. Phiên bản demo của Kỳ thi Thống nhất Tin học 2018 (FIPI):
Các thông điệp được mã hóa chỉ chứa mười chữ cái được truyền qua kênh liên lạc: A, B, E, I, K, L, R, C, T, U. Một mã nhị phân không đồng đều được sử dụng để truyền. Các từ mã được sử dụng cho chín chữ cái. 
Các thông điệp được mã hóa chỉ chứa bốn chữ cái được truyền qua kênh liên lạc: A, B, C, D; để truyền, mã nhị phân được sử dụng cho phép giải mã rõ ràng. Đối với các bức thư NHƯNG, B, TẠI các từ mã được sử dụng:
A: 00011 B: 111 C: 1010
Chỉ định từ mã ngắn nhất cho chữ cái G, tại đó mã sẽ cho phép giải mã rõ ràng. Nếu có một số mã như vậy, hãy chỉ ra mã với ít nhất giá trị số.
✍ Giải pháp:
Kết quả: 00
5.9: Phương án đào tạo số 3 ngày 01.10.2018 (FIPI):
Tin nhắn chỉ chứa các chữ cái được truyền qua kênh liên lạc: A, E, D, K, M, R; để truyền, mã nhị phân được sử dụng thỏa mãn điều kiện Fano. Các mã sau được biết là sẽ được sử dụng:
E - 000 D - 10 K - 111
Chỉ định độ dài nhỏ nhất có thể của thông điệp được mã hóa DEDMAKAR.
Trong câu trả lời, viết một số - số bit.
✍ Giải pháp:
D E D M A C A R 10 000 10 001 01 111 01 110
Kết quả: 20
Xem giải pháp cho vấn đề:
Chú Vanya cốt truyện của vở kịch. “Chú Ivan. Thái độ đối với giáo sư của những người khác
Tsakhes nhỏ, biệt danh Zinnober
Maikov, Apollon Nikolaevich - tiểu sử ngắn