Thuật toán và Lập trình

Hiểu biết bền vững (AAP-1): Để tìm các giải pháp cụ thể cho các vấn đề có thể áp dụng rộng rãi, các lập trình viên biểu diễn và tổ chức dữ liệu theo nhiều cách khác nhau.

Mục tiêu học tập AAP-1.A: Biểu diễn một giá trị bằng một biến. [Kỹ năng 3.A]

• AAP-1.A.1 Một biến là một khái niệm trừu tượng bên trong chương trình có thể chứa một giá trị. Mỗi biến có bộ nhớ dữ liệu liên kết đại diện cho một giá trị tại một thời điểm, nhưng giá trị đó có thể là danh sách hoặc tập hợp khác chứa nhiều giá trị.
• AAP-1.A.2 Việc sử dụng tên biến có ý nghĩa giúp cải thiện tính dễ đọc của mã nguồn và sự hiểu biết về các giá trị mà biến đại diện.
• AAP-1.A.3 Một số ngôn ngữ lập trình cung cấp kiểu (types) để biểu diễn dữ liệu, được tham chiếu thông qua các biến. Các kiểu này bao gồm số, Booleans, danh sách và chuỗi.
• AAP-1.A.4 Một số giá trị phù hợp hơn để biểu diễn bằng một loại dữ liệu cụ thể thay vì loại khác.

Mục tiêu học tập AAP-1.B: Xác định giá trị của một biến như là kết quả của phép gán. [Kỹ năng 4.B]

• AAP-1.B.1 toán tử gán cho phép một chương trình thay đổi giá trị được biểu diễn bởi một biến.

• AAP-1.B.2 Sheet tham khảo kỳ thi cung cấp toán tử "$\leftarrow$" để sử dụng cho việc gán. Ví dụ,

  Văn bản:

  a ← expression

  Khối:

  a ← expression

  đánh giá expression và sau đó gán một bản sao của kết quả vào biến a.

• AAP-1.B.3 Giá trị được lưu trữ trong một biến sẽ là giá trị gần đây nhất được gán. Ví dụ:

  a ← 1 b ← a a ← 2 display(b)

  vẫn hiển thị 1.

Hiểu biết bền vững (AAP-1): Để tìm các giải pháp cụ thể cho các vấn đề có thể áp dụng rộng rãi, các lập trình viên biểu diễn và tổ chức dữ liệu theo nhiều cách khác nhau.

Mục tiêu học tập AAP-1.C: Biểu diễn danh sách hoặc chuỗi ký tự bằng một biến. [Kỹ năng 3.A]

• AAP-1.C.1 Một danh sách là một dãy thứ tự các phần tử. Ví dụ,

  [value1, value2, value3, ...]

  mô tả một danh sách nơi value1 là phần tử đầu tiên, value2 là phần tử thứ hai, value3 là phần tử thứ ba, và cứ thế tiếp diễn.

• AAP-1.C.2 Một phần tử là một giá trị đơn lẻ trong danh sách được gán một chỉ số duy nhất.

• AAP-1.C.3 Một chỉ số là phương pháp phổ biến để tham chiếu các phần tử trong danh sách hoặc chuỗi ký tự bằng các số tự nhiên.

• AAP-1.C.4 Một chuỗi ký tự là một dãy thứ tự các ký tự.

Mục tiêu học tập AAP-1.D: Đối với trừu tượng hóa dữ liệu: a. Phát triển trừu tượng hóa dữ liệu sử dụng danh sách để lưu trữ nhiều phần tử. [Kỹ năng 3.B] b. Giải thích cách sử dụng trừu tượng hóa dữ liệu quản lý độ phức tạp trong mã chương trình. [Kỹ năng 3.C]

• AAP-1.D.1 Trừu tượng hóa dữ liệu cung cấp sự phân tách giữa các thuộc tính trừu tượng của một kiểu dữ liệu và các chi tiết cụ thể của biểu diễn của nó.

• AAP-1.D.2 Trừu tượng hóa dữ liệu quản lý độ phức tạp trong chương trình bằng cách đặt tên cho một tập hợp dữ liệu mà không cần tham chiếu đến các chi tiết cụ thể của biểu diễn.

• AAP-1.D.3 Các trừu tượng dữ liệu có thể được tạo ra bằng cách sử dụng danh sách.

• AAP-1.D.4 Việc phát triển một trừu tượng dữ liệu để triển khai trong chương trình có thể dẫn đến một chương trình dễ phát triển và bảo trì hơn.

• AAP-1.D.5 Các trừu tượng dữ liệu thường chứa các loại phần tử khác nhau.

• AAP-1.D.6 Việc sử dụng danh sách cho phép nhiều mục liên quan được xem xét như một giá trị duy nhất. Danh sách được gọi là tên khác nhau, chẳng hạn như mảng, tùy thuộc vào ngôn ngữ lập trình.

  • Câu lệnh loại trừ (EK AAP-1.D.6): Việc sử dụng danh sách liên kết nằm ngoài phạm vi của khóa học này và Bài thi AP.

• AAP-1.D.7 Bảng tham khảo bài thi cung cấp ký hiệu

  [value1, value2, value3, ...]

để tạo một danh sách với các giá trị đó là mục đầu tiên, thứ hai, thứ ba, v.v. Ví dụ,

• Văn bản:

  aList ← [value1, value2, value3, ...]

  Khối:

  aList ← value1, value2, value3

  tạo ra một danh sách mới chứa các giá trị value1, value2, value3, và ... tại các chỉ số 1, 2, 3, và ... tương ứng và gán nó cho aList.

