GAC024 Toán học Rời rạc

Một thành viên được lặp lại được tính là một, carry nhị phân có thể vượt quá độ rộng cố định, và tuyến đường ít cạnh nhất có thể không có trọng số nhỏ nhất. Toán học rời rạc làm rõ những quy tắc đó.

GAC024 bao gồm các tập hợp, hệ đếm, logic nhị phân, thuật toán và mạng lưới. Yêu cầu hiện tại của trung tâm bạn sẽ xác định các bài đánh giá, công cụ, tỷ trọng và hạn chót. Các trang thực hành gốc này không thiết lập quy tắc chấm điểm chính thức hay quyết định tín chỉ đại học.

Xác định vũ trụ, độ rộng biểu diễn, đầu vào được phép hoặc giả thuyết đồ thị trước khi giải. Trình bày đủ bước giải để người đọc khác có thể tái tạo kết quả và phân biệt mô hình toán học với triển khai thực tế của nó.

• Một tập hợp là một tập hợp các đối tượng phân biệt. Thứ tự và sự lặp lại không quan trọng.
• Hợp $A \cup B$ là tất cả những gì thuộc về ít nhất một trong hai; giao $A \cap B$ là những gì nằm trong cả hai; bù của tập hợp là tất cả những gì nằm trong vũ trụ đã nêu nhưng nằm ngoài tập hợp.
• Một tập con có tất cả các phần tử nằm bên trong một tập hợp khác.
• Một liên hệ ghép cặp các phần tử của hai tập hợp. Một hàm số là liên hệ mà mỗi đầu vào thuộc miền xác định đã cho đều có đúng một đầu ra. Các đầu vào khác nhau có thể chia sẻ cùng một đầu ra; một liên hệ nghịch đảo chỉ là hàm số khi các đầu ra xác định duy nhất các đầu vào tương ứng.
• Một sơ đồ Venn chuyển bài toán tập hợp thành hình ảnh, và có thể hiển thị các vùng rời rạc cũng như số lượng của chúng. Kiểm tra xem tổng các vùng này có bằng tổng số phần tử của vũ trụ đã cung cấp hay không.

Nguyên lý đếm bù trừ trừ đi phần giao bị đếm trùng hai lần đi một lần: $|A\cup B|=|A|+|B|-|A\cap B|$.

Ví dụ minh họa. trừ phần giao chỉ một lần

Đã biết: 30 học sinh, 18 học tiếng Pháp, 15 học tiếng Đức, và 7 học cả hai. Phần giao nằm trong tổng số của cả hai môn học.

Chỉ học tiếng Pháp là $18-7=11$ và chỉ học tiếng Đức là $15-7=8$. Bốn vùng rời rạc cộng lại bằng 30.

Phiếu bài tập 4.1 bao gồm các bài toán tăng dần độ khó và lời giải đã được kiểm tra độc lập.

• Một căn bậc b theo vị trí sử dụng các chữ số từ 0 đến b trừ 1 và trọng số vị trí $b^i$. Thập phân dùng mười, nhị phân hai, thập lục phân sixteen.
• Giá trị của mỗi chữ số chính là trọng số vị trí của nó: trong nhị phân, các vị trí là 1, 2, 4, 8, 16 v.v.
• Hệ thập phân chia (hexadecimal) là cách viết tắt của nhị phân: mỗi chữ số hex đúng bằng bốn bit, vì vậy phép chuyển đổi có thể nhóm một mẫu nhị phân có độ rộng xác định thành các khối bốn bit. Các số zero dẫn đầu giữ nguyên độ rộng trong khi để lại giá trị không dấu không thay đổi.

Đối với n bit vô hướng, các giá trị chạy từ 0 đến $2^n-1$. Phân biệt tổng không giới hạn với kết quả lưu trữ có độ rộng cố định; nếu quy tắc tràn (wraparound) được nêu rõ, nó sẽ giữ lại n bit thấp nhất.

Ví dụ minh họa. trọng số vị trí xác định giá trị thập phân

Số đã biết $1101_2$. Sử dụng trọng số từ phải sang trái: 1, 2, 4 và 8.

Cùng một giá trị là D trong hệ thập phân chia. Các số zero dẫn đầu sẽ không thay đổi giá trị không âm này nhưng có thể ghi lại độ rộng mong muốn.

Phiếu bài tập 4.2 bao gồm các bài toán tăng dần độ khó và lời giải đã được kiểm tra độc lập.

• Phép toán nhị phân cộng giống như thập phân, mang số khi đạt 2 thay vì 10.
• Một bit là một chữ số nhị phân; một byte là tám bit.
• Đại số Boole làm việc với TRUE (đúng) và FALSE (sai) với các phép AND, OR và NOT.
• Một bảng chân lý liệt kê mọi tổ hợp đầu vào Boolean và đầu ra tương ứng. Việc khớp từng hàng chứng minh tính tương đương cho cùng một tập đầu vào Boolean hữu hạn; nó không chứng minh thời gian hoạt động của mạch vật lý hay bảo mật của hệ thống thực tế.
• Các cổng logic thực hiện các thao tác đã nêu, và một mạch logic kết nối chúng. Theo dõi logic trừu tượng theo các kết nối và quy ước đầu vào của nó.

