AP Computer Science Principles · AP Nguyên lý khoa học máy tính · Topic 3 · Chủ đề 3
9:17
Thuật toán và Lập trình
Hãy tưởng tượng một danh bạ điện thoại có một triệu tên, và bạn phải tìm thấy một người. Kiểm tra từng cái một, và bạn có thể ở đó suốt cả ngày. Có cách để tìm thấy nó trong khoảng…
English narration · English + 中文 subtitles burned in · Giọng đọc tiếng Anh · phụ đề tiếng Anh + 中文 được ghi trực tiếp
Code below uses the AP CSP pseudocode – the exam's language-neutral reference. Assignment is written a ← expression, and list indices start at 1.
Mã bên dưới sử dụng giả mã AP CSP – tài liệu tham khảo trung lập ngôn ngữ của kỳ thi. Phép gán được viết a ← expression, và chỉ mục danh sách bắt đầu từ 1.
Enduring Understanding (AAP-1): To find specific solutions to generalizable problems, programmers represent and organize data in multiple ways.
Learning Objective AAP-1.A: Represent a value with a variable. [Skill 3.A]
Learning Objective AAP-1.B: Determine the value of a variable as a result of an assignment. [Skill 4.B]
AAP-1.B.1 The assignment operator allows a program to change the value represented by a variable.
AAP-1.B.2 The exam reference sheet provides the "$\leftarrow$" operator to use for assignment. For example,
Text:
a ← expression
Block:
a ← expression
evaluates expression and then assigns a copy of the result to the variable a.
AAP-1.B.3 The value stored in a variable will be the most recent value assigned. For example:
a ← 1
b ← a
a ← 2
display(b)
still displays 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.A: Biểu diễn một giá trị bằng một biến. [Kỹ năng 3.A]
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.
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
A variable 变量 is a named place that holds a value. The assignment 赋值 operator stores the value on the right into the variable on the left:
A variable holds one value at a time; assigning again replaces it. Variables let a program store input, remember results, and reuse them.
Một biến là một tên gọi dành cho nơi chứa một giá trị. Toán tử gán lưu giá trị ở vế phải vào biến ở vế trái:
a ← 5
b ← a + 3 // b is now 8
Một biến chỉ chứa một giá trị tại một thời điểm; việc gán lại sẽ thay thế nó. Biến cho phép chương trình lưu đầu vào, nhớ kết quả và tái sử dụng chúng.
A variable is a named box that stores one value at a time. An assignment copies a value into the box; assigning again overwrites whatever was there. · Một biến là một hộp có tên chỉ lưu trữ một giá trị tại một thời điểm. Một phép gán sao chép một giá trị vào hộp này; việc gán lại sẽ ghi đè lên bất cứ thứ gì đã có ở đó.
| English | Tiếng Việt |
|---|---|
| variable/ˈveərɪəbl/ | biến |
| assignment/əˈsaɪnmənt/ | gán (assignment) |
| Data abstraction/ˈdeɪtə əbˈstrækʃn/ | trừu tượng hóa dữ liệu |
| remainder/rɪˈmeɪndə/ | phần dư |
Enduring Understanding (AAP-1): To find specific solutions to generalizable problems, programmers represent and organize data in multiple ways.
Learning Objective AAP-1.C: Represent a list or string using a variable. [Skill 3.A]
AAP-1.C.1 A list is an ordered sequence of elements. For example,
[value1, value2, value3, ...]
describes a list where value1 is the first element, value2 is the second element, value3 is the third element, and so on.
AAP-1.C.2 An element is an individual value in a list that is assigned a unique index.
AAP-1.C.3 An index is a common method for referencing the elements in a list or string using natural numbers.
AAP-1.C.4 A string is an ordered sequence of characters.
Learning Objective AAP-1.D: For data abstraction: a. Develop data abstraction using lists to store multiple elements. [Skill 3.B] b. Explain how the use of data abstraction manages complexity in program code. [Skill 3.C]
AAP-1.D.1 Data abstraction provides a separation between the abstract properties of a data type and the concrete details of its representation.
AAP-1.D.2 Data abstractions manage complexity in programs by giving a collection of data a name without referencing the specific details of the representation.
AAP-1.D.3 Data abstractions can be created using lists.
AAP-1.D.4 Developing a data abstraction to implement in a program can result in a program that is easier to develop and maintain.
AAP-1.D.5 Data abstractions often contain different types of elements.
AAP-1.D.6 The use of lists allows multiple related items to be treated as a single value. Lists are referred to by different names, such as array, depending on the programming language.
AAP-1.D.7 The exam reference sheet provides the notation
[value1, value2, value3, ...]
to create a list with those values as the first, second, third, and so on items. For example,
Text:
aList ← [value1, value2, value3, ...]
Block:
aList ← value1, value2, value3
creates a new list that contains the values value1, value2, value3, and ... at indices 1, 2, 3, and ... respectively and assigns it to aList.
Text:
aList ← []
Block:
aList ← (empty)
creates a new empty list and assigns it to aList.
Text:
aList ← bList
Block:
aList ← bList
assigns a copy of the list bList to the list aList. For example, if bList contains [20, 40, 60], then aList will also contain [20, 40, 60] after the assignment.
AAP-1.D.8 The exam reference sheet describes a list structure whose index values are 1 through the number of elements in the list, inclusive. For all list operations, if a list index is less than 1 or greater than the length of the list, an error message is produced and the program will terminate.
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.
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.
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
Data abstraction 数据抽象 lets you manage complexity by giving a single name to a collection of data – for example, a list rather than dozens of separate variables. It hides detail: you use the named collection without worrying about how it is stored. Lists (below) are the course's main data abstraction.
Trừ抽象 dữ liệu cho phép bạn quản lý độ phức tạp bằng cách gán một tên duy nhất cho một tập hợp dữ liệu – ví dụ, một danh sách thay vì hàng chục biến riêng biệt. Nó ẩn đi chi tiết: bạn sử dụng tập hợp có tên mà không cần lo lắng về cách nó được lưu trữ. Danh sách (bên dưới) là trừu tượng dữ liệu chính của khóa học.
Enduring Understanding (AAP-2): The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.A: Express an algorithm that uses sequencing without using a programming language. [Skill 2.A]
Learning Objective AAP-2.B: Represent a step-by-step algorithmic process using sequential code statements. [Skill 2.B]
Learning Objective AAP-2.C: Evaluate expressions that use arithmetic operators. [Skill 4.B]
AAP-2.C.1 Arithmetic operators are part of most programming languages and include addition, subtraction, multiplication, division, and modulus operators.
AAP-2.C.2 The exam reference sheet provides a MOD b, which evaluates to the remainder when a is divided by b. Assume that a is an integer greater than or equal to 0 and b is an integer greater than 0. For example, 17 MOD 5 evaluates to 2.
AAP-2.C.3 The exam reference sheet provides the arithmetic operators +, -, *, /, and MOD.
Text and Block:
a + ba - ba * ba / ba MOD bThese are used to perform arithmetic on a and b. For example, 17 / 5 evaluates to 3.4.
AAP-2.C.4 The order of operations used in mathematics applies when evaluating expressions. The MOD operator has the same precedence as the * and / operators.
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]
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]
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 + ba - ba * ba / ba MOD bNhữ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à /.
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
Programs compute with the operators +, -, *, /, and MOD (the remainder 余数 of a division, e.g. 17 MOD 5 is 2). Expressions follow the usual order of operations. MOD is especially useful for testing divisibility (n MOD 2 = 0 means n is even) and for wrapping values around a range.
Các chương trình tính toán sử dụng các toán tử +, -, *, / và MOD (phần dư của phép chia, ví dụ: 17 MOD 5 là 2). Các biểu thức tuân theo thứ tự ưu tiên thông thường. MOD đặc biệt hữu ích cho việc kiểm tra tính chia hết (n MOD 2 = 0 có nghĩa là n là số chẵn) và để bao wrap các giá trị quanh một khoảng范围.
An expression is evaluated with order of operations: multiplication and division happen before addition and subtraction, left to right. · Một biểu thức được đánh giá theo thứ tự ưu tiên phép toán: nhân và chia diễn ra trước cộng và trừ, từ trái sang phải.
Enduring Understanding (AAP-2): The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.D: Evaluate expressions that manipulate strings. [Skill 4.B]
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]
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
A string 字符串 is an ordered sequence of characters, like "hello". Programs join strings (concatenation 拼接) and find their length. Strings represent text – names, messages, sequences – and are a common program input and output.
Một chuỗi (string) là một dãy có thứ tự các ký tự, giống như "hello". Chương trình nối chuỗi (nối chuỗi) và tìm chiều dài của chúng. Chuỗi đại diện cho văn bản – tên, tin nhắn, dãy – và là đầu vào/đầu ra phổ biến của chương trình.
| English | Tiếng Việt |
|---|---|
| string/strɪŋ/ | chuỗi ký tự |
| concatenation/kənˌkætəˈneɪʃn/ | nối chuỗi (concatenation) |
Enduring Understanding (AAP-2): The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.E: For relationships between two variables, expressions, or values: a. Write expressions using relational operators. [Skill 2.B] b. Evaluate expressions that use relational operators. [Skill 4.B]
AAP-2.E.1 A Boolean value is either true or false.
AAP-2.E.2 The exam reference sheet provides the following relational operators: =, ≠, >, <, ≥, and ≤.
Text and Block:
a = ba ≠ ba > ba < ba ≥ ba ≤ bThese are used to test the relationship between two variables, expressions, or values. A comparison using a relational operator evaluates to a Boolean value. For example, a = b evaluates to true if a and b are equal; otherwise, it evaluates to false.
Learning Objective AAP-2.F: For relationships between Boolean values: a. Write expressions using logical operators. [Skill 2.B] b. Evaluate expressions that use logic operators. [Skill 4.B]
AAP-2.F.1 The exam reference sheet provides the logical operators NOT, AND, and OR, which evaluate to a Boolean value.
AAP-2.F.2 The exam reference sheet provides
Text:
NOT condition
Block:
NOT condition
which evaluates to true if condition is false; otherwise it evaluates to false.
AAP-2.F.3 The exam reference sheet provides
Text:
condition1 AND condition2
Block:
condition1 AND condition2
which evaluates to true if both condition1 and condition2 are true; otherwise it evaluates to false.
AAP-2.F.4 The exam reference sheet provides
Text:
condition1 OR condition2
Block:
condition1 OR condition2
which evaluates to true if condition1 is true or if condition2 is true or if both condition1 and condition2 are true; otherwise it evaluates to false.
AAP-2.F.5 The operand for a logical operator is either a Boolean expression or a single Boolean value.
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 = ba ≠ ba > ba < ba ≥ ba ≤ bNhữ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.
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
A Boolean expression 布尔表达式 evaluates to true or false. It uses relational operators (=, ≠, <, >, ≤, ≥) and logical operators NOT, AND, OR:
NOT reverses a value,AND is true only when both sides are true,OR is true when at least one side is true.These conditions drive every decision and loop.
Một biểu thức logic (Boolean expression) trả về true hoặc false. Nó sử dụng toán tử quan hệ (=, ≠, <, >, ≤, ≥) và toán tử logic NOT, AND, OR:
NOT đảo ngược một giá trị,AND chỉ đúng khi cả hai vế đều đúng,OR đúng khi ít nhất một vế đúng.Các điều kiện này dẫn dắt mọi quyết định và vòng lặp.
A Boolean expression is either true (1) or false (0). OR is true when at least one input is true; flip the inputs to see every case. · Một biểu thức Boolean luôn đúng (1) hoặc sai (0). Phép OR đúng khi ít nhất một đầu vào là đúng; đảo ngược các đầu vào để xem mọi trường hợp.
| English | Tiếng Việt |
|---|---|
| Boolean expression/ˈbuːlɪən ekˈspreʃn/ | biểu thức Boolean |
| conditional (selection)/kənˈdɪʃənl/ | có điều kiện (lựa chọn) |
| nested conditional/ˈnestɪd kənˈdɪʃənl/ | điều kiện lồng nhau |
Enduring Understanding (AAP-2): The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.G: Express an algorithm that uses selection without using a programming language. [Skill 2.A]
true or false.Learning Objective AAP-2.H: For selection: a. Write conditional statements. [Skill 2.B] b. Determine the result of conditional statements. [Skill 4.B]
AAP-2.H.1 Conditional statements, or "if-statements," affect the sequential flow of control by executing different statements based on the value of a Boolean expression.
AAP-2.H.2 The exam reference sheet provides
Text:
IF(condition)
{
<block of statements>
}
Block:
IF condition
block of statements
in which the code in block of statements is executed if the Boolean expression condition evaluates to true; no action is taken if condition evaluates to false.
AAP-2.H.3 The exam reference sheet provides
Text:
IF(condition)
{
<first block of statements>
}
ELSE
{
<second block of statements>
}
Block:
IF condition
first block of statements
ELSE
second block of statements
in which the code in first block of statements is executed if the Boolean expression condition evaluates to true; otherwise, the code in second block of statements is executed.
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]
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.
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
A conditional (selection) 条件语句 chooses which code to run. IF runs a block only when its condition is true; ELSE gives an alternative:
Một điều kiện (lựa chọn) chọn xem đoạn mã nào sẽ chạy. IF chạy một khối mã chỉ khi điều kiện của nó là đúng; ELSE đưa ra một tùy chọn thay thế:
IF (score ≥ 60)
{
DISPLAY("Pass")
}
ELSE
{
DISPLAY("Fail")
}
A conditional runs one branch or another depending on whether its condition is true. Slide the value across the threshold and watch which branch is taken. · Một điều kiện sẽ thực thi một nhánh hoặc nhánh khác tùy thuộc vào điều kiện của nó có đúng hay không. Kéo giá trị vượt qua ngưỡng và xem nhánh nào được chọn.
Enduring Understanding (AAP-2): The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.I: For nested selection: a. Write nested conditional statements. [Skill 2.B] b. Determine the result of nested conditional statements. [Skill 4.B]
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]
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
A nested conditional 嵌套条件 places one IF inside another (or chains ELSE IF) to choose among more than two paths. Only the first matching branch runs:
Một điều kiện lồng nhau đặt một IF bên trong另一个 (hoặc ghép ELSE IF) để chọn giữa hơn hai đường đi. Chỉ nhánh đầu tiên khớp sẽ chạy:
IF (g ≥ 90) { grade ← "A" }
ELSE IF (g ≥ 80) { grade ← "B" }
ELSE { grade ← "C" }
Enduring Understanding (AAP-2): The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.J: Express an algorithm that uses iteration without using a programming language. [Skill 2.A]
Learning Objective AAP-2.K: For iteration: a. Write iteration statements. [Skill 2.B] b. Determine the result or side effect of iteration statements. [Skill 4.B]
AAP-2.K.1 Iteration statements change the sequential flow of control by repeating a set of statements zero or more times, until a stopping condition is met.
AAP-2.K.2 The exam reference sheet provides
Text:
REPEAT n TIMES
{
<block of statements>
}
Block:
REPEAT n TIMES
block of statements
in which the block of statements is executed n times.
AAP-2.K.3 The exam reference sheet provides
Text:
REPEAT UNTIL(condition)
{
<block of statements>
}
Block:
REPEAT UNTIL condition
block of statements
in which the code in block of statements is repeated until the Boolean expression condition evaluates to true.
AAP-2.K.4 In REPEAT UNTIL(condition) iteration, an infinite loop occurs when the ending condition will never evaluate to true.
AAP-2.K.5 In REPEAT UNTIL(condition) iteration, if the conditional evaluates to true initially, the loop body is not executed at all, due to the condition being checked before the loop.
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]
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.
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.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.Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
Iteration (a loop) 迭代 repeats instructions. AP pseudocode has two forms:
A loop that never meets its stopping condition is an infinite loop 无限循环.
Lặp (Iteration) lặp lại các lệnh. Giả mã AP có hai dạng:
REPEAT 5 TIMES // a fixed count
{
DISPLAY("hi")
}
REPEAT UNTIL (found) // until a condition becomes true
{
...
}
Một vòng lặp chưa bao giờ đạt được điều kiện dừng là vòng lặp vô hạn.
A loop repeats a block while its counter runs through a range. Step through to watch the counter and the running total update each pass. · Một vòng lặp lặp lại một khối lệnh khi bộ đếm của nó chạy qua một khoảng giá trị. Bước qua từng lượt để xem bộ đếm và tổng tích lũy cập nhật mỗi lần lặp.
| English | Tiếng Việt |
|---|---|
| Iteration (a loop)/ˌɪtəˈreɪʃn/ | Lặp lại (vòng lặp) |
| infinite loop/ˈɪnfɪnət luːp/ | vòng lặp vô hạn |
| algorithm/ˈælɡərɪθəm/ | thuật toán |
Enduring Understanding (AAP-2): The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.L: Compare multiple algorithms to determine if they yield the same side effect or result. [Skill 1.D]
Learning Objective AAP-2.M: For algorithms: a. Create algorithms. [Skill 2.A] b. Combine and modify existing algorithms. [Skill 2.B]
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]
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]
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
An algorithm is not the same thing as code. Beyond visual and textual programming languages, an algorithm can be expressed in a variety of ways: in natural language (ordinary sentences), as a diagram such as a flowchart, or in pseudocode. Those forms are for people — they let you check the logic and agree on it before any language is chosen, and the same algorithm can then be written in any language.
When you do write it in a programming language, clarity and readability are important considerations, not decoration: meaningful variable names, consistent indentation and comments explaining why rather than what. The program has to be read and modified later by someone — often you — and an algorithm nobody can follow cannot be maintained or debugged.
An algorithm 算法 is a finite sequence of steps that solves a problem, built from sequencing, selection, and iteration. Different algorithms can solve the same problem, and you should be able to combine and modify existing algorithms (for example, count the values in a list that meet a condition, or find the largest). Trace an algorithm by hand to check it is correct.
Thuật toán không phải là code. Ngoài các ngôn ngữ lập trình trực quan và văn bản, một thuật toán có thể được biểu diễn bằng nhiều cách khác nhau: trong ngôn ngữ tự nhiên (câu thông thường), dưới dạng sơ đồ như flowchart, hoặc trong pseudocode. Những hình thức này dành cho con người — chúng cho phép bạn kiểm tra logic và thống nhất về nó trước khi chọn bất kỳ ngôn ngữ nào, và cùng một thuật toán sau đó có thể được viết bằng bất kỳ ngôn ngữ nào.
Khi bạn viết mã bằng ngôn ngữ lập trình, sự rõ ràng và khả năng đọc hiểu là những yếu tố quan trọng, không chỉ là trang trí: tên biến có ý nghĩa, thụt lề nhất quán và comment giải thích tại sao thay vì cái gì. Chương trình sẽ cần được đọc và sửa đổi sau này bởi ai đó — thường là chính bạn — và một thuật toán mà không ai theo kịp thì không thể bảo trì hay gỡ lỗi được.
Một thuật toán là một chuỗi hữu hạn các bước để giải quyết một vấn đề, được xây dựng từ thứ tự thực thi (sequencing), lựa chọn (selection) và lặp lại (iteration). Các thuật toán khác nhau có thể giải quyết cùng một vấn đề, và bạn nên có khả năng kết hợp và điều chỉnh các thuật toán hiện có (ví dụ: đếm các giá trị trong danh sách thỏa mãn một điều kiện, hoặc tìm giá trị lớn nhất). Hãy chạy thử thuật toán bằng tay để kiểm tra xem nó có đúng không.
Enduring Understanding (AAP-2): The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.N: For list operations: a. Write expressions that use list indexing and list procedures. [Skill 2.B] b. Evaluate expressions that use list indexing and list procedures. [Skill 4.B]
accessing an element by index
Text:
aList[i]
Block:
aList i
accesses the element of aList at index i. The first element of aList is at index 1 and is accessed using the notation aList[1].
assigning a value of an element of a list to a variable
Text:
x ← aList[i]
Block:
x ← aList i
assigns the value of aList[i] to the variable x.
assigning a value to an element of a list
Text:
aList[i] ← x
Block:
aList i ← x
assigns the value of x to aList[i].
Text:
aList[i] ← aList[j]
Block:
aList i ← aList j
assigns the value of aList[j] to aList[i].
inserting elements at a given index
Text:
INSERT(aList, i, value)
Block:
INSERT aList, i, value
shifts to the right any values in aList at indices greater than or equal to i. The length of the list is increased by 1, and value is placed at index i in aList.
adding elements to the end of the list
Text:
APPEND(aList, value)
Block:
APPEND aList, value
increases the length of aList by 1, and value is placed at the end of aList.
removing elements
Text:
REMOVE(aList, i)
Block:
REMOVE aList, i
removes the item at index i in aList and shifts to the left any values at indices greater than i. The length of aList is decreased by 1.
determining the length of a list
Text:
LENGTH(aList)
Block:
LENGTH aList
evaluates to the number of elements currently in aList.
Learning Objective AAP-2.O: For algorithms involving elements of a list: a. Write iteration statements to traverse a list. [Skill 2.B] b. Determine the result of an algorithm that includes list traversals. [Skill 4.B]
AAP-2.O.1 Traversing a list can be a complete traversal, where all elements in the list are accessed, or a partial traversal, where only a portion of elements are accessed.
AAP-2.O.2 Iteration statements can be used to traverse a list.
AAP-2.O.3 The exam reference sheet provides
Text:
FOR EACH item IN aList
{
<block of statements>
}
Block:
FOR EACH item IN aList
block of statements
The variable item is assigned the value of each element of aList sequentially, in order, from the first element to the last element. The code in block of statements is executed once for each assignment of item.
AAP-2.O.4 Knowledge of existing algorithms that use iteration can help in constructing new algorithms. Some examples of existing algorithms that are often used with lists include:
AAP-2.O.5 Linear search or sequential search algorithms check each element of a list, in order, until the desired value is found or all elements in the list have been checked.
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]
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.
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.
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:
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.
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
A list 列表 is an ordered collection of values under one name, the course's key data abstraction. AP pseudocode indexes from 1:
Traverse a list with a loop to sum, count, search, or find a maximum:
Một danh sách (list) là một tập hợp có thứ tự các giá trị dưới một tên duy nhất, đây là phép trừu tượng dữ liệu cốt lõi của khóa học. Pseudocode của AP đánh số chỉ mục bắt đầu từ 1:
scores ← [88, 74, 95]
DISPLAY(scores[1]) // 88
scores[2] ← 80 // replace the 2nd value
APPEND(scores, 60) // add to the end
INSERT(scores, 1, 100) // insert at index 1
REMOVE(scores, 3) // delete the 3rd element
LENGTH(scores) // how many elements
Duyệt qua danh sách với vòng lặp để tính tổng, đếm, tìm kiếm hoặc tìm giá trị tối đa:
FOR EACH x IN scores
{
total ← total + x
}
| English | Tiếng Việt |
|---|---|
| list/lɪst/ | list (danh sách) |
Enduring Understanding (AAP-2): The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.
Learning Objective AAP-2.P: For binary search algorithms: a. Determine the number of iterations required to find a value in a data set. [Skill 1.D] b. Explain the requirements necessary to complete a binary search. [Skill 1.A]
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]
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
Binary search 二分搜索 finds a value in a sorted list far faster than checking each element. It looks at the middle element, then discards the half that cannot contain the target, repeating until found. Each step halves the search space, so a list of $n$ items takes about $\log_2 n$ steps. It requires the data to be sorted first.
Worked example. Searching a sorted list of $8$ items, binary search halves the range each step: $8\rightarrow4\rightarrow2\rightarrow1$, at most $3$ comparisons ($\log_2 8=3$), whereas a linear search could take up to $8$. The advantage grows explosively: about $1{,}000$ items need only $\approx10$ binary-search steps (but up to $1{,}000$ linear ones), and $1{,}000{,}000$ items need just $\approx20$. Halving is what makes it a reasonable-time algorithm.
Tìm kiếm nhị phân tìm thấy một giá trị trong một danh sách đã sắp xếp nhanh hơn rất nhiều so với việc kiểm tra từng phần tử. Nó xem xét phần tử ở giữa, sau đó loại bỏ một nửa không thể chứa mục tiêu, tiếp tục lặp lại cho đến khi tìm thấy. Mỗi bước giảm một nửa không gian tìm kiếm, vì vậy một danh sách $n$ phần tử mất khoảng $\log_2 n$ bước. Nó yêu cầu dữ liệu phải được sắp xếp trước tiên.
Ví dụ minh họa. Tìm kiếm trong một danh sách đã sắp xếp $8$ phần tử, tìm kiếm nhị phân giảm một nửa phạm vi ở mỗi bước: $8\rightarrow4\rightarrow2\rightarrow1$, tối đa $3$ phép so sánh ($\log_2 8=3$), trong khi tìm kiếm tuyến tính có thể mất tới $8$. Lợi thế tăng trưởng theo cấp số nhân: khoảng $1{,}000$ phần tử chỉ cần $\approx10$ bước tìm kiếm nhị phân (nhưng tới $1{,}000$ bước tìm kiếm tuyến tính), và $1{,}000{,}000$ phần tử chỉ cần $\approx20$. Việc giảm một nửa chính là điều khiến nó trở thành một thuật toán có thời gian xử lý hợp lý.
| English | Tiếng Việt |
|---|---|
| Binary search/ˈbaɪnəri sɜːtʃ/ | Tìm kiếm nhị phân |
Enduring Understanding (AAP-3): Programmers break down problems into smaller and more manageable pieces. By creating procedures and leveraging parameters, programmers generalize processes that can be reused. Procedures allow programmers to draw upon existing code that has already been tested, allowing them to write programs more quickly and with more confidence.
Learning Objective AAP-3.A: For procedure calls: a. Write statements to call procedures. [Skill 3.B] b. Determine the result or effect of a procedure call. [Skill 4.B]
AAP-3.A.1 A procedure is a named group of programming instructions that may have parameters and return values.
AAP-3.A.2 Procedures are referred to by different names, such as method or function, depending on the programming language.
AAP-3.A.3 Parameters are input variables of a procedure. Arguments specify the values of the parameters when a procedure is called.
AAP-3.A.4 A procedure call interrupts the sequential execution of statements, causing the program to execute the statements within the procedure before continuing. Once the last statement in the procedure (or a return statement) has executed, flow of control is returned to the point immediately following where the procedure was called.
AAP-3.A.5 The exam reference sheet provides
procName(arg1, arg2, ...)
as a way to call
Text:
PROCEDURE procName(parameter1, parameter2, ...)
{
<block of statements>
}
Block:
PROCEDURE procName parameter1, parameter2,...
block of statements
which takes zero or more arguments; arg1 is assigned to parameter1, arg2 is assigned to parameter2, and so on.
AAP-3.A.6 The exam reference sheet provides the procedure
Text:
DISPLAY(expression)
Block:
DISPLAY expression
to display the value of expression, followed by a space.
AAP-3.A.7 The exam reference sheet provides the
Text:
RETURN(expression)
Block:
RETURN expression
statement, which is used to return the flow of control to the point where the procedure was called and to return the value of expression.
AAP-3.A.8 The exam reference sheet provides
result ← procName(arg1, arg2, ...)
to assign to result the "value of the procedure" being returned by calling
Text:
PROCEDURE procName(parameter1, parameter2, ...)
{
<block of statements>
RETURN(expression)
}
Block:
PROCEDURE procName parameter1, parameter2,...
block of statements
RETURN expression
AAP-3.A.9 The exam reference sheet provides procedure
Text:
INPUT()
Block:
INPUT
which accepts a value from the user and returns the input value.
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 đó.
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
A procedure (function) 过程 is a named, reusable block of code. Calling it runs its code with the arguments you supply, and it may return a value:
Procedures let you use code without knowing its inner workings – procedural abstraction 过程抽象.
Một quy trình (function) là một khối code có tên và có thể tái sử dụng. Gọi nó sẽ thực thi code của quy trình đó với các tham số bạn cung cấp, và nó có thể trả về một giá trị:
sum ← Add(3, 4) // call, passing 3 and 4
Các quy trình cho phép bạn sử dụng code mà không cần biết chi tiết hoạt động bên trong — đó là trừu tượng hóa quy trình (procedural abstraction).
| English | Tiếng Việt |
|---|---|
| procedural abstraction/prəˈsiːdʒərəl əbˈstrækʃn/ | trừ抽象 hóa thủ tục |
| abstraction/əbˈstrækʃn/ | trừu tượng hóa |
| library/ˈlaɪbrəri/ | thư viện (library) |
| simulation/ˌsɪmjʊˈleɪʃn/ | mô phỏng |
| Efficiency/ɪˈfɪʃənsi/ | Hiệu quả |
Enduring Understanding (AAP-3): Programmers break down problems into smaller and more manageable pieces. By creating procedures and leveraging parameters, programmers generalize processes that can be reused. Procedures allow programmers to draw upon existing code that has already been tested, allowing them to write programs more quickly and with more confidence.
Learning Objective AAP-3.B: Explain how the use of procedural abstraction manages complexity in a program. [Skill 3.C]
Learning Objective AAP-3.C: Develop procedural abstractions to manage complexity in a program by writing procedures. [Skill 3.B]
AAP-3.C.1 The exam reference sheet provides
Text:
PROCEDURE procName(parameter1, parameter2, ...)
{
<block of statements>
}
Block:
PROCEDURE procName parameter1, parameter2,...
block of statements
which is used to define a procedure that takes zero or more arguments. The procedure contains block of statements.
AAP-3.C.2 The exam reference sheet provides
Text:
PROCEDURE procName(parameter1, parameter2, ...)
{
<block of statements>
RETURN(expression)
}
Block:
PROCEDURE procName parameter1, parameter2,...
block of statements
RETURN expression
which is used to define a procedure that takes zero or more arguments. The procedure contains block of statements and returns the value of expression. The RETURN statement may appear at any point inside the procedure and causes an immediate return from the procedure back to the calling statement.
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]
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.
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
You define a procedure with a name, parameters (inputs), and a body, and optionally RETURN a result:
Writing your own procedures reduces repetition, breaks a big problem into named pieces, and makes programs readable and easier to test – the essence of abstraction 抽象.
Bạn định nghĩa một quy trình với tên, tham số (dữ liệu đầu vào), và thân quy trình, và tùy chọn RETURN một kết quả trả về:
PROCEDURE Add(a, b)
{
RETURN(a + b)
}
Viết các quy trình của riêng bạn giúp giảm bớt sự lặp lại, chia nhỏ một vấn đề lớn thành các phần có tên, và làm cho chương trình dễ đọc và dễ kiểm tra hơn — đó là cốt lõi của trừu tượng hóa.
| English | Tiếng Việt |
|---|---|
| procedure (function)/prəˈsiːdʒə/ | thuật toán (hàm) |
Enduring Understanding (AAP-3): Programmers break down problems into smaller and more manageable pieces. By creating procedures and leveraging parameters, programmers generalize processes that can be reused. Procedures allow programmers to draw upon existing code that has already been tested, allowing them to write programs more quickly and with more confidence.
Learning Objective AAP-3.D: Select appropriate libraries or existing code segments to use in creating new programs. [Skill 2.B]
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]
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
A library 库 is a collection of ready-made procedures that others can reuse. An API (Application Program Interface) 应用程序接口 documents what each procedure does, its parameters, and its result – so you can use it without seeing its code. Libraries save time and let you build on existing, tested work.
The documentation is part of the library. Documentation for an API or library is necessary in order to understand the behaviours it provides and how to use them — what each procedure expects as parameters, what it returns, and what it does at the edges. Without it you would have to read the source, which defeats the point of abstraction; with it you can use a procedure correctly without knowing how it works inside.
Một thư viện là tập hợp các quy trình sẵn sàng mà người khác có thể tái sử dụng. Một API (Giao diện Lập trình Ứng dụng) tài liệu hóa xem mỗi quy trình làm gì, các tham số của nó và kết quả trả về — vì vậy bạn có thể sử dụng nó mà không cần nhìn vào code của nó. Thư viện tiết kiệm thời gian và cho phép bạn xây dựng dựa trên công việc đã có sẵn và đã được kiểm chứng.
Tài liệu là một phần của thư viện. Tài liệu cho API hoặc thư viện là cần thiết để hiểu các hành vi mà nó cung cấp và cách sử dụng chúng — mỗi quy trình yêu cầu tham số gì, trả về gì, và làm gì ở các trường hợp đặc biệt. Không có tài liệu, bạn sẽ phải đọc source code, điều đó vô ích đối với trừu tượng hóa; với tài liệu, bạn có thể sử dụng đúng cách một quy trình mà không cần biết hoạt động bên trong của nó.
Enduring Understanding (AAP-3): Programmers break down problems into smaller and more manageable pieces. By creating procedures and leveraging parameters, programmers generalize processes that can be reused. Procedures allow programmers to draw upon existing code that has already been tested, allowing them to write programs more quickly and with more confidence.
Learning Objective AAP-3.E: For generating random values: a. Write expressions to generate possible values. [Skill 2.B] b. Evaluate expressions to determine the possible results. [Skill 4.B]
AAP-3.E.1 The exam reference sheet provides
Text:
RANDOM(a, b)
Block:
RANDOM a, b
which generates and returns a random integer from a to b, inclusive. Each result is equally likely to occur. For example, RANDOM(1, 3) could return 1, 2, or 3.
AAP-3.E.2 Using random number generation in a program means each execution may produce a different result.
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.
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
RANDOM(a, b) returns a random integer from a to b (inclusive), letting a program produce unpredictable results – for games, sampling, or simulations. Each call may give a different value, so a program using randomness behaves differently each run.
RANDOM(a, b) trả về một số nguyên ngẫu nhiên từ a đến b (bao gồm cả hai đầu mút), cho phép chương trình tạo ra các kết quả không thể dự đoán được — phục vụ cho trò chơi, lấy mẫu, hoặc mô phỏng. Mỗi lần gọi có thể trả về một giá trị khác nhau, do đó một chương trình sử dụng tính ngẫu nhiên sẽ hoạt động khác nhau ở mỗi lần chạy.
Enduring Understanding (AAP-3): Programmers break down problems into smaller and more manageable pieces. By creating procedures and leveraging parameters, programmers generalize processes that can be reused. Procedures allow programmers to draw upon existing code that has already been tested, allowing them to write programs more quickly and with more confidence.
Learning Objective AAP-3.F: For simulations: a. Explain how computers can be used to represent real-world phenomena or outcomes. [Skill 1.A] b. Compare simulations with real-world contexts. [Skill 1.D]
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]
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
A simulation 模拟 is a program that models a real-world process to study it safely and cheaply. Simulations simplify reality (they leave out detail) and often use randomness to imitate chance events. They let you test scenarios that would be too costly, slow, or dangerous in real life – but their results are only as good as their assumptions.
A simulation is a way of doing science, not just a picture. Because it can be run many times, cheaply and with one variable changed at a time, a simulation facilitates the formulation and refinement of hypotheses about the object or phenomenon under consideration: you propose an explanation, run the model, compare the result with reality, and adjust either the hypothesis or the model. That is why a simulation's simplifications matter — a result only supports a hypothesis about the real world to the extent that what was left out does not matter.
Một mô phỏng là một chương trình mô hình hóa một quá trình thực tế để nghiên cứu nó một cách an toàn và rẻ tiền. Mô phỏng đơn giản hóa thực tế (loại bỏ các chi tiết) và thường sử dụng tính ngẫu nhiên để mô phỏng các sự kiện ngẫu nhiên. Chúng cho phép bạn thử nghiệm các kịch bản mà trong đời thực sẽ quá tốn kém, chậm chạp, hoặc nguy hiểm — nhưng kết quả của chúng chỉ tốt bằng các giả định của chúng.
Mô phỏng là một phương pháp làm khoa học, không chỉ đơn thuần là một bức tranh. Vì nó có thể được chạy nhiều lần, rẻ tiền và chỉ thay đổi một biến số tại một thời điểm, mô phỏng thúc đẩy việc xây dựng và tinh chỉnh các giả thuyết về đối tượng hoặc hiện tượng đang xem xét: bạn đưa ra một lời giải thích, chạy mô hình, so sánh kết quả với thực tế, và điều chỉnh cả giả thuyết lẫn mô hình. Đó là lý do tại sao những sự đơn giản hóa của mô phỏng lại quan trọng — một kết quả chỉ hỗ trợ một giả thuyết về thế giới thực ở mức độ mà những gì bị loại bỏ không quan trọng.
Enduring Understanding (AAP-4): There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.
Learning Objective AAP-4.A: For determining the efficiency of an algorithm: a. Explain the difference between algorithms that run in reasonable time and those that do not. [Skill 1.D] b. Identify situations where a heuristic solution may be more appropriate. [Skill 1.D]
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]
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
Efficiency 效率 is how much time (or memory) an algorithm needs as its input grows. A reasonable-time algorithm's work grows like a polynomial of the input size (e.g. linear or quadratic); an unreasonable-time algorithm grows far faster (e.g. doubling with each added item), becoming impractical for large inputs. A faster algorithm can make a previously impossible problem solvable. Sometimes an exact answer takes too long, so a heuristic 启发式 – an approach that finds a good-enough answer quickly – is used instead.
Hiệu suất là lượng thời gian (hoặc bộ nhớ) mà thuật toán cần thiết khi dữ liệu đầu vào tăng lên. Một thuật toán thời gian hợp lý có khối lượng công việc tăng theo đa thức của kích thước đầu vào (ví dụ: tuyến tính hoặc bậc hai); một thuật toán thời gian không hợp lý tăng nhanh hơn nhiều (ví dụ: nhân đôi với mỗi mục được thêm vào), trở nên bất khả thi đối với dữ liệu đầu vào lớn. Một thuật toán nhanh hơn có thể biến một vấn đề trước đây không thể giải quyết thành có thể. Đôi khi một đáp án chính xác tốn quá lâu, vì vậy người ta sử dụng thuật toán tham khảo (heuristic) – một phương pháp tìm ra đáp án đủ tốt một cách nhanh chóng thay thế.
| English | Tiếng Việt |
|---|---|
| heuristic/hjuːˈrɪstɪk/ | phương tiện heuristic |
| undecidable/ˌʌndɪˈsaɪdəbl/ | không thể giải quyết |
| Interface/ˈɪntəfeɪs/ | Giao diện |
Enduring Understanding (AAP-4): There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.
Learning Objective AAP-4.B: Explain the existence of undecidable problems in computer science. [Skill 1.A]
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]
Source: College Board AP Course and Exam Description · Nguồn: Mô tả Khóa học và Bài thi College Board AP
Some problems are undecidable 不可判定: no algorithm can solve every case of them with a correct yes/no answer. This is a fundamental limit of computing – not a matter of needing a faster computer, but a proof that no such algorithm can exist.
Exam skill: be able to determine a code segment's result by tracing it, compare two algorithms' efficiency (reasonable vs unreasonable time), and recognize procedural and data abstraction in a program.
Một số vấn đề là không quyết định được: không có thuật toán nào có thể giải quyết mọi trường hợp của chúng bằng câu trả lời đúng/sai chính xác. Đây là giới hạn cơ bản của máy tính – không phải do thiếu máy tính nhanh hơn, mà là bằng chứng chứng minh rằng không tồn tại thuật toán nào như vậy.
Kỹ năng làm bài thi: biết xác định kết quả của một đoạn mã bằng cách truy vết, so sánh hiệu suất của hai thuật toán (thời gian hợp lý so với không hợp lý), và nhận biết sự trừu tượng thủ tục cũng như trừu tượng dữ liệu trong chương trình.
a <- expression assigns, and lists are 1-indexed on the exam reference sheet.AND, OR, NOT).a <- expression thực hiện gán lại, và các danh sách đánh chỉ số từ 1 trên trang tham khảo kỳ thi.AND, OR, NOT).Work through it step by step, with instant-check exercises. · Làm theo từng bước, kèm theo bài tập kiểm tra ngay lập tức.
Loading subjects… · Đang tải danh sách môn…