• Văn bản:

  aList ← []

  Khối:

  aList ← (rỗng)

  tạo ra một danh sách rỗng mới và gán nó cho aList.

• Văn bản:

  aList ← bList

  Khối:

  aList ← bList

  gán một bản sao của danh sách bList cho danh sách aList. Ví dụ, nếu bList chứa [20, 40, 60], thì aList cũng sẽ chứa [20, 40, 60] sau khi gán.

• AAP-1.D.8 Bảng tham khảo bài thi mô tả cấu trúc danh sách mà các giá trị chỉ số là từ 1 đến số lượng phần tử trong danh sách, bao gồm cả hai đầu mút. Đối với tất cả các thao tác trên danh sách, nếu chỉ số danh sách nhỏ hơn 1 hoặc lớn hơn độ dài của danh sách, một thông báo lỗi sẽ được tạo ra và chương trình sẽ bị dừng.

Hiểu biết bền vững (AAP-2): Cách các câu lệnh được sắp xếp và kết hợp trong một chương trình xác định kết quả tính toán. Các chương trình tích hợp các cấu trúc lặp và chọn lọc để biểu diễn sự lặp lại và đưa ra quyết định xử lý các giá trị đầu vào khác nhau.

Mục tiêu Học tập AAP-2.A: Biểu diễn một thuật toán sử dụng thứ tự tuần tự mà không cần dùng ngôn ngữ lập trình. [Kỹ năng 2.A]

• AAP-2.A.1 Một thuật toán là một tập hợp hữu hạn các câu lệnh thực hiện một nhiệm vụ cụ thể.
• AAP-2.A.2 Ngoài các ngôn ngữ lập trình trực quan và văn bản, thuật toán có thể được biểu diễn theo nhiều cách khác nhau, chẳng hạn như ngôn ngữ tự nhiên, sơ đồ, và mã giả.
• AAP-2.A.3 Các thuật toán được thực thi bởi các chương trình được triển khai bằng các ngôn ngữ lập trình.
• AAP-2.A.4 Mọi thuật toán đều có thể được xây dựng bằng cách kết hợp thứ tự tuần tự, lựa chọn, và lặp lại.

Mục tiêu Học tập AAP-2.B: Biểu diễn một quy trình thuật toán từng bước bằng các câu lệnh code tuần tự. [Kỹ năng 2.B]

• AAP-2.B.1 Thứ tự tuần tự là việc áp dụng từng bước của thuật toán theo đúng thứ tự mà các câu lệnh code được đưa ra.
• AAP-2.B.2 Một câu lệnh code là một phần của mã chương trình biểu thị một hành động cần thực hiện.
• AAP-2.B.3 Một biểu thức có thể bao gồm một giá trị, một biến, một toán tử, hoặc một lời gọi thủ tục trả về một giá trị.
• AAP-2.B.4 Các biểu thức được đánh giá để tạo ra một giá trị đơn lẻ.
• AAP-2.B.5 Việc đánh giá các biểu thức tuân theo một thứ tự các phép toán được định nghĩa bởi ngôn ngữ lập trình.
• AAP-2.B.6 Các câu lệnh tuần tự được thực thi theo thứ tự chúng xuất hiện trong đoạn code.
• AAP-2.B.7 Sự rõ ràng và khả năng đọc hiểu là những yếu tố quan trọng khi biểu diễn một thuật toán bằng ngôn ngữ lập trình.

Mục tiêu Học tập AAP-2.C: Đánh giá các biểu thức sử dụng các toán tử số học. [Kỹ năng 4.B]

• AAP-2.C.1 Các toán tử số học là một phần của hầu hết các ngôn ngữ lập trình và bao gồm các toán tử cộng, trừ, nhân, chia, và dư (modulus).

• AAP-2.C.2 Bảng tham khảo bài thi cung cấp a MOD b, đánh giá lấy phần dư khi a được chia cho b. Giả sử rằng a là số nguyên lớn hơn hoặc bằng 0 và b là số nguyên lớn hơn 0. Ví dụ, 17 MOD 5 đánh giá thành 2.

• AAP-2.C.3 Sheet tham khảo kỳ thi cung cấp các toán tử số học +, -, *, /, và MOD.

  Văn bản và Khối:

  • a + b
  • a - b
  • a * b
  • a / b
  • a MOD b

  Những toán tử này được sử dụng để thực hiện phép tính số học trên a và b. Ví dụ, 17 / 5 được đánh giá thành 3.4.

• AAP-2.C.4 Thứ tự thực hiện các phép toán trong toán học được áp dụng khi đánh giá biểu thức. Toán tử MOD có cùng độ ưu tiên với các toán tử * và /.

Hiểu biết bền vững (AAP-2): Cách các câu lệnh được sắp xếp và kết hợp trong một chương trình xác định kết quả tính toán. Các chương trình tích hợp các cấu trúc lặp và chọn lọc để biểu diễn sự lặp lại và đưa ra quyết định xử lý các giá trị đầu vào khác nhau.

Mục tiêu Học tập AAP-2.D: Đánh giá các biểu thức thao tác với chuỗi. [Kỹ năng 4.B]

• AAP-2.D.1 Nối chuỗi ghép hai hoặc nhiều chuỗi lại với nhau cuối đầu để tạo ra một chuỗi mới.
• AAP-2.D.2 Một chuỗi con là một phần của một chuỗi đã tồn tại.

Hiểu biết bền vững (AAP-2): Cách các câu lệnh được sắp xếp và kết hợp trong một chương trình xác định kết quả tính toán. Các chương trình tích hợp các cấu trúc lặp và chọn lọc để biểu diễn sự lặp lại và đưa ra quyết định xử lý các giá trị đầu vào khác nhau.