Sử dụng OR bao hàm và ngoặc đơn rõ ràng. De Morgan cho $\neg(A\land B)=(\neg A)\lor(\neg B)$. Phép NOT theo bit chỉ đảo ngược độ rộng đã nêu, chứ không phải biểu diễn vô hạn không xác định.

Ví dụ minh họa. đầu ra OR bị đảo bởi NOT

Đã biết: $Y=\neg(A\lor B)$. OR bao hàm chỉ sai khi cả hai đầu vào đều sai; NOT đảo ngược kết quả đó. Theo thứ tự dòng $(A,B)=(0,0),(0,1),(1,0),(1,1)$, cột đầu ra là 1, 0, 0, 0. De Morgan cho biểu thức tương đương $(\neg A)\land(\neg B)$.

Phiếu bài tập 4.3 bao gồm các bài toán tăng dần độ khó và lời giải đã được kiểm tra độc lập.

• Một thuật toán mô tả các bước không mơ hồ cho một nhiệm vụ. Một thủ tục giải quyết nhiệm vụ hữu hạn đã cho phải dừng lại và đưa ra kết quả yêu cầu cho các đầu vào được phép.
• Một sơ đồ luồng vẽ nó: một quyết định là hình thoi, một quy trình là hình chữ nhật.
• Pseudocode biểu diễn các bước của nó mà không đòi hỏi ngôn ngữ triển khai cụ thể. Xác định quy ước gán biến, cận vòng lặp và chỉ số trước khi thực hiện theo dõi.
• Theo dõi một thuật toán — một bảng có một cột cho mỗi biến và một hàng cho mỗi bước — ghi lại các cập nhật thực tế của nó. Một bản theo dõi kiểm tra đầu vào đã chọn; một tuyên bố áp dụng cho tất cả các đầu vào được phép cũng cần một lập luận về tính đúng đắn.
• Hiệu suất rất quan trọng: tìm kiếm tuyến tính có thể dừng sớm nhưng có thể phải kiểm tra tất cả n mục. Tìm kiếm nhị phân liên tục loại bỏ một nửa khoảng tìm kiếm đã sắp xếp; số phép so sánh logarit của nó đòi hỏi dữ liệu đã sắp xếp và các quy ước cận.

Ví dụ minh họa. lặp lại bước lấy dư cho đến khi số thứ hai bằng 0

Đã biết: bắt đầu với các số nguyên dương a bằng 10 và b bằng 6. Trong khi b khác không, tính r = a MOD b, sau đó đặt a = b và b = r. Các cặp sau khi hoàn thành các vòng lặp là (6,4), (4,2), (2,0), cho ra kết quả output là 2. Giá trị tạm thời r lưu giữ phần dư trước khi a và b thay đổi. Mỗi phần dư khác không đều nhỏ hơn b dương trước đó, hỗ trợ quá trình kết thúc.

Phiếu bài tập 4.4 bao gồm các bài toán tăng dần độ khó và lời giải đã được kiểm tra độc lập.

• Một đồ thị là một tập hợp các đỉnh được nối bởi các cạnh. Nó mô phỏng bất cứ điều gì có kết nối: đường sá, tình bạn, phụ thuộc lẫn nhau.
• Đối với đồ thị vô hướng đơn giản không có vòng lặp hoặc cạnh trùng, bậc đếm số cạnh kề. Mỗi cạnh đóng góp hai vào tổng bậc.
• Một cây là đồ thị liên thông không có chu trình, và một cây hữu hạn với n đỉnh có n trừ 1 cạnh. Một số mô hình phân cấp sử dụng cây, nhưng các hệ thống thực tế cũng có thể chứa các liên kết chéo hoặc chu trình.
• Một bài toán đường đi ngắn nhất yêu cầu tìm tuyến đường có chi phí thấp nhất giữa hai đỉnh, dựa trên tổng trọng số theo các ràng buộc đã cho, chứ không chỉ dựa vào số lượng cạnh. Thay vào đó, một cây bao trùm tối thiểu (minimum spanning tree) kết nối mọi đỉnh mà không tạo thành chu trình và tối thiểu hóa tổng trọng số của các cạnh được chọn.

Ví dụ minh họa. so sánh tổng trọng số tuyến đường, không phải số lượng cạnh

Trọng số cạnh đã biết là AB = 2, BC = 3, AC = 8 và CD = 1. Tuyến A-C-D có trọng số 9, trong khi A-B-C-D có trọng số 6. Do đó, tuyến ba cạnh này có trọng số nhỏ hơn dù có nhiều cạnh hơn. Cây bao trùm tối thiểu cho mạng nhỏ này sử dụng AB, BC và CD với tổng là 6; sự trùng khớp về tổng ở đây không khiến hai nhiệm vụ trở nên giống nhau.

Tờ bài tập 4.5 bao gồm các bài toán tăng dần độ khó và lời giải đã được kiểm tra độc lập.