Kiểm tra đối chứng môn khoa học máy tính với chủ đề “Cơ sở toán học của khoa học máy tính”. Cơ sở toán học của khoa học máy tính Cơ sở toán học của trắc nghiệm khoa học máy tính trực tuyến
Bài kiểm tra Cơ sở toán tin học lớp 9 gồm 20 câu hỏi nhằm kiểm tra kết quả học tập môn khoa học máy tính lớp 9 về một chủ đề phù hợp.
1. Tập hợp các dấu hiệu để viết số gọi là:
a) hệ thống số
b) số của hệ thống số
c) bảng chữ cái của hệ thống số
d) cơ sở của hệ thống số
2. Kết quả của phép cộng hai số viết bằng chữ số La Mã: MSM + LXVIII là gì?
a) 1168
b) 1968
c) 2168
đ) 1153
3. Số 301011 có thể tồn tại trong hệ số có cơ số:
a) 2 và 10
b) 4 và 3
c) 4 và 8
d) 2 và 4
4. Số nhị phân 100110 trong hệ thập phân được viết là:
a) 36
b) 38
c) 37
d) 46
5. Lớp 110010 có 2% nữ và lớp 1010 có 2% nam. Có bao nhiêu học sinh trong lớp?
a) 10
b) 20
c) 30
d) 40
6. Có bao nhiêu chữ số của số 1 trong biểu diễn nhị phân của số thập phân 15?
a) 1
b) 2
tại 3
d) 4
7. Phép cộng các số 110 2 và 12 8 là bao nhiêu?
a) 6 10
b) 10 10
c) 10000 2
d) 17 8
8. Ô nhớ của máy tính bao gồm các phần tử đồng nhất gọi là:
a) mã
b) xả thải
c) số
d) hệ số
9. Số bit mà một số có hai byte chiếm giữ là:
a) 8
b) 16
c) 32
d) 64
10. Giá trị sau được nhập vào chữ số dấu của ô đối với số âm:
a) +
b) -
c) 0
d) 1
11. Số thực được biểu diễn trên máy tính dưới dạng:
a) hình thức tự nhiên
b) dạng mở rộng
c) dạng bình thường với mantissa chuẩn hóa
d) ở dạng phân số thông thường
12. Câu nào không phải là câu khẳng định?
a) Không có lý do gì bào chữa cho sự bất lịch sự.
b) Phấn đấu trở thành học sinh giỏi
c) Bản thảo không bị cháy
d) 10112 = 1 2 3 + 0 2 2 + 1 2 1 + 1 2 0
13. Câu nào sai?
quen thuộc v là viết tắt của phép toán logic OR
b) Hoạt động logic HOẶC còn được gọi là phép cộng logic
c) Phép tách còn được gọi là phép cộng logic
d) Quen thuộc v biểu thị phép toán logic kết hợp
14. Với giá trị nào của số X thì câu khẳng định đúng?
((X?
a) 1
b) 2
tại 3
d) 4
15. Biểu thức biểu tượng nào sau đây là đúng:
“NOT (Chữ cái đầu tiên là phụ âm) VÀ KHÔNG (Chữ cái thứ hai là nguyên âm)”?
a)abcde
b) bcade
c) ba ba
d) ca-ba-bốt
16. Một phân đoạn nhất định của Internet bao gồm 1000 trang web. Máy chủ tìm kiếm tự động biên soạn một bảng từ khóa cho các trang web trong phân khúc này. Đây là đoạn của nó:
máy quét - 200
máy in - 250
màn hình - 450
Có bao nhiêu trang web sẽ được tìm thấy theo yêu cầu? máy in | máy quét | màn hình, nếu theo yêu cầu máy in | máy quét 450 trang web được tìm thấy theo yêu cầu máy in và màn hình- 40, và theo yêu cầu máy quét và màn hình - 50?
a) 900
6) 540
c) 460
đ) 810
17. Biểu thức logic nào tương ứng với bảng chân trị sau đây?
A B F
0 0 1
0 1 1
1 0 1
1 1 0
18. Khi máy tính bị hỏng, chủ nhân của nó nói: “RAM không thể hỏng được”. Con trai chủ máy tính cho rằng bộ vi xử lý đã bị cháy nhưng ổ cứng vẫn hoạt động. Kỹ thuật viên bảo trì đến nói rằng rất có thể mọi thứ đều ổn với bộ xử lý, nhưng RAM bị lỗi. Kết quả là hai người trong số họ nói đúng và người thứ ba nói sai. Cái gì bị hỏng?
a) RAM
b) bộ xử lý
c) ổ cứng
d) bộ xử lý và RAM
19. Tại ngã tư xảy ra tai nạn giao thông giữa xe buýt (A), xe tải (D), xe khách (L) và xe buýt nhỏ (M). Những người chứng kiến vụ việc đã đưa ra lời khai sau đây. Nhân chứng đầu tiên cho rằng xe buýt là chiếc đầu tiên đi vào ngã tư, còn chiếc xe buýt nhỏ là chiếc thứ hai. Một nhân chứng khác cho rằng chiếc ô tô cuối cùng đi vào ngã tư là xe tải, còn chiếc thứ hai là xe tải. Nhân chứng thứ ba khẳng định chiếc xe buýt là chiếc thứ hai đi vào ngã tư, theo sau là xe khách. Kết quả là mỗi nhân chứng chỉ đúng một trong những lời khai của họ. Các ô tô đi vào giao lộ theo thứ tự nào? Các phương án trả lời liệt kê các chữ cái đầu tiên của tên các phương tiện liên tiếp không có dấu cách theo thứ tự xuất phát đến giao lộ.
a) AML
b) AGLM
c) GLMA
d) MLGA
giáo trình
| №_TIN TỨC | Bài học |
Bài giảng 1."cơ sở toán học của khoa học máy tính" là gì? Tại sao khoa học máy tính thường được coi giống như Thông tin và mã hóa của nó. Toán học về mật mã. Mã sửa lỗi. Mã hóa kinh tế |
|
| Bài giảng 2 .Mô hình toán học của người biểu diễn chính thức. Xử lý thông tin chính thức là gì? Kết thúc- máy móc mới. Điều gì đến trước: ngôn ngữ hay người biểu diễn? Ngữ pháp của ngôn ngữ. Các ngôn ngữ được công nhận Phiên bản phổ thông teli (Máy Turing, máy Post). |
|
| Bài giảng 3 .Thuật toán và các thuộc tính của nó. Tính không thể quyết định của thuật toán. Khả năng tính toán. Sự phức tạp. | |
| Bài kiểm tra số 1. | |
| Bài giảng 4. Đồ thị. Đồ thị và chữ ghép. Chúng phát sinh trong những nhiệm vụ nào? Các tính chất khác nhau của đồ thị (Eulerian, Hamiltonian) tin tức, tính phẳng, tính lưỡng cực). Mạng. Dòng chảy trong mạng. Biểu diễn đồ thị. Các thuật toán cơ bản trên đồ thị. |
|
| Bài giảng 5. Các mô hình logic trong khoa học máy tínhĐại số của các mệnh đề. Các hàm Boolean. Dạng bình thường. Đầy các lớp hàm Boolean. Sơ đồ tiếp điểm của rơle. Van. Mô hình toán học của bộ xử lý và bộ nhớ máy tính. Vị ngữ và quan hệ. Đại số quan hệ. Cơ sở lý thuyết của DBMS quan hệ. Ngôn ngữ lập trình logic và cơ sở toán học của chúng. |
|
| Bài kiểm tra số 2. | |
| Bài giảng 6. Lý thuyết số máy tính và hình học tính toán. Tại sao lý thuyết số lại cần thiết trong khoa học máy tính? khoa học? Cuộc đua cho số nguyên tố. Làm thế nào để phân tích một số? Sự khác biệt giữa hình học lý thuyết và tin học? Tại sao trên giấy thì mịn nhưng trên máy tính thì lại vụng về? Các quy tắc và thuật toán cơ bản của máy tính hình học. |
|
| 23/2007 | Bài giảng 7. Bảo vệ dữ liệu. Bảo vệ thông tin mang tính biểu tượng. Những gì cần được bảo vệ? Chữ ký điện tử. Hệ thống xác minh. Các hệ mật mã khóa công khai. Bảo vệ thông tin đồ họa. Toán học của hình mờ điện tử. |
| 24/2007 | Bài giảng 8. Những nguyên tắc cơ bản của phương pháp giảng dạy cơ sở toán học của khoa học máy tính. |
| Công việc cuối cùng |
Bài giảng 7. Lý thuyết số máy tính
Lý thuyết số và hình học... Hai nhánh của toán học, từ xa xưa đã mang đến cho nó tinh thần của một trò chơi trí tuệ cao, trong đó vẻ đẹp của các công trình logic ngự trị. Đối với câu hỏi có vẻ ngây thơ và tự nhiên của học sinh, “Công dụng của hình học là gì?” Euclid ra lệnh cho người nô lệ đưa cho người sinh viên một đồng xu và đuổi anh ta đi. “Anh ấy đang tìm kiếm lợi ích trong hình học!” - Euclid phẫn nộ đáp lại.
Sự vô dụng của lý thuyết số đối với nền kinh tế quốc dân dường như càng rõ ràng hơn. Chà, hãy nói cho tôi biết, ai cảm thấy dễ sống hơn sau khi nhận được câu trả lời cho câu hỏi liệu phương trình có nghiệm bằng số tự nhiên hay không? xn + năm = z n, Nếu như N> 2? Nhưng câu hỏi này, được gọi là Bài toán lớn của Fermat, đã khiến các nhà toán học bối rối trong hơn 300 năm. Và ngay cả thực tế đã được Euclid chứng minh rằng có vô số số nguyên tố cũng khó có thể giúp tăng tổng sản phẩm quốc gia.
Máy tính là một vấn đề khác. Điều này chắc chắn là hữu ích. Đúng, có giới hạn. Và số lượng ô nhớ tuy lớn nhưng lại có hạn. Và dung lượng của mỗi ô cũng có hạn. Vì vậy, những con số như hoặc p, do tính vô tỷ của chúng, “không vừa” với máy tính. Làm thế nào bạn có thể nhìn thấy một đường thẳng vô hạn trên màn hình máy tính? Điều gì sẽ xảy ra nếu có hai đường thẳng và nhìn bằng mắt chúng có vẻ song song? Điều gì sẽ xảy ra nếu vẫn còn một điểm giao nhau, nhưng ở một nơi nào đó rất xa?
Hữu hạn và vô hạn, hợp lý và phi lý - đây là những mặt đối lập được trình bày trong toán học một cách sống động, có thể nói, ở dạng trần trụi. Sự phi lý và vô tận mê hoặc, giống như nhìn vào vực sâu không đáy của không gian hay nhìn vào nền tảng của vũ trụ. Đây là thứ không thể tiếp cận được bằng cảm giác mà chỉ phụ thuộc vào lý trí. Và một chiếc máy tính nhỏ, hạn chế, dù mạnh đến đâu, dường như cũng vô dụng ở đây.
Năm 1742, Goldbach, trong một bức thư gửi Euler, đã đưa ra giả thuyết rằng mọi số lẻ, bắt đầu bằng 7, đều có thể được biểu diễn dưới dạng tổng của ba số nguyên tố. Trong gần 200 năm, giải pháp cho vấn đề này vẫn chưa thể thành công. Năm 1934, Viện sĩ I.M. Vinogradov đã chứng minh rằng có một con số nhất định N, sao cho mọi số lẻ lớn hơn N, có thể được biểu diễn dưới dạng tổng của ba số nguyên tố. Hơn nữa, con số này Nđã được tính toán (K. Borozdkin): N = cô ấy 16.038. Nó chỉ có 4.008.659 chữ số. Và không có vô cùng. Chỉ cần kiểm tra câu lệnh cho tất cả các số lẻ nhỏ hơn là đủ N, và bài toán Goldbach sẽ được giải. Tất nhiên, một người không thể làm được điều này. Nhưng thật không may, hệ thống máy tính vẫn chưa đáp ứng được nhiệm vụ này.
Trong nửa sau thế kỷ 20, nhiều định lý lý thuyết số đã được tích lũy, cho rằng mọi thứ đều ổn, bắt đầu từ một thời điểm nhất định. N, I E. ở đó, rất xa, nơi chúng ta không ở. Và than ôi, chúng ta không thể đạt đến giới hạn này chỉ bằng cách sử dụng máy tính. Hóa ra lý thuyết số đã trở thành nguồn cung cấp các bài toán cực kỳ khó cho máy tính về dung lượng bộ nhớ, tốc độ và hiệu quả của các thuật toán đang được phát triển. Ngoài ra, các nhà toán học cần bằng chứng cho thấy chương trình máy tính được tạo ra hoạt động chính xác. Nhưng bạn không thể kiểm tra lại kết quả một cách thủ công. Nó đòi hỏi sự phát triển của các phương pháp rất phức tạp để chứng minh tính đúng đắn của các thuật toán và chương trình (lưu ý rằng nói chung, chúng không giống nhau). Chúng ta đã nói về một số phương pháp này trong Bài giảng 3. Ở đây chúng tôi sẽ cho bạn biết các nhà toán học giúp hạn chế tính vô cực và tính vô tỷ như thế nào.
Có thể nói rằng bài giảng này nói về sự cộng tác giữa toán học thuần túy và khoa học máy tính.
§ 24. Sử dụng máy tính trong nghiên cứu lý thuyết số
Những thảo luận chung ở trên về việc sử dụng các phép tính trên máy tính trong việc chứng minh các phát biểu toán học có lẽ khá minh bạch. Tuy nhiên, có vẻ hữu ích khi xem chúng thực sự trở thành hiện thực như thế nào. Tất nhiên, chúng tôi sẽ không giải quyết vấn đề lý thuyết số nổi tiếng này hay vấn đề lý thuyết số nổi tiếng kia, nhưng sẽ chứng minh điều này bằng cách sử dụng một vấn đề không quá khó.
Bài 1. Có đúng là với mọi chữ số N khác 0 đều tồn tại một số tự nhiên tận cùng bằng chữ số N và nếu di chuyển nó lên đầu số đó thì số đó sẽ tăng N lần?
Tại N= 1, câu trả lời khẳng định là hiển nhiên: bất kỳ số nào được tạo thành từ nhiều hơn 1 đều phù hợp, ví dụ: 11. Còn các giá trị khác thì sao? N?
Có rất ít số khác 0; bạn có thể thử tìm câu trả lời cho từng số đó. Hãy bắt đầu với N= 2. Số có tận cùng là 2, và sau khi di chuyển chữ số này về đầu, bạn sẽ được một số lớn gấp 2 lần, và do đó nó có tận cùng bằng 4. Điều này có nghĩa là số ban đầu kết thúc bằng 42. Sau đó, sau khi di chuyển chữ số 2 vào đầu, bạn sẽ nhận được một số kết thúc bằng 84. Điều này có nghĩa là số ban đầu kết thúc bằng 842. Tiếp tục suy luận, chúng ta thấy rằng số trước đó là 6. Quá trình đã bắt đầu. Nhưng đâu là sự đảm bảo rằng nó sẽ kết thúc?
Nếu người đọc đủ kiên nhẫn, sẽ tin chắc rằng trong trường hợp này một kết thúc có hậu đang chờ đợi mình - đến bước thứ mười bảy, sẽ thu được số 105.263.157.894.736.842, thỏa mãn yêu cầu của bài toán.
Quá trình được mô tả ở trên không khó để lập trình, nhưng phải chờ phản hồi trong bao lâu? Điều gì sẽ xảy ra nếu đối với một số người N Con số đó không tồn tại sao? Sau đó chương trình sẽ chạy mãi mãi 1.
Và một lần nữa chúng ta phải nhờ đến toán học để giúp đỡ. Đầu tiên chúng ta hãy thay đổi một chút điều kiện của bài toán, đề nghị xem xét một tình huống tổng quát hơn 2 .
Bài 2. Biết rằng một số tăng K lần khi chuyển chữ số cuối cùng về đầu. Ở mức K nào thì điều này có thể xảy ra? Với mỗi K như vậy, hãy tìm số nhỏ nhất thỏa mãn điều kiện đã cho.
Trong bài toán này, không giống như Bài toán 1, bản thân số đó không bắt đầu bằng K; Hơn nữa, một số tự nhiên K không nhất thiết phải là một con số.
Giải pháp. Hãy ký hiệu bằng MỘT số gốc, thông qua B- số có được từ MỘT bằng cách chuyển chữ số cuối cùng về đầu. Sau đó K = B/MỘT. Đang xảy ra K= 1 không đáng quan tâm, bởi vì khi đó MỘT = B và số nhỏ nhất, như chúng tôi đã lưu ý, là 11. (Nhân tiện, xin lưu ý rằng trong trường hợp này, chữ số được sắp xếp lại trùng với K.) Vì vậy, trong phần tiếp theo chúng ta sẽ giả sử rằng K 2.
Trước hết, hãy tìm hiểu xem có thể có bao nhiêu chữ số K. Vì những con số B Và MỘT có cùng số chữ số, tỷ lệ BĐẾN MỘT không vượt quá 9. Vì vậy K 9 (tức là chúng ta có thể nói rằng chính K luôn là một “chữ số”).
Cho phép X- chữ số cuối cùng của số MỘT(còn gọi là chữ số đầu tiên của số B), MỘT Y- số được tạo bởi tất cả các chữ số của một số MỘT, ngoại trừ cái cuối cùng. Hãy cũng N- số chữ số trong một số Y. Sau đó MỘT= 10 · Y + X, MỘT B = X· 10 N + Y. Vì vậy, chúng tôi có được sự bình đẳng:
X 10 N + Y = K(10 · Y + X),
.
Mẫu số 10 K– 1 luôn có hai chữ số. Dưới đây là các giá trị cần có:
Dòng thứ ba của bảng này hiển thị giá trị của số nhân ở phía trước nó dưới dạng một phân số tối giản. X Tại N= 1. Điều này có nghĩa là không có chữ số X Tại N= 1 giá trị Y không diễn ra trọn vẹn. Có nghĩa, N 2.
Sự thật là Yđã có hồ sơ N chữ số có nghĩa là 10 N–1 Y< 10N. Từ đây cho X ta nhận được bất đẳng thức kép:
.
Vế trái của bất đẳng thức này có thể dễ dàng chuyển về dạng:
Bởi vì N 2 và K 9, phân số (10 N–1 – K) : (10N – K) dương và nhỏ hơn 1. Xét rằng X là số nguyên thì vế trái của bất đẳng thức có thể viết được K X.
Bây giờ chúng ta giải quyết vế phải của bất đẳng thức này. Các phép biến đổi tương tự chứng tỏ nó bằng nhau
.
Bởi vì K 9 và N 2, phân số 9 K / (10 N – K) dương và nhỏ hơn 1. Xét rằng X- một số nguyên, vế phải của bất đẳng thức có thể được viết X 10K– 1. Tuy nhiên, bất đẳng thức này không cho ta nhiều điều, vì theo điều kiện X và như vậy ít hơn 9.
Vì vậy, chúng tôi phát hiện ra rằng chữ số được di chuyển không thể nhỏ hơn K. Vì vậy, trong Bài toán 1, chúng ta chỉ cần lấy giá trị nhỏ nhất có thể có cho chữ số được di chuyển.
Bây giờ chúng ta hãy giải quyết câu hỏi chính của Vấn đề 2: trong những điều kiện nào? K có một cái gì đó như thế này N con số đó Y nó sẽ còn nguyên vẹn chứ? Nói cách khác, đối với điều gì K tồn tại N, tại đó 10 N – K chia hết cho 10 K- 1? Ở đây chúng ta sẽ sử dụng ý tưởng sau. Để thuận tiện cho việc thảo luận thêm, chúng ta hãy ký hiệu số 10 K– 1 chữ cái tôi. Rõ ràng là số tôi không có ước chung nào ngoài 1 với số 10. Đặc biệt, không có lũy thừa nào của 10 chia hết cho tôi Không một dâu vêt.
Xét dãy lũy thừa của số 10:
1 = 10 0 ; 10 1 ; 10 2 ; 10 3 ; ...; 10m-1,
và thứ tự số dư khi chia các số này cho tôi. Tất cả những số dư này, như đã nói, đều khác không. Tuy nhiên, nhiều số dư khác 0 khi chia cho tôi chỉ một tôi– 1. Điều này có nghĩa là trong dãy lũy thừa này có hai số có cùng số dư khi chia cho tôi. Hãy để nó là 10 Một và 10 b, Ở đâu
0 Một < b tôi– 1. Rồi 10 b – 10 Một chia tôi. Nhưng 10 b – 10 Một = 10 Một
(10 ba– 1), và số tôi không có ước chung không phải đơn vị là số 10. Vì vậy trên tôi trong sản phẩm này số 10 được chia ba– 1. Hãy ký hiệu b – Một bởi vì t.
Như vậy, chúng ta đã chứng minh được rằng có một số mũ dương như vậy t tôi– 1, tức là 10 t– 1 được chia cho tôi. Chúng ta có thể cho rằng tđược chọn là nhỏ nhất với tính chất là 10 t– 1 được chia cho tôi. Nói cách khác, trong số các quyền hạn của 10 1 ; 10 2 ; 10 3 ; ...; 10 t-1 không có số nào chia cho số dư 1 tôi. Và bắt đầu từ ngày 10 t phần còn lại sẽ được lặp lại theo cùng một trình tự. Vậy không có số dư nào khác khi chia cho tôi lũy thừa của số 10, ngoại trừ những lũy thừa trong dãy 1 = 10 0 ; 10 1 ; 10 2 ; 10 3 ; ...; 10 t-1, KHÔNG. ĐẾN tôi số 10 chia N – K, cần phải K có số dư khi chia lũy thừa thích hợp của 10 cho tôi. Và điều này có thể được tìm ra bằng cách xây dựng một thuật toán tuần hoàn đơn giản, vì người ta biết số lũy thừa lớn nhất sẽ phải được xem xét để hiểu liệu phần còn lại cần thiết có xảy ra hay không: không quá tôi– 1. Đây là thuật toán tương ứng:
nhiệm vụ alg_2 ( arg int K)
được cho 2 K 9
cần thiết| in số mũ của số 10,
| cho phần dư K tại
| chia sức mạnh này cho 10K–1.
sự khởi đầu nguyên vẹn X, N
nc Tạm biệt Không(X = K hoặc N = M)
X:= mod(10*X, M)
Cái đó Phần kết luận N
nếu không thì xuất ra"Không có bằng cấp như vậy"
Kết quả của thuật toán này được trình bày trong bảng sau:
Vì không có giá trị chấp nhận được K thuật toán không đưa ra thông báo về sự thiếu vắng mức độ phù hợp, chúng tôi đã chứng minh định lý sau:
Định lý. Với mọi K tự nhiên 9 có một số tăng K lần khi chuyển chữ số cuối cùng về đầu.
Hãy chú ý cách sử dụng máy tính để chứng minh định lý này. Thứ nhất, tính hữu hạn của số lượng tùy chọn cần tìm kiếm đã được chứng minh và thứ hai, bằng cách sử dụng thuật toán được biên dịch, chúng tôi không tìm kiếm chính con số đó mà đang kiểm tra việc đáp ứng một số điều kiện cần và đủ cho sự tồn tại của một số có thuộc tính mong muốn.
Tuy nhiên, bằng cách sử dụng bảng kết quả, có thể dễ dàng chỉ ra các số có thuộc tính bắt buộc - như X cần phải lấy K và sử dụng công thức tính được Yđể tìm số cần tìm ở đó MỘT:
Những người muốn bây giờ có thể có được một bản ghi số MỘT số (ví dụ: khi K= số 5 MỘT= 510 204 081 632 653 061 224 489 795 918 367 346 938 775; và số dài nhất thu được khi K= 6 - nó chứa 58 chữ số).
Lưu ý rằng không phải tất cả các câu trả lời cho bài tập 1 đều là câu trả lời cho bài tập 2 của chúng ta: khi K= 5 (và chỉ với giá trị này K) 3 tồn tại số nhỏ hơn thỏa mãn điều kiện của bài toán. Con số này có được nếu X lấy bằng 7. Khi đó, bạn sẽ cần tìm lũy thừa của số 10, số này dư 5 khi chia không phải cho 49 mà chỉ cho 7. Số mũ của lũy thừa đó là 5. Số cần tìm trong trường hợp này là 10(10 5 – 5) / 7 + 7 = 142,857. Con số này chỉ là “nhỏ” so với số có 42 chữ số ở trên, được lấy làm đáp án cho Bài toán 1.
Tất nhiên, đây chỉ là minh chứng cho thấy máy tính có thể được áp dụng như thế nào để chứng minh một định lý. Trên thực tế, nếu bạn suy nghĩ kỹ hơn một chút, bạn có thể chứng minh khẳng định sau: nếu 10 t– 1 chia hết cho 10 K– 1, rồi 10 t-1 khi chia cho 10 K– 1 nhất thiết phải cho phần còn lại K. Vì vậy, việc chứng minh định lý có thể được thực hiện mà không cần máy tính. Tuy nhiên, ngày nay có một số phát biểu toán học mà chưa thể có được bằng chứng nếu không có máy tính. Đây chỉ là một ví dụ. Người ta đã biết từ lâu (từ thế kỷ 17) và không khó để chứng minh bằng đại số phổ thông rằng số 2 N– 1 chỉ có thể là số nguyên tố nếu chính số đó N Thì đơn giản. Số loại 2 N– 1 thậm chí còn nhận được một cái tên đặc biệt - số Mersenne - theo tên của vị tu sĩ thời Trung cổ, người đã thu hút sự chú ý của các nhà toán học đến những con số 4 này. Thật không may, điều ngược lại không đúng: không phải mọi số có dạng 2 N- 1 khi không hoạt động N Thì đơn giản. Ví dụ như số 2 11 – 1 = 2047 = 23 89 là hợp số. Mặc dù người ta không biết liệu có vô số số nguyên tố Mersenne hay không, nhưng chúng vẫn đóng vai trò là một trong những nguồn gốc của các số nguyên tố lớn ngày nay. Trước khi phát minh ra máy tính, số nguyên tố Mersenne lớn nhất được biết đến là 2127 – 1, có 39 chữ số. Và nói chung nó là số nguyên tố lớn nhất được biết đến vào thời điểm đó. Sự ra đời của máy tính ngay lập tức nâng cao kiến thức của chúng ta về số nguyên tố Mersenne. Ngay trong năm 1952, 5 số nguyên tố đã được phát hiện cùng một lúc: 2.521 – 1; 2 607 – 1; 2 1279 – 1; 2 2203 – 1; 2 2281 – 1. Số cuối có 687 chữ số; Ngay cả đối với các máy tính hiện đại, việc phân tích một con số như vậy là một công việc rất căng thẳng. Cách thoát khỏi tình huống khó khăn này là sử dụng cái gọi là “tiêu chuẩn Luc” để chứng minh tính nguyên tố của số Mersenne. Nó như sau. Đối với số nguyên tố đã chọn R trình tự được xây dựng đệ quy S 1 , S 2 ,S 3 , …, S n, ở đâu S 1 = 4, và S k+1 - số dư khi chia cho số – 2 cho R. Nếu như S p-1 = 0 thì số đó là 2 R– 1 điều đơn giản. Vâng, đối với R= 2281 người ta phải thực hiện các phép tính với số không quá bảy chữ số (vì 2280 2 = 5.198.400) và điều này có thể được thực hiện bằng phép tính số học thông thường nhất trên máy tính. Tình huống này khá giống với tình huống chúng ta gặp phải khi giải bài toán 1 - thay vì tìm số 58 bit khi K= 6, chúng ta đã chọn một dạng viết khác của số đó và thực hiện các phép tính với số không quá hai chữ số.
§ 25. Toán học số học máy tínhỞ đoạn trước, chúng tôi đã đề cập nhiều lần đến những khó khăn trong tính toán máy tính liên quan đến lưới bit giới hạn. Đằng sau những lời này là gì?
Về mặt vật lý, bộ nhớ máy tính là một tập hợp các ô được đánh số. Lần lượt, mỗi ô bao gồm tám thiết bị, mỗi thiết bị có thể ở một trong hai trạng thái. Một trong các trạng thái được mã hóa bằng ký hiệu 0 và trạng thái còn lại bằng ký hiệu 1. Do đó, 1 byte thông tin được đặt trong một ô.
Nội dung của mỗi ô, nếu chúng ta loại bỏ các số 0 đứng đầu có thể có trong đó, có thể được coi là bản ghi của một số tự nhiên trong hệ thống số nhị phân. Trong trường hợp này, mã 00000000 được liên kết với số 0.
Tuy nhiên, ngoài số nguyên dương còn có số nguyên âm. Để biểu thị dấu của một số, cần có một bit khác. Đồng thời, người ta thống nhất rằng giá trị 0 của nó tương ứng với dấu “+” và giá trị duy nhất của nó tương ứng với dấu “-”. Thông thường, bit ngoài cùng bên trái của ô được phân bổ cho dấu. Khi đó mã của số tự nhiên lớn nhất có thể viết trong một ô là 01111111. Nó tương ứng với số thập phân +127. Và mã cho số âm nhỏ nhất là 111111111; trong ký hiệu thập phân nó tương ứng với số –127.
Để tìm tổng của các số 101 2 và 1011 2, với mã của chúng, bạn có thể thực hiện theo các quy tắc cộng số nhị phân: 00000101 + 00001011 = 00010000. Nhưng hãy thử gấp các số 1010101 2 và 111101 2 bằng các quy tắc tương tự sẽ dẫn đến một kết quả lạ: 01010101 + 001111101 = 100100010. Kết quả là số âm!
Mọi người đều rõ ràng: lỗi phát sinh do lưới bit của ô chỉ chứa bảy vị trí. Tuy nhiên, nếu ô có nhiều chữ số hơn thì lỗi như vậy vẫn xảy ra mỗi khi bạn cần tìm tổng các số đủ lớn.
Hiện tượng mô tả ở trên được gọi là hiệu ứng tràn. Và bạn phải nhớ nó khi làm việc với những số nguyên khá lớn.
Bây giờ chúng ta hãy thử cộng một số dương với một số âm. Ví dụ: số 1010 2 với số –101 2. Mã của chúng lần lượt như sau: 00001010 và 10000101. Và kết quả phải là số tự nhiên 101 2. Ngay cả bản thân thuật toán để lấy mã kết quả cũng không dễ dàng để xây dựng (thử làm điều này cho vui) và thậm chí còn hơn thế nữa để triển khai một thiết bị đơn giản có thể thực thi thuật toán này. Nhưng máy tính phải thực hiện phép cộng khá thường xuyên nên mọi việc phải đơn giản và nhanh nhất có thể.
Để làm cho phép cộng đơn giản hơn và không phụ thuộc vào dấu của các số hạng, các số nguyên âm được mã hóa theo một cách khác. Nhưng trước tiên, hãy nói về số không.
Điều gì xảy ra nếu bạn cố gắng viết số tự nhiên 100000000 2 vào một ô 8 bit? Tất cả tám chữ số sẽ là số không. Điều này có nghĩa là máy tính coi số này là 0. Đây là số chúng ta sẽ sử dụng. Trừ 101 2 từ số 100000000 2. Kết quả là 11111011 2. Nếu bây giờ chúng ta cộng số này với số 101 2 thì máy tính sẽ nhận kết quả là 0. Do đó, việc khai báo số 11111011 2 làm mã cho số âm –101 2 là điều đương nhiên. Anh ấy được gọi mã bổ sungđã cho số âm.
Hãy nói về một mã riêng biệt. Hãy xem xét mã 10000000. Đầu tiên, nó là mã số âm vì chữ số ngoài cùng bên trái là 1. Máy tính coi nó như một mã bổ sung. Khi đó mã trực tiếp của số dương đối diện với nó trùng với hiệu 100000000 2 – 10000000 2. Nó bằng 10000000, tức là 128 10. Do đó, số âm nhỏ nhất có thể được ghi vào ô 8 bit là –128.
Mã cho số 0 là 00000000. Điều gì xảy ra nếu bạn viết mã bổ sung cho số –0? Trừ 0 2 từ 100000000 2 và nhận được 10000000 2 . Khi ghi vào một ô, nó lại sẽ là 00000000. Vì vậy, máy tính cũng như bạn và tôi, không phân biệt giữa các số +0 và –0.
Tất nhiên, để tính phần bù của số âm N bạn có thể trừ 2 mô đun số từ 100000000 mỗi lần N. Nhưng có một cách khác. Đây là những gì bạn có thể làm để có được phần bù của số âm:
1. Viết mã nhị phân của mô đun của số.
2. Trong bản ghi thu được, thay mỗi chữ số 1 bằng số 0 và mỗi chữ số 0 bằng số 1.
3. Thêm 1 vào mã kết quả, được coi là số tự nhiên trong hệ nhị phân.
Như bạn có thể thấy, việc xây dựng mã bổ sung rất dễ dàng. Và vì phép trừ có thể được thay thế bằng phép cộng với số đối diện, nên việc chuyển sang mã bù của phần bù cho phép bạn thực hiện mà không cần thực hiện phép trừ hoàn toàn.
Tất nhiên, phạm vi từ –128 đến +127 trong nhiều trường hợp là quá nhỏ để giải quyết các vấn đề mới nổi. Nhưng không nhất thiết phải lưu trữ một số nguyên trong chính xác một ô 8 bit. Thông thường, hai ô được phân bổ cho số nguyên - đây chính xác là điều xảy ra nếu bạn khai báo loại biến là Số nguyên. Nếu bạn khai báo kiểu LongInt thì 4 ô 8 bit sẽ được phân bổ cho số nguyên. Nhưng một ô sẽ được phân bổ nếu loại ShortInt được khai báo.
Nếu hai ô được phân bổ để ghi một số thì chúng được coi là một tổng thể duy nhất. Nguyên tắc mã hóa giống nhau: chữ số ngoài cùng bên trái dùng làm dấu của số, mười lăm chữ số còn lại dùng làm mã giá trị tuyệt đối của số đó. Đối với số dương nó được sử dụng mã trực tiếp, đối với những cái tiêu cực - bổ sung. Như vậy, phạm vi của các số nguyên là: từ –32,768 đến +32,767 = 2 15 – 1.
Ở tất cả, nếu được sử dụng để viết số nguyên tôi-bit mã nhị phân thì phạm vi số được mã hóa là từ –2 tôi-1 đến 2 tôi–1 – 1, với mã bổ sung là số âm N từ phạm vi này trùng với biểu diễn nhị phân của số 2 tôi + N.
Rõ ràng là khi nhân các số nguyên, hiệu ứng tràn còn xảy ra thường xuyên hơn. Máy tính phản ứng thế nào với điều này? Tràn điểm cố định không làm gián đoạn bộ xử lý. Tùy thuộc vào ngôn ngữ được sử dụng, chẩn đoán có thể không có (ví dụ: điều này xảy ra khi sử dụng hầu hết các phiên bản của ngôn ngữ Turbo Pascal), có thể thông báo cho người dùng về sự kiện này và chờ phản ứng của anh ta hoặc có thể chỉ đơn giản là tiến hành viết dấu phẩy động số (điều này xảy ra trong các phiên bản khác nhau của ngôn ngữ BASIC).
Tất nhiên, ngoài số nguyên, người ta còn tích cực sử dụng phân số. Và bất kỳ số thực nào cũng có thể được viết dưới dạng phân số thập phân hữu hạn hoặc vô hạn. Tuy nhiên, cách biểu diễn như vậy thường chỉ cần thiết trong các cấu trúc lý thuyết. Nhưng trong thực tế...
Trong thực tế, trong hầu hết các trường hợp, người ta phải xử lý các giá trị gần đúng của đại lượng. Các giá trị gần đúng phát sinh trong quá trình đo, khi tính toán số lượng lớn và trong nhiều trường hợp khác. Do đó, một nhà nghiên cứu hoặc kỹ sư, khi giải quyết một vấn đề cụ thể, ban đầu phải ước tính xem trong quá trình tính toán của mình sẽ có bao nhiêu con số quan trọng và bao nhiêu con số sẽ còn lại trong kết quả. Nhưng điều này thường được thảo luận trong các khóa học toán. Bây giờ chúng tôi muốn thu hút sự chú ý của bạn đến một cái gì đó khác.
Giả sử người ta quyết định rằng ba chữ số có nghĩa là đủ. Sau đó, về số lượng, chẳng hạn như 37.200.000; –372; 3,72; 0,000372 chúng ta chỉ cần biết ba chữ số này và chúng được viết từ vị trí thập phân nào. Đây chính xác là thông tin cần được cung cấp cho máy tính. Để làm điều này, hãy trình bày các số một cách thống nhất: chúng ta viết 0 (và trước nó là dấu “-” nếu số âm), sau đó là dấu phẩy, ngay sau dấu phẩy chúng ta viết các chữ số có nghĩa và nhân phân số thập phân thu được với lũy thừa thích hợp của 10. Đây là kết quả chúng ta nhận được cho bốn số trên:
37.200.000 = 0,372 ·10 8;
–372 = –0.372 · 10 3 ;
3,72 = 0,372 · 10 1;
0,000372 = 0,372 10 –3.
Rõ ràng là giá trị tuyệt đối của bất kỳ số nào cũng có thể được biểu diễn dưới dạng tích của một số từ 0,1 đến 1 và lũy thừa của 10 với số mũ là số nguyên. Phần phân số của thừa số đầu tiên trong biểu diễn này được gọi là lớp phủ số và số mũ của số 10 là theo thứ tự những con số. Sự biểu diễn của một số dưới dạng tích như vậy được gọi là ký hiệu chuẩn hóa những con số. Một tên khác cho cách biểu diễn số này là viết số dấu phẩy động. Số chữ số tối đa được phép trong phần định trị của một số xác định độ chính xác mà số đó có thể được biểu thị.
Trong máy tính, các số được biểu diễn dưới dạng hệ thống số nhị phân. Đối với hệ nhị phân, dạng chuẩn hóa của một số là biểu diễn của nó dưới dạng ± tôi·2 P, trong đó 0,1 2 tôi < 1, а R- một số nguyên. Ví dụ,
0,1 10 = 0,0(0011) 2 = 0,11(0011) 2 –3.
Một số dấu phẩy động có thể chiếm một số byte khác nhau trong bộ nhớ máy tính. Như người ta nói, để viết một số với độ chính xác thông thường, 4 byte được phân bổ và các số có độ chính xác kép chiếm 8 byte. Tuy nhiên, tùy thuộc vào thiết kế của máy tính, có các tùy chọn khác, chẳng hạn như khi 10 byte được phân bổ để ghi một số.
Trong hầu hết các trường hợp thực tế, cái được gọi là độ chính xác thông thường khi biểu diễn số thực là khá đủ. Vì vậy, chúng tôi sẽ chỉ xem xét thêm trường hợp này. Trong đó ký hiệu số và thứ tự được gán
1 byte và đây là 8 bit đầu tiên. 24 bit còn lại được phân bổ cho phần định trị. Ví dụ, điều này có nghĩa là phần định trị của biểu diễn máy tính của số 0,1 10 sẽ như sau:
110011001100110011001101
Dấu của một số được mã hóa theo cách thông thường: “cộng” được mã hóa bằng ký hiệu 0, “trừ” bằng ký hiệu 1. Về thứ tự của số, cái gọi là đặt hàng máy. Nó có bảy bit và bằng một số nguyên không âm mà mã này là mã nhị phân trực tiếp. Ví dụ: mã 0101011 tương ứng với thứ tự máy 43. Thứ tự máy liên quan đến thứ tự số như sau:
số thứ tự = thứ tự máy – 2 6 .
Do đó, chuỗi 0101011 là mã thứ tự bằng –21. Và dãy 0000000 mã hóa thứ tự –64. Dễ dàng nhận thấy thứ tự 0 được mã hóa là 1000000. Thứ tự dương cao nhất được mã hóa 1111111 và bằng 63.
Đây là mã máy tính hoàn chỉnh cho số 0,1 10 trông như thế nào:
Chúng ta hãy lưu ý một lần nữa rằng việc biểu diễn số dấu phẩy động trong bộ nhớ máy tính có thể được thực hiện rất khác nhau - tùy thuộc vào ngôn ngữ lập trình, đặc điểm kiến trúc
vân vân. Ví dụ: trong một số ngôn ngữ, chỉ một byte được phân bổ cho phần định trị và ký hiệu của số được viết dưới phần định trị chứ không được đặt ở chữ số ngoài cùng bên trái. Ở đây chúng tôi chỉ trình bày những nguyên tắc cơ bản để biểu diễn những con số đó.
Bây giờ chúng ta hãy xem xét việc thêm các số dấu phẩy động. Nếu các số ở dạng chuẩn hóa có cùng thứ tự, thì việc cộng phần trị giá của các số này là đủ, sau đó chuẩn hóa kết quả thu được nếu tổng này lớn hơn 1 hoặc nhỏ hơn 0,1. Ví dụ,
Mặc dù các ví dụ được đưa ra trong hệ thống số nhị phân, rõ ràng là quy tắc đã nêu áp dụng cho bất kỳ hệ thống vị trí nào.
Nếu thứ tự của các số chuẩn hóa khác nhau thì khi cộng các số dấu phẩy động, hoạt động sắp xếp các đơn đặt hàngđiều kiện. Lưu ý rằng giá trị của số không thay đổi khi phần định trị được dịch chuyển sang bên phải một chữ số với mức tăng đồng thời theo thứ tự là 1. Do đó, trong số hạng có thứ tự thấp hơn, phần định trị được dịch chuyển sang bên phải bởi hiệu giữa các đơn hàng, sau đó phần định trị được thêm vào và kết quả được chuẩn hóa lại. Ví dụ,
Điều này có nghĩa là chúng ta có thể xây dựng quy tắc sau để cộng các số có dấu phẩy động.
Việc nhân và chia số ở dạng chuẩn hóa sẽ dễ dàng hơn nhiều.
Ví dụ,
0,101 · 2 –3 · 0,1011 · 2 4 = (0,101 · 0,1011) · 2 –3+4 = 0,0110111 · 2 1 = 0,110111 · 2 0 .
Ví dụ,
0,1011 · 2 –3: 0,101 · 2 4 = (0,1011: 0,101) · 2 –3–4 = 1,0001100110011... · 2 –7 = =0,10001100110011... · 2 –6.
Ví dụ cuối cùng cho thấy rằng trong thực tế, ngay cả với những phép tính thông thường, chúng ta sẽ buộc phải hài lòng với giá trị gần đúng của phân số. Trong máy tính, lưới bit giới hạn còn đóng vai trò lớn hơn. Ví dụ, chúng ta cộng các số Một= 0,1 2 13 và b= 0,1 · 2 –12. Sau khi sắp xếp thứ tự ta được:
Nhưng chỉ có 24 chữ số phù hợp với lưới bit cho phần định trị chứ không phải 26. Do đó, hai chữ số cuối cùng sẽ bị mất và kết quả sẽ trùng với phần bổ sung đầu tiên. Hoá ra là trong “số học máy tính” có thể có Một + b = Một, Mặc dù b 0. Và đây không phải là tính năng duy nhất của số học máy tính. Nhiệm vụ 15 cung cấp một ví dụ cho thấy rằng luật kết hợp để bổ sung có thể không giữ.
Khi nhân và chia các số đã chuẩn hóa, một tác động có thể xảy ra là làm tràn lưới bit theo thứ tự của số đó. Đây là một ví dụ:
0,1001 · 2 32 · 0,11 · 2 33 = 0,011011 · 2 65 = 0,11011 · 2 64.
Nhưng bậc cao nhất có thể là 63. Do đó, kết quả này không thể biểu diễn được trong số học máy tính. Thông thường, hệ điều hành hoặc trình biên dịch ngôn ngữ lập trình trong trường hợp này sẽ đưa ra chẩn đoán "tràn". Tuy nhiên, tình trạng tràn số đã chuẩn hóa cũng có thể xảy ra trong quá trình cộng; trong nhiệm vụ 17 bạn được yêu cầu xây dựng một ví dụ tương ứng.
Ngoài các trường hợp đã nêu ở trên, khi tính toán trên máy tính cho ra kết quả sai hoặc không có kết quả nào, người ta phải lưu ý đến tác dụng của việc làm tròn số. Những ảnh hưởng này cũng là do tính chất hạn chế của lưới xả. Một trong số đó là mất đi những con số đáng kể. Lấy ví dụ các số 1/1000 và 1/1004. Trong hệ thống số nhị phân ở dạng chuẩn hóa, có tính đến việc làm tròn, chúng tương ứng bằng 0,100000110001001001101111 · 2 –9 và 0,100000101000110010110000 · 2 –9. Sau khi trừ, chúng ta nhận được 0,1000010110111111 · 2 –17. Sự khác biệt chính xác là 4/1004000. Khi được viết ở dạng chuẩn hóa với lớp định trị 24 bit, chúng ta thu được 0,100001011010111011101100 · 2 –17. Như bạn có thể thấy, chỉ có 11 chữ số thập phân đầu tiên là chính xác.
Vì vậy, số học máy tính có thể tạo ra các hiệu ứng sau:
1) lỗi làm tròn xảy ra khi viết số làm tròn và có thể tích lũy trong quá trình thực hiện các phép tính;
2) tràn lưới bit theo thứ tự số dẫn đến thu được một số không thể sao chép được trong máy tính;
3) mất các chữ số có nghĩa khi trừ các số gần nhau hoặc khi lưới bit của lớp phủ tràn;
4) bỏ qua thuật ngữ có sự khác biệt lớn về thứ tự.
Theo khuyến nghị thực tế, hãy lưu ý rằng đối với các số thực được biểu diễn trong máy tính ở dạng chuẩn hóa, bạn không nên so sánh chúng để có sự bằng nhau chính xác; thay vào đó, người ta phải so sánh giá trị tuyệt đối của hiệu của chúng với một số dương nhỏ phù hợp tương ứng với sai số biểu diễn.
Câu hỏi và nhiệm vụ1. Nguyên nhân chính dẫn đến những tác động khác nhau của phép tính số học trên máy tính là gì?
2. Mã bổ sung là gì? Lợi ích của việc sử dụng mã bổ sung là gì?
3. Phạm vi số nguyên mà 4 ô được sử dụng để mã hóa là bao nhiêu?
4. Tràn nước có tác dụng gì?
5. Giải thích tại sao phương pháp được đưa ra trong phần giải thích của đoạn văn thực sự đưa ra một mã bổ sung cho số âm.
6. a) Các số nguyên sau được viết bằng mã 8 bit trực tiếp: 01101010; 10111011; 10001001; 01010111; 11111111. Tìm các số âm trong số chúng và viết chúng dưới dạng mã bù hai.
b) Các số sau được viết bằng mã 16 bit trực tiếp:
Tìm các số âm trong số đó và viết chúng dưới dạng mã bù hai.
7. a) Thực hiện phép cộng các số 100 10 và 50 10 trong mã số nguyên dấu phẩy cố định một byte. Kết quả sẽ là mã số nào (trong hệ thập phân)? (Gợi ý: Hãy nhớ rằng số âm được biểu diễn dưới dạng số bù hai.)
b) Thực hiện phép cộng các số –80 10 và –64 10 trong mã số nguyên dấu phẩy cố định 1 byte. Kết quả sẽ là mã số nào (trong hệ thập phân)?
8. Tại sao luật tổ hợp có thể bị vi phạm trong quá trình cộng các số nguyên trên máy tính?
(Một + b) + c = Một + (b + c)? Đưa ra một ví dụ phù hợp để hỗ trợ câu trả lời của bạn.
9. Ký hiệu nào của một số được gọi là chuẩn hóa? Phần định trị và thứ tự của một số là gì?
10. Ký tự đầu tiên của mã lệnh máy của một số sẽ là gì nếu thứ tự của số được biểu diễn ở dạng chuẩn hóa nhị phân là không âm?
11. Văn bản giải thích của đoạn chứa một bản ghi bốn byte của số 0,1 10 trong bộ nhớ máy tính.
a) Mục này thực sự đại diện cho số thập phân nào?
b) Sai số tuyệt đối và tương đối khi biểu diễn số 0,1 10 là gì?
c) Giải thích tại sao chữ số cuối cùng của phần định trị là 1.
12. Cho biết số thực nào sau đây có thể được biểu diễn trong bộ nhớ máy tính bằng mã dấu phẩy động 4 byte được mô tả trong phần giải thích.
13. Thực hiện phép cộng các số nhị phân ở dạng chuẩn hóa. Bình thường hóa kết quả.
14. Thực hiện phép nhân các số nhị phân biểu diễn dưới dạng chuẩn hóa. Bình thường hóa kết quả.
15. Sử dụng các quy tắc số học trên máy tính, tính các số
Đảm bảo rằng luật kết hợp bị vi phạm đối với những con số này.
16. Giải thích tại sao có thể vi phạm luật tổ hợp khi nhân các số có dấu phẩy động. Cung cấp các ví dụ hỗ trợ.
17. Cho ví dụ về hai số nhị phân chuẩn hóa có thể tràn khi cộng.
18. Để giải một bài toán nào đó, Petya đã biên soạn thuật toán sau:
alg Số tiền1 ( tranh luận nguyên vẹn N, độ phân giải đồ đạc :S)
sự khởi đầu nguyên vẹn : K
đầu vào N
nc Vì K từ 1 trước N
Phần kết luận S
Đổi lại, Kolya đã biên soạn thuật toán sau để giải quyết vấn đề tương tự:
alg Sum2 ( tranh luận nguyên vẹn N, độ phân giải đồ đạc :S)
sự khởi đầu nguyên vẹn : K
đầu vào N
nc Vì K từ N trước 1 Với bước chân –1
kts
Phần kết luận S
a) Có đúng là cả hai thuật toán đều giải quyết được cùng một vấn đề không?
b) Có đúng là khi N= 1.000.000.000 liệu các chương trình thực hiện các thuật toán này có cho kết quả tương tự nếu sử dụng biểu diễn bốn byte của các số chuẩn hóa được mô tả trong văn bản của đoạn văn không?
1 Tất nhiên, nó sẽ không hoạt động mãi mãi - hoặc bộ nhớ máy tính sẽ tràn khi tính toán ngày càng nhiều số mới, hoặc Chubais sẽ tắt đèn...
2 Kỹ thuật này khá nổi tiếng với các nhà toán học nhưng hiếm khi được sử dụng trong lập trình.
3 Nhân tiện, bằng chứng của phát biểu này là đối với các giá trị khác K không có lời giải nào của bài toán 2 mà không trùng với lời giải của bài toán 1 - tác giả bài viết không thể có được nếu không có máy tính.
4 Tuy nhiên, lịch sử toán học cũng có nhiều chỗ trống như bất kỳ lịch sử nào khác. Một số nhà nghiên cứu tin rằng người Pythagore đã quan tâm đến số nguyên tố Mersenne liên quan đến cái gọi là “số hoàn hảo”.
Bài kiểm tra khoa học máy tính Cơ sở toán học của khoa học máy tính dành cho học sinh lớp 8. Bài kiểm tra có 20 câu hỏi. Có đáp án ở cuối bài thi.
1. Tập hợp các dấu hiệu dùng để viết số được gọi là:
a) hệ thống số
b) số của hệ thống số
c) bảng chữ cái của hệ thống số
d) cơ sở của hệ thống số
2. Kết quả của phép cộng hai số viết bằng chữ số La Mã: MSM + LXVIII là gì?
a) 1168
b) 1968
c) 2168
đ) 1153
3. Số 301011 có thể tồn tại trong hệ thống số có cơ số:
a) 2 và 10
b) 4 và 3
c) 4 và 8
d) 2 và 4
4. Số nhị phân 100110 trong hệ thập phân được viết là:
a) 36
b) 38
c) 37
d) 46
5. Lớp 110010 có 2% nữ và 1010 2% nam. Có bao nhiêu học sinh trong lớp?
a) 10
b) 20
c) 30
d) 40
6. Có bao nhiêu chữ số của 1 trong biểu diễn nhị phân của số thập phân 15?
a) 1
b) 2
tại 3
d) 4
7. Kết quả của việc cộng các số 110 2 và 12 8 là gì?
a) 6 10
b) 10 10
c) 10000 2
d) 17 8
8. Một ô nhớ máy tính bao gồm các phần tử đồng nhất được gọi là:
a) mã
b) xả thải
c) số
d) hệ số
9. Số bit bị chiếm bởi một số có hai byte là:
a) 8
b) 16
c) 32
d) 64
10. Thông tin sau được nhập vào chữ số dấu của ô cho số âm:
a) +
b) -
c) 0
d) 1
11. Số thực được biểu diễn trên máy tính dưới dạng:
a) hình thức tự nhiên
b) dạng mở rộng
c) dạng bình thường với mantissa chuẩn hóa
d) ở dạng phân số thông thường
12. Câu nào không phải là câu khẳng định?
a) Không có lý do gì bào chữa cho sự bất lịch sự.
b) Phấn đấu trở thành học sinh giỏi
c) Bản thảo không bị cháy
d) 1011 2 = 1 x 2 3 + 0 x 2 2 + 1 x 2 1 + 1 x 2 0
13. Tuyên bố nào là sai?
quen thuộc v biểu thị một hoạt động logic HOẶC
b) Hoạt động logic HOẶC còn được gọi là phép cộng logic
c) Phép tách còn được gọi là phép cộng logic
d) Quen thuộc v biểu thị phép toán logic kết hợp
14.
Với giá trị nào của số X thì phát biểu đúng?
((X?
a) 1
b) 2
tại 3
d) 4
15.
Với biểu thức biểu tượng nào thì mệnh đề là đúng:
“NOT (Chữ cái đầu tiên là phụ âm) VÀ KHÔNG (Chữ cái thứ hai là nguyên âm)”?
a)abcde
b) bcade
c) ba ba
d) ca-ba-bốt
16.
Một số phân đoạn của Internet bao gồm 1000 trang web. Máy chủ tìm kiếm tự động biên soạn một bảng từ khóa cho các trang web trong phân khúc này. Đây là đoạn của nó:
máy quét - 200
máy in - 250
màn hình - 450
Có bao nhiêu trang web sẽ được tìm thấy theo yêu cầu? máy in | máy quét | màn hình, nếu theo yêu cầu máy in | máy quét 450 trang web được tìm thấy theo yêu cầu máy in và màn hình- 40, và theo yêu cầu máy quét và màn hình - 50?
a) 900
6) 540
c) 460
đ) 810
17. Biểu thức logic nào tương ứng với bảng chân lý sau?
A B F
0 0 1
0 1 1
1 0 1
1 1 0
18. Khi máy tính bị hỏng, chủ nhân của nó đã nói: “RAM không thể hỏng được”. Con trai chủ máy tính cho rằng bộ vi xử lý đã bị cháy nhưng ổ cứng vẫn hoạt động. Kỹ thuật viên bảo trì đến nói rằng rất có thể mọi thứ đều ổn với bộ xử lý, nhưng RAM bị lỗi. Kết quả là hai người trong số họ nói đúng và người thứ ba nói sai. Cái gì bị hỏng?
a) RAM
b) bộ xử lý
c) ổ cứng
d) bộ xử lý và RAM
19. Tại ngã tư đã xảy ra một vụ tai nạn giao thông liên quan đến xe buýt (A), xe tải (D), xe khách (L) và xe buýt nhỏ (M). Những người chứng kiến vụ việc đã đưa ra lời khai sau đây. Nhân chứng đầu tiên cho rằng xe buýt là chiếc đầu tiên đi vào ngã tư, còn chiếc xe buýt nhỏ là chiếc thứ hai. Một nhân chứng khác cho rằng chiếc ô tô cuối cùng đi vào ngã tư là xe tải, còn chiếc thứ hai là xe tải. Nhân chứng thứ ba khẳng định chiếc xe buýt là chiếc thứ hai đi vào ngã tư, theo sau là xe khách. Kết quả là mỗi nhân chứng chỉ đúng một trong những lời khai của họ. Các ô tô đi vào giao lộ theo thứ tự nào? Các phương án trả lời liệt kê các chữ cái đầu tiên của tên các phương tiện liên tiếp không có dấu cách theo thứ tự xuất phát đến giao lộ.