Mục tiêu Học tập AAP-2.E: Đối với mối quan hệ giữa hai biến, biểu thức, hoặc giá trị: a. Viết các biểu thức sử dụng các toán tử quan hệ. [Kỹ năng 2.B] b. Đánh giá các biểu thức sử dụng các toán tử quan hệ. [Kỹ năng 4.B]

• AAP-2.E.1 Một giá trị Boolean là đúng hoặc sai.

• AAP-2.E.2 Bảng tham khảo bài thi cung cấp các toán tử quan hệ sau: =, ≠, >, <, ≥, và ≤.

  Văn bản và Khối:

  • a = b
  • a ≠ b
  • a > b
  • a < b
  • a ≥ b
  • a ≤ b

  Những cái này được sử dụng để kiểm tra mối quan hệ giữa hai biến, biểu thức, hoặc giá trị. Một phép so sánh sử dụng toán tử quan hệ đánh giá thành một giá trị Boolean. Ví dụ, a = b đánh giá thành true nếu a và b bằng nhau; ngược lại, nó đánh giá thành false.

Mục tiêu Học tập AAP-2.F: Đối với mối quan hệ giữa các giá trị Boolean: a. Viết các biểu thức sử dụng các toán tử logic. [Kỹ năng 2.B] b. Đánh giá các biểu thức sử dụng các toán tử logic. [Kỹ năng 4.B]

• AAP-2.F.1 Bảng tham khảo bài thi cung cấp các toán tử logic NOT, AND, và OR, đánh giá thành một giá trị Boolean.

• AAP-2.F.2 Bảng tham khảo bài thi cung cấp

  Văn bản:

  NOT condition

  Khối:

  NOT condition

  trả về kết quả là true nếu condition là false; ngược lại, nó trả về kết quả là false.

• AAP-2.F.3 Bảng tham khảo bài thi cung cấp

  Văn bản:

  condition1 AND condition2

  Khối:

  condition1 AND condition2

đánh giá ra true nếu cả condition1 và condition2 đều true; ngược lại, nó đánh giá ra false.

• AAP-2.F.4 Bảng tham khảo kỳ thi cung cấp

  Văn bản:

  condition1 OR condition2

  Khối:

  condition1 OR condition2

đánh giá ra true nếu condition1 là true hoặc nếu condition2 là true hoặc nếu cả condition1 và condition2 đều true; ngược lại, nó đánh giá ra false.

• AAP-2.F.5 Toán hạng của một toán tử logic có thể là một biểu thức Boolean hoặc một giá trị Boolean đơn lẻ.

Hiểu biết bền vững (AAP-2): Cách các câu lệnh được sắp xếp và kết hợp trong một chương trình xác định kết quả tính toán. Các chương trình tích hợp các cấu trúc lặp và chọn lọc để biểu diễn sự lặp lại và đưa ra quyết định xử lý các giá trị đầu vào khác nhau.

Mục tiêu học tập AAP-2.G: Diễn đạt một thuật toán sử dụng sự lựa chọn mà không dùng ngôn ngữ lập trình. [Kỹ năng 2.A]

• AAP-2.G.1 Sự lựa chọn xác định phần nào của thuật toán được thực thi dựa trên việc một điều kiện là true hay false.

Mục tiêu học tập AAP-2.H: Đối với sự lựa chọn: a. Viết câu lệnh điều kiện. [Kỹ năng 2.B] b. Xác định kết quả của các câu lệnh điều kiện. [Kỹ năng 4.B]

• AAP-2.H.1 Các câu lệnh điều kiện, hay "câu lệnh if", ảnh hưởng đến luồng điều khiển tuần tự bằng cách thực thi các câu lệnh khác nhau dựa trên giá trị của một biểu thức Boolean.

• AAP-2.H.2 Bảng tham khảo kỳ thi cung cấp

  Văn bản:

  IF(condition) { <block of statements> }

  Khối:

  IF condition block of statements

  trong đó mã code trong block of statements sẽ được thực thi nếu biểu thức logic condition cho kết quả là true; không có hành động nào được thực hiện nếu condition cho kết quả là false.

• AAP-2.H.3 Bảng tham khảo kỳ thi cung cấp

  Văn bản:

  IF(condition) { <first block of statements> } ELSE { <second block of statements> }

  Khối:

  IF condition first block of statements ELSE second block of statements

trong đó mã trong first block of statements sẽ được thực thi nếu biểu thức Boolean condition đánh giá là true; ngược lại, mã trong second block of statements sẽ được thực thi.

Hiểu biết bền vững (AAP-2): Cách các câu lệnh được sắp xếp và kết hợp trong một chương trình xác định kết quả tính toán. Các chương trình tích hợp các cấu trúc lặp và chọn lọc để biểu diễn sự lặp lại và đưa ra quyết định xử lý các giá trị đầu vào khác nhau.

Mục tiêu học tập AAP-2.I: Đối với sự lựa chọn lồng nhau: a. Viết câu lệnh điều kiện lồng nhau. [Kỹ năng 2.B] b. Xác định kết quả của các câu lệnh điều kiện lồng nhau. [Kỹ năng 4.B]

• AAP-2.I.1 Các câu lệnh điều kiện lồng nhau bao gồm các câu lệnh điều kiện nằm bên trong các câu lệnh điều kiện khác.

Hiểu biết bền vững (AAP-2): Cách các câu lệnh được sắp xếp và kết hợp trong một chương trình xác định kết quả tính toán. Các chương trình tích hợp các cấu trúc lặp và chọn lọc để biểu diễn sự lặp lại và đưa ra quyết định xử lý các giá trị đầu vào khác nhau.

Mục tiêu học tập AAP-2.J: Diễn đạt một thuật toán sử dụng lặp mà không dùng ngôn ngữ lập trình. [Kỹ năng 2.A]

• AAP-2.J.1 Lặp là một phần của thuật toán được lặp lại. Lặp lại một số lần đã chỉ định hoặc cho đến khi một điều kiện nhất định được thỏa mãn.

Mục tiêu học tập AAP-2.K: Đối với lặp: a. Viết câu lệnh lặp. [Kỹ năng 2.B] b. Xác định kết quả hoặc hiệu ứng phụ của các câu lệnh lặp. [Kỹ năng 4.B]

• AAP-2.K.1 Các câu lệnh lặp thay đổi luồng điều khiển tuần tự bằng cách lặp lại một nhóm câu lệnh từ zero đến nhiều lần, cho đến khi điều kiện dừng được thỏa mãn.

• AAP-2.K.2 Bảng tham khảo kỳ thi cung cấp

  Văn bản:

  REPEAT n TIMES { <block of statements> }

  Khối:

  REPEAT n TIMES block of statements

trong đó block of statements được thực thi n lần.

• AAP-2.K.3 Bảng tham khảo kỳ thi cung cấp

  Văn bản:

  REPEAT UNTIL(condition) { <block of statements> }

  Khối:

  REPEAT UNTIL condition block of statements

trong đó mã trong block of statements được lặp lại cho đến khi biểu thức Boolean condition đánh giá là true.

• AAP-2.K.4 Trong lặp REPEAT UNTIL(condition), vòng lặp vô hạn xảy ra khi điều kiện kết thúc sẽ không bao giờ đánh giá là true.
• AAP-2.K.5 Trong lặp REPEAT UNTIL(condition), nếu điều kiện ban đầu đánh giá là true, thân vòng lặp sẽ không được thực thi bất cứ lúc nào, do điều kiện được kiểm tra trước khi bắt đầu vòng lặp.

Hiểu biết bền vững (AAP-2): Cách các câu lệnh được sắp xếp và kết hợp trong một chương trình xác định kết quả tính toán. Các chương trình tích hợp các cấu trúc lặp và chọn lọc để biểu diễn sự lặp lại và đưa ra quyết định xử lý các giá trị đầu vào khác nhau.

Mục tiêu học tập AAP-2.L: So sánh nhiều thuật toán để xác định xem chúng có tạo ra cùng hiệu ứng phụ hay kết quả hay không. [Kỹ năng 1.D]

• AAP-2.L.1 Thuật toán có thể được viết theo nhiều cách khác nhau nhưng vẫn hoàn thành cùng một nhiệm vụ.
• AAP-2.L.2 Các thuật toán trông giống nhau có thể tạo ra các hiệu ứng phụ hoặc kết quả khác nhau.
• AAP-2.L.3 Một số câu lệnh điều kiện có thể được viết dưới dạng các biểu thức Boolean tương đương.
• AAP-2.L.4 Một số biểu thức Boolean có thể được viết dưới dạng các câu lệnh điều kiện tương đương.
• AAP-2.L.5 Có thể phát triển hoặc sử dụng các thuật toán khác nhau để giải quyết cùng một vấn đề.

Mục tiêu học tập AAP-2.M: Đối với thuật toán: a. Tạo thuật toán. [Kỹ năng 2.A] b. Kết hợp và chỉnh sửa các thuật toán có sẵn. [Kỹ năng 2.B]

• AAP-2.M.1 Thuật toán có thể được tạo ra từ một ý tưởng, bằng cách kết hợp các thuật toán có sẵn, hoặc bằng cách chỉnh sửa các thuật toán có sẵn.
• AAP-2.M.2 Kiến thức về các thuật toán có sẵn có thể giúp xây dựng các thuật toán mới. Một số thuật toán có sẵn bao gồm:
  • xác định giá trị lớn nhất hoặc nhỏ nhất của hai hoặc nhiều số
  • tính tổng hoặc trung bình cộng của hai hoặc nhiều số
  • xác định xem một số nguyên chẵn hay lẻ khi chia hết cho một số nguyên khác
  • xác định đường đi của robot qua mê cung
• AAP-2.M.3 Sử dụng các thuật toán đúng có sẵn làm khối xây dựng để tạo ra một thuật toán khác mang lại lợi ích như giảm thời gian phát triển, giảm thử nghiệm và đơn giản hóa việc xác định lỗi.

Hiểu biết bền vững (AAP-2): Cách các câu lệnh được sắp xếp và kết hợp trong một chương trình xác định kết quả tính toán. Các chương trình tích hợp các cấu trúc lặp và chọn lọc để biểu diễn sự lặp lại và đưa ra quyết định xử lý các giá trị đầu vào khác nhau.

Mục tiêu học tập AAP-2.N: Đối với các thao tác trên danh sách: a. Viết các biểu thức sử dụng chỉ mục danh sách và các thủ tục trên danh sách. [Kỹ năng 2.B] b. Đánh giá các biểu thức sử dụng chỉ mục danh sách và các thủ tục trên danh sách. [Kỹ năng 4.B]

• AAP-2.N.1 Sheet tham khảo kỳ thi cung cấp các thao tác cơ bản trên danh sách, bao gồm:

  • truy cập phần tử theo chỉ mục

    Văn bản:

    aList[i]

    Khối:

    aList i

    truy cập phần tử của aList tại chỉ mục i. Phần tử đầu tiên của aList nằm ở chỉ mục 1 và được truy cập bằng ký hiệu aList[1].

  • gán giá trị của một phần tử danh sách vào một biến

    Văn bản:

    x ← aList[i]

    Khối:

    x ← aList i

    gán giá trị của aList[i] vào biến x.

  • gán giá trị vào một phần tử của danh sách

    Văn bản:

    aList[i] ← x

    Khối:

    aList i ← x

    gán giá trị của x vào aList[i].

    Văn bản:

    aList[i] ← aList[j]

    Khối:

    aList i ← aList j

    gán giá trị của aList[j] vào aList[i].

  • chèn phần tử tại một chỉ mục cho trước

    Văn bản:

    INSERT(aList, i, value)

    Khối:

    INSERT aList, i, value

    dịch sang phải bất kỳ giá trị nào trong aList tại các chỉ mục lớn hơn hoặc bằng i. Độ dài của danh sách tăng lên 1, và value được đặt tại chỉ mục i trong aList.

  • thêm phần tử vào cuối danh sách

    Văn bản:

    APPEND(aList, value)

    Khối:

    APPEND aList, value

    tăng độ dài của aList lên 1, và value được đặt vào cuối aList.

  • xóa phần tử

    Văn bản:

    REMOVE(aList, i)

    Khối:

    REMOVE aList, i

    xóa mục tại chỉ mục i trong aList và dịch sang trái bất kỳ giá trị nào tại các chỉ mục lớn hơn i. Độ dài của aList giảm đi 1.

  • xác định độ dài của một danh sách

    Văn bản:

    LENGTH(aList)

    Khối:

    LENGTH aList

    đánh giá thành số lượng phần tử hiện có trong aList.

• AAP-2.N.2 Các thủ tục trên danh sách được triển khai theo quy tắc cú pháp của ngôn ngữ lập trình.

Mục tiêu học tập AAP-2.O: Đối với các thuật toán liên quan đến các phần tử của danh sách: a. Viết các câu lệnh lặp để duyệt qua một danh sách. [Kỹ năng 2.B] b. Xác định kết quả của một thuật toán bao gồm việc duyệt qua danh sách. [Kỹ năng 4.B]

• AAP-2.O.1 Duyệt qua một danh sách có thể là duyệt hoàn toàn, nơi tất cả các phần tử trong danh sách được truy cập, hoặc duyệt một phần, nơi chỉ một phần các phần tử được truy cập.

  • Câu loại trừ (EK AAP-2.O.1): Duyệt qua nhiều danh sách cùng lúc sử dụng cùng chỉ mục cho cả hai (duyệt song song) nằm ngoài phạm vi của khóa học và Kỳ thi AP.

• AAP-2.O.2 Câu lệnh lặp có thể được sử dụng để duyệt qua một danh sách.

• AAP-2.O.3 Sheet tham khảo kỳ thi cung cấp

  Văn bản:

  FOR EACH item IN aList { <block of statements> }

  Khối:

  FOR EACH item IN aList block of statements

  Biến item được gán giá trị của từng phần tử của aList lần lượt, theo thứ tự, từ phần tử đầu tiên đến phần tử cuối cùng. Mã code trong block of statements được thực thi một lần cho mỗi lần gán item.

• AAP-2.O.4 Kiến thức về các thuật toán có sẵn sử dụng lặp có thể giúp xây dựng các thuật toán mới. Một số ví dụ về các thuật toán có sẵn thường được sử dụng với danh sách bao gồm:

  • xác định giá trị nhỏ nhất hoặc lớn nhất trong một danh sách
  • tính tổng hoặc trung bình cộng của một danh sách số

• AAP-2.O.5 Thuật toán tìm kiếm tuyến tính hay tìm kiếm tuần tự kiểm tra từng phần tử của một danh sách, theo thứ tự, cho đến khi giá trị mong muốn được tìm thấy hoặc tất cả các phần tử trong danh sách đã được kiểm tra.

Hiểu biết bền vững (AAP-2): Cách các câu lệnh được sắp xếp và kết hợp trong một chương trình xác định kết quả tính toán. Các chương trình tích hợp các cấu trúc lặp và chọn lọc để biểu diễn sự lặp lại và đưa ra quyết định xử lý các giá trị đầu vào khác nhau.

Mục tiêu học tập AAP-2.P: Đối với các thuật toán tìm kiếm nhị phân: a. Xác định số lần lặp cần thiết để tìm thấy một giá trị trong tập dữ liệu. [Kỹ năng 1.D] b. Giải thích các yêu cầu cần thiết để hoàn thành tìm kiếm nhị phân. [Kỹ năng 1.A]

• AAP-2.P.1 Thuật toán tìm kiếm nhị phân bắt đầu từ giữa một tập dữ liệu số đã được sắp xếp và loại bỏ một nửa dữ liệu; quá trình này lặp lại cho đến khi giá trị mong muốn được tìm thấy hoặc tất cả các phần tử đã bị loại bỏ.
  • Câu loại trừ (EK AAP-2.P.1): Các triển khai cụ thể của tìm kiếm nhị phân nằm ngoài phạm vi của khóa học và Kỳ thi AP.
• AAP-2.P.2 Dữ liệu phải được sắp xếp để sử dụng thuật toán tìm kiếm nhị phân.
• AAP-2.P.3 Tìm kiếm nhị phân thường hiệu quả hơn so với tìm kiếm tuần tự/tuyến tính khi áp dụng trên dữ liệu đã được sắp xếp.

Hiểu biết bền vững (AAP-3): Các lập trình viên chia nhỏ các vấn đề thành những phần nhỏ hơn và dễ quản lý hơn. Bằng cách tạo ra các thủ tục và tận dụng tham số, các lập trình viên có thể tổng quát hóa các quy trình để tái sử dụng. Thủ tục cho phép các lập trình viên sử dụng mã nguồn đã được kiểm tra sẵn, giúp họ viết chương trình nhanh hơn và tự tin hơn.

Mục tiêu học tập AAP-3.A: Đối với lời gọi thủ tục: a. Viết câu lệnh để gọi thủ tục. [Kỹ năng 3.B] b. Xác định kết quả hoặc tác động của một lời gọi thủ tục. [Kỹ năng 4.B]

• AAP-3.A.1 Một thủ tục là một nhóm các câu lệnh lập trình có tên, có thể có tham số và giá trị trả về.

• AAP-3.A.2 Thủ tục được gọi bằng các tên khác nhau, chẳng hạn như phương thức hoặc hàm, tùy thuộc vào ngôn ngữ lập trình.

• AAP-3.A.3 Tham số là các biến đầu vào của một thủ tục. Tham đối xác định giá trị của các tham số khi một thủ tục được gọi.

• AAP-3.A.4 Một lời gọi thủ tục làm gián đoạn việc thực thi tuần tự của các câu lệnh, khiến chương trình thực thi các câu lệnh bên trong thủ tục trước khi tiếp tục. Khi câu lệnh cuối cùng trong thủ tục (hoặc câu lệnh return) đã được thực thi, luồng điều khiển sẽ trở lại điểm ngay sau nơi thủ tục được gọi.

• AAP-3.A.5 Bảng tham khảo kỳ thi cung cấp

  procName(arg1, arg2, ...)

  như một cách để gọi

  Văn bản:

  PROCEDURE procName(parameter1, parameter2, ...) { <block of statements> }

  Khối:

  PROCEDURE procName parameter1, parameter2,... block of statements

  nhận không hoặc nhiều tham đối; arg1 được gán cho parameter1, arg2 được gán cho parameter2, và cứ thế tiếp diễn.

• AAP-3.A.6 Bảng tham khảo kỳ thi cung cấp thủ tục

  Văn bản:

  DISPLAY(expression)

  Khối:

  DISPLAY expression

  để hiển thị giá trị của expression, theo sau là một khoảng trắng.

• AAP-3.A.7 Bảng tham khảo kỳ thi cung cấp câu lệnh

  Văn bản:

  RETURN(expression)

  Khối:

  RETURN expression

  dùng để trả luồng điều khiển về điểm nơi thủ tục được gọi và trả về giá trị của expression.

• AAP-3.A.8 Bảng tham khảo kỳ thi cung cấp

  result ← procName(arg1, arg2, ...)

  để gán cho result "giá trị của thủ tục" đang được trả về bởi lời gọi

  Văn bản:

  PROCEDURE procName(parameter1, parameter2, ...) { <block of statements> RETURN(expression) }

  Khối:

  PROCEDURE procName parameter1, parameter2,... block of statements RETURN expression

• AAP-3.A.9 Bảng tham khảo kỳ thi cung cấp thủ tục

  Văn bản:

  INPUT()

  Khối:

  INPUT

  nhận một giá trị từ người dùng và trả về giá trị đầu vào đó.

Hiểu biết bền vững (AAP-3): Các lập trình viên chia nhỏ các vấn đề thành những phần nhỏ hơn và dễ quản lý hơn. Bằng cách tạo ra các thủ tục và tận dụng tham số, các lập trình viên có thể tổng quát hóa các quy trình để tái sử dụng. Thủ tục cho phép các lập trình viên sử dụng mã nguồn đã được kiểm tra sẵn, giúp họ viết chương trình nhanh hơn và tự tin hơn.

Mục tiêu học tập AAP-3.B: Giải thích cách sử dụng sự trừu tượng thủ tục giúp quản lý độ phức tạp trong một chương trình. [Kỹ năng 3.C]

• AAP-3.B.1 Một loại trừu tượng phổ biến là trừu tượng thủ tục, cung cấp tên cho một quy trình và cho phép sử dụng thủ tục chỉ cần biết nó làm gì, chứ không cần biết nó làm như thế nào.
• AAP-3.B.2 Trừ抽象 thủ tục cho phép giải quyết một vấn đề lớn dựa trên các giải pháp của các vấn đề con nhỏ hơn. Điều này được thực hiện bằng cách tạo ra các thủ tục để giải quyết từng vấn đề con.
• AAP-3.B.3 Việc phân chia một chương trình máy tính thành các chương trình con riêng biệt được gọi là tính mô-đun.
• AAP-3.B.4 Sự trừu abstract thủ tục có thể trích xuất các đặc điểm chung để tổng quát hóa chức năng thay vì sao chép mã. Điều này cho phép tái sử dụng mã chương trình, giúp quản lý độ phức tạp.
• AAP-3.B.5 Sử dụng tham số cho phép tổng quát hóa thủ tục, giúp chúng có thể được tái sử dụng với nhiều giá trị đầu vào hoặc tham đối khác nhau.
• AAP-3.B.6 Sử dụng trừ抽象 thủ tục giúp cải thiện khả năng đọc hiểu của mã.
• AAP-3.B.7 Sử dụng trừ抽象 thủ tục trong một chương trình cho phép các lập trình viên thay đổi nội bộ của thủ tục (để làm cho nó nhanh hơn, hiệu quả hơn, tiết kiệm bộ nhớ hơn, v.v.) mà không cần thông báo cho người dùng về sự thay đổi, miễn là hành vi của thủ tục vẫn được giữ nguyên.

Mục tiêu học tập AAP-3.C: Phát triển trừ抽象 thủ tục để quản lý độ phức tạp trong một chương trình bằng cách viết các thủ tục. [Kỹ năng 3.B]

• AAP-3.C.1 Bảng tham khảo kỳ thi cung cấp

  Văn bản:

  PROCEDURE procName(parameter1, parameter2, ...) { <block of statements> }

  Khối:

  PROCEDURE procName parameter1, parameter2,... block of statements

  dùng để định nghĩa một thủ tục nhận không hoặc nhiều tham đối. Thủ tục chứa block of statements.

• AAP-3.C.2 Bảng tham khảo kỳ thi cung cấp

  Văn bản:

  PROCEDURE procName(parameter1, parameter2, ...) { <block of statements> RETURN(expression) }

  Khối:

  PROCEDURE procName parameter1, parameter2,... block of statements RETURN expression

  được sử dụng để định nghĩa một thủ tục nhận không hoặc nhiều tham số. Thủ tục chứa block of statements và trả về giá trị của expression. Câu lệnh RETURN có thể xuất hiện ở bất kỳ đâu bên trong thủ tục và gây ra việc trả về ngay lập tức từ thủ tục trở lại câu lệnh gọi.

Hiểu biết bền vững (AAP-3): Các lập trình viên chia nhỏ các vấn đề thành những phần nhỏ hơn và dễ quản lý hơn. Bằng cách tạo ra các thủ tục và tận dụng tham số, các lập trình viên có thể tổng quát hóa các quy trình để tái sử dụng. Thủ tục cho phép các lập trình viên sử dụng mã nguồn đã được kiểm tra sẵn, giúp họ viết chương trình nhanh hơn và tự tin hơn.

Mục tiêu học tập AAP-3.D: Chọn các thư viện hoặc đoạn mã nguồn có sẵn phù hợp để sử dụng trong việc tạo ra các chương trình mới. [Kỹ năng 2.B]

• AAP-3.D.1 Một thư viện phần mềm chứa các thủ tục có thể được sử dụng trong việc tạo ra các chương trình mới.
• AAP-3.D.2 Các đoạn mã nguồn có sẵn có thể đến từ các nguồn nội bộ hoặc bên ngoài, chẳng hạn như thư viện hoặc mã nguồn đã được viết trước đó.
• AAP-3.D.3 Việc sử dụng thư viện đơn giản hóa nhiệm vụ tạo ra các chương trình phức tạp.
• AAP-3.D.4 Giao diện lập trình ứng dụng (APIs) là các quy định về cách các thủ tục trong thư viện hoạt động và có thể được sử dụng.
• AAP-3.D.5 Tài liệu hướng dẫn cho API/thư viện là cần thiết để hiểu các hành vi do API/thư viện cung cấp và cách sử dụng chúng.

Hiểu biết bền vững (AAP-3): Các lập trình viên chia nhỏ các vấn đề thành những phần nhỏ hơn và dễ quản lý hơn. Bằng cách tạo ra các thủ tục và tận dụng tham số, các lập trình viên có thể tổng quát hóa các quy trình để tái sử dụng. Thủ tục cho phép các lập trình viên sử dụng mã nguồn đã được kiểm tra sẵn, giúp họ viết chương trình nhanh hơn và tự tin hơn.

Mục tiêu học tập AAP-3.E: Đối với việc tạo ra các giá trị ngẫu nhiên: a. Viết biểu thức để tạo ra các giá trị có thể xảy ra. [Kỹ năng 2.B] b. Đánh giá biểu thức để xác định các kết quả có thể. [Kỹ năng 4.B]

• AAP-3.E.1 Bảng tham khảo kỳ thi cung cấp

  Văn bản:

  RANDOM(a, b)

  Khối:

  RANDOM a, b

  tạo và trả về một số nguyên ngẫu nhiên từ a đến b, bao gồm cả hai đầu mút. Mỗi kết quả đều có khả năng xảy ra ngang nhau. Ví dụ, RANDOM(1, 3) có thể trả về 1, 2, hoặc 3.

• AAP-3.E.2 Việc sử dụng tạo số ngẫu nhiên trong một chương trình có nghĩa là mỗi lần thực thi có thể tạo ra kết quả khác nhau.

Hiểu biết bền vững (AAP-3): Các lập trình viên chia nhỏ các vấn đề thành những phần nhỏ hơn và dễ quản lý hơn. Bằng cách tạo ra các thủ tục và tận dụng tham số, các lập trình viên có thể tổng quát hóa các quy trình để tái sử dụng. Thủ tục cho phép các lập trình viên sử dụng mã nguồn đã được kiểm tra sẵn, giúp họ viết chương trình nhanh hơn và tự tin hơn.

Mục tiêu học tập AAP-3.F: Đối với các mô phỏng: a. Giải thích cách máy tính có thể được sử dụng để đại diện cho các hiện tượng hoặc kết quả trong thế giới thực. [Kỹ năng 1.A] b. So sánh các mô phỏng với bối cảnh thế giới thực. [Kỹ năng 1.D]

• AAP-3.F.1 Mô phỏng là sự trừu tượng hóa các đối tượng hoặc hiện tượng phức tạp hơn nhằm phục vụ một mục đích cụ thể.
• AAP-3.F.2 Một mô phỏng là đại diện sử dụng các tập giá trị khác nhau để phản ánh trạng thái thay đổi của một hiện tượng.
• AAP-3.F.3 Mô phỏng thường mô phỏng lại các sự kiện thực tế với mục đích rút ra kết luận, cho phép điều tra một hiện tượng mà không bị giới hạn bởi thế giới thực.
• AAP-3.F.4 Quá trình phát triển mô phỏng trừu tượng liên quan đến việc loại bỏ các chi tiết cụ thể hoặc đơn giản hóa chức năng.
• AAP-3.F.5 Mô phỏng có thể chứa thiên kiến xuất phát từ những lựa chọn về các yếu tố thực tế được bao gồm hoặc loại bỏ.
• AAP-3.F.6 Mô phỏng hữu ích nhất khi các sự kiện thực tế không khả thi cho thí nghiệm (ví dụ: quá lớn, quá nhỏ, quá nhanh, quá chậm, quá đắt tiền, hoặc quá nguy hiểm).
• AAP-3.F.7 Mô phỏng hỗ trợ việc xây dựng và tinh chỉnh các giả thuyết liên quan đến các đối tượng hoặc hiện tượng đang xem xét.
• AAP-3.F.8 Bộ tạo số ngẫu nhiên có thể được sử dụng để mô phỏng sự biến dị tồn tại trong thế giới thực.

Hiểu biết dai dẳng (AAP-4): Tồn tại các vấn đề mà máy tính không thể giải quyết, và ngay cả khi máy tính có thể giải quyết một vấn đề, nó cũng có thể không làm được trong khoảng thời gian hợp lý.

Mục tiêu học tập AAP-4.A: Để xác định hiệu quả của thuật toán: a. Giải thích sự khác biệt giữa các thuật toán chạy trong khoảng thời gian hợp lý và các thuật toán không làm được. [Kỹ năng 1.D] b. Xác định các tình huống mà giải pháp hồi quy có thể phù hợp hơn. [Kỹ năng 1.D]

• AAP-4.A.1 Một vấn đề là mô tả chung về một nhiệm vụ có thể (hoặc không thể) được giải quyết bằng thuật toán. Một trường hợp của vấn đề cũng bao gồm đầu vào cụ thể. Ví dụ, sắp xếp là một vấn đề; sắp xếp danh sách (2,3,1,7) là một trường hợp của vấn đề đó.
• AAP-4.A.2 Một vấn đề quyết định là một vấn đề có câu trả lời có/không (ví dụ: có đường đi từ A đến B không?). Một vấn đề tối ưu hóa là một vấn đề có mục tiêu tìm "giải pháp tốt nhất" trong nhiều giải pháp (ví dụ: đường đi ngắn nhất từ A đến B là gì?).
• AAP-4.A.3 Hiệu quả là ước lượng lượng tài nguyên tính toán được sử dụng bởi một thuật toán. Hiệu quả thường được biểu diễn dưới dạng hàm của kích thước đầu vào.
  • Câu loại trừ (EK AAP-4.A.3): Phân tích chính thức về thuật toán (Big-O) và lập luận chính thức sử dụng công thức toán học nằm ngoài phạm vi của khóa học này và kỳ thi AP.
• AAP-4.A.4 Hiệu quả của một thuật toán được xác định thông qua lập luận chính thức hoặc toán học.
• AAP-4.A.5 Hiệu quả của một thuật toán có thể được đo lường một cách phi chính thức bằng cách xác định số lần một câu lệnh hoặc nhóm câu lệnh được thực thi.
• AAP-4.A.6 Các thuật toán đúng khác nhau cho cùng một vấn đề có thể có hiệu quả khác nhau.
• AAP-4.A.7 Các thuật toán có hiệu quả đa thức hoặc chậm hơn (hằng số, tuyến tính, bình phương, lập phương, v.v.) được nói là chạy trong khoảng thời gian hợp lý. Các thuật toán có hiệu quả mũ hay giai thừa là ví dụ về các thuật toán chạy trong khoảng thời gian không hợp lý.
• AAP-4.A.8 Một số vấn đề không thể được giải quyết trong khoảng thời gian hợp lý vì không có thuật toán hiệu quả nào để giải quyết chúng. Trong những trường hợp này, các giải pháp xấp xỉ được tìm kiếm.
• AAP-4.A.9 Một hồi quy là tiếp cận vấn đề tạo ra giải pháp không được đảm bảo là tối ưu nhưng có thể được sử dụng khi các kỹ thuật đảm bảo luôn tìm thấy giải pháp tối ưu là không khả thi.
  • Câu loại trừ (AAP-4.A.9): Các giải pháp hồi quy cụ thể nằm ngoài phạm vi của khóa học này và kỳ thi AP.

Hiểu biết dai dẳng (AAP-4): Tồn tại các vấn đề mà máy tính không thể giải quyết, và ngay cả khi máy tính có thể giải quyết một vấn đề, nó cũng có thể không làm được trong khoảng thời gian hợp lý.

Mục tiêu học tập AAP-4.B: Giải thích sự tồn tại của các vấn đề không thể quyết định trong khoa học máy tính. [Kỹ năng 1.A]

• AAP-4.B.1 Một vấn đề có thể quyết định là một vấn đề quyết định mà một thuật toán có thể được viết để tạo ra đầu ra chính xác cho tất cả các đầu vào (ví dụ: "Số có chẵn không?").
• AAP-4.B.2 Một vấn đề không thể quyết định là vấn đề mà không có thuật toán nào có thể được xây dựng luôn cung cấp câu trả lời đúng yes/no.
  • Câu loại trừ (EK AAP-4.B.2): Việc xác định liệu một vấn đề đã cho có phải là vấn đề không thể quyết định hay không nằm ngoài phạm vi của khóa học này và kỳ thi AP.
• AAP-4.B.3 Một vấn đề không thể quyết định có thể có một số trường hợp có giải pháp thuật toán, nhưng không có giải pháp thuật toán nào có thể giải quyết tất cả các trường hợp của vấn đề đó.