IGCSE、A-Level & AP IGCSE, A-Level & AP シートプレビュー

アルゴリズムとプログラミング

APコンピュータサイエンス・プリンシプルズ · トピック 3

查看幻灯片 練習する
このトピックのビデオレッスン 動画ページを開く
9:17

アルゴリズムとプログラミング

Imagine a phone book with a million names, and you must find one. Check them one at a time, and you could be there all day. There is a way to find it in about…

英語ナレーション・英語＋中文字幕 burning-in

以下のコードはAP CSP擬似言語を使用しています——これは試験の言語に依存しない参照仕様です。代入演算子は a ← expression で記述され、リストのインデックスは 1 から始まります。

3.1

変数と代入
シラバス

持続的理解 (AAP-1): 一般化可能な問題に対する特定の解を見つけるために、プログラマーはデータを複数の方法で表現および整理します。

学習目標 AAP-1.A: 変数を使用して値を表記する。[スキル 3.A]

  • AAP-1.A.1 変数とは、プログラム内で値を保持できる抽象概念である。各変数にはデータストレージが関連付けられており、一度に1つの値を表すことができるが、その値はリストや他のコレクションであり、それ自体が複数の値を含んでいることもある。
  • AAP-1.A.2 意味のある変数名を使用すると、プログラムのコードの可読性が向上し、変数が何を表しているかを理解しやすくなる。
  • AAP-1.A.3 一部のプログラミング言語では、データを表現するための型を提供しており、これらは変数によって参照される。これらの型には、数、ブール値、リスト、文字列が含まれる。
  • AAP-1.A.4 一部の値は、ある種類のデータとして表現することが、別の種類よりも適している場合がある。

学習目標 AAP-1.B: 代入の結果として変数の値を決定する。[スキル 4.B]

  • AAP-1.B.1 代入演算子により、プログラムは変数が表す値を変更できる。

  • AAP-1.B.2 試験用参考シートでは、代入に使用する「$\leftarrow$」演算子が提供されている。例えば、

    テキスト:

    a ← expression

    ブロック:

    a ← expression

    expressionを評価した後に、その結果のコピーを変数aに代入する。

  • AAP-1.B.3 変数に格納された値は、最後に代入された値となる。例えば：

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

    はまだ1を表示する。

出典: College Board AP コースおよび試験説明書

変数とは名付けられた領域で値を保持します。代入演算子は右側の値を左側の変数に格納します：

変数は名前の付いたストレージであり、その値は変更可能です
変数は名前の付いたストレージであり、その値は変更可能です
a ← 5
b ← a + 3      // b is now 8

変数は一度に1つの値しか持ちません。再度代入すると上書きされます。変数を使うことで、プログラムは入力値を格納し、結果を記憶して再利用できます。

探索

変数が値を保持して変化させる様子を見る

変数とは、一度に1つの値を格納する名前の付いた箱です。代入は値を箱にコピーすることであり、再度代入するとそれまで入っていた値は上書きされます。

語彙 練習する
English 日本語
variable/ˈveərɪəbl/ 変数
assignment/əˈsaɪnmənt/ 代入
Data abstraction/ˈdeɪtə əbˈstrækʃn/ データ抽象化
remainder/rɪˈmeɪndə/ 余り
string/strɪŋ/ 文字列
concatenation/kənˌkætəˈneɪʃn/ 連結
Boolean expression/ˈbuːlɪən ekˈspreʃn/ ブーリアン式
conditional (selection)/kənˈdɪʃənl/ 条件分岐（選択）
nested conditional/ˈnestɪd kənˈdɪʃənl/ ネスト条件分岐
Iteration (a loop)/ˌɪtəˈreɪʃn/ 反復（ループ）
infinite loop/ˈɪnfɪnət luːp/ 無限ループ
algorithm/ˈælɡərɪθəm/ アルゴリズム
list/lɪst/ リスト
3.2

データ抽象化
シラバス
Enduring UnderstandingLearning ObjectiveEssential Knowledge

AAP-1
To find specific solutions to generalizable problems, programmers represent and organize data in multiple ways.

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.

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.

    • Exclusion statement (EK AAP-1.D.6): The use of linked lists is outside the scope of this course and the AP Exam.

  • 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.

出典: College Board AP コースおよび試験説明書

データ抽象化とは、複雑さを管理するために一連のデータを単一の名称で管理する方法です——例えば、数十個の個別の変数ではなく、リストを使用するといった例です。詳細は隠蔽されており、名前付きの集合体を使用する際は、その格納方法について気にする必要はありません。以下のリストは、本コースにおける主要なデータ抽象化です。

3.3

数学的式
シラバス

持続的認識 (AAP-2): プログラム内の文の順序と組み合わせが計算結果を決定する。プログラムは反復構造と選択構造を取り入れ、繰り返しを表したり、多様な入力値に対応するために判断を行う。

学習目標 AAP-2.A: プログラミング言語を使用せずに、順序構成を用いるアルゴリズムを表す。[スキル 2.A]

  • AAP-2.A.1 アルゴリズム とは、特定のタスクを達成するための有限の命令のセットである。
  • AAP-2.A.2 視覚的およびテキストベースのプログラミング言語以外でも、アルゴリズムは自然言語、図、擬似コードなど、多様な方法で表現できる。
  • AAP-2.A.3 プログラムによって実行されるアルゴリズムは、プログラミング言語を使用して実装される。
  • AAP-2.A.4 どのアルゴリズムも、順序構成、選択、反復の組み合わせによって構築できる。

学習目標 AAP-2.B: 順次コード文を使用して、段階的なアルゴリズムプロセスを表現する。[スキル 2.B]

  • AAP-2.B.1 順序構成 とは、アルゴリズムの各ステップを、コード文に与えられた順に適用することである。
  • AAP-2.B.2 コード文 とは、実行すべきアクションを表すプログラムのコードの一部である。
  • AAP-2.B.3 式 は、値、変数、演算子、または値を返す手続き呼び出しで構成される可能性がある。
  • AAP-2.B.4 式は評価されて単一の値を生成する。
  • AAP-2.B.5 式の評価は、プログラミング言語によって定義された演算子の優先順位に従って行われる。
  • AAP-2.B.6 順次文は、コードセグメント内に現れる順に実行される。
  • AAP-2.B.7 プログラミング言語でアルゴリズムを表現する際は、明瞭さと読易性が重要な考慮事項となる。

学習目標 AAP-2.C: 算術演算子を使用した式を評価する。[スキル 4.B]

  • AAP-2.C.1 算術演算子はほとんどのプログラミング言語に含まれており、加算、減算、乗算、除算、および剰余演算子が含まれる。

  • AAP-2.C.2 試験用参考シートには a MOD b が提供されており、これは a を b で割ったときの余りを評価する。a は 0 以上の整数であり、b は 0 より大きい整数であると仮定する。例えば、17 MOD 5 は 2 に評価される。

  • AAP-2.C.3 試験用参考資料には、演算子+、-、*、/、MODが記載されています。

    テキストとブロック：

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

    これらは a と b に対する算術計算を行うために使用される。例えば、17 / 5 は 3.4 に評価される。

  • AAP-2.C.4 数学で使用される演算子の優先順位は、式の評価にも適用される。MOD 演算子の優先順位は、* および / 演算子と同じである。

出典: College Board AP コースおよび試験説明書

プログラムは演算子 +, -, *, /, MOD で計算を行います（17 MOD 5 は除数の剰余、例：2 の場合）。式は通常の演算優先順に従います。MOD は整除テスト（n MOD 2 = 0 は n が偶数であることを意味する）や、値を範囲内でラップさせるのに特に有用です。

探索

式を段階的に評価する

式は演算の優先順に従って評価されます：掛け算や割り算は足し算や引き算より先に実行され、左から右へ進みます。

3.4

ストリング（文字列）
シラバス

持続的認識 (AAP-2): プログラム内の文の順序と組み合わせが計算結果を決定する。プログラムは反復構造と選択構造を取り入れ、繰り返しを表したり、多様な入力値に対応するために判断を行う。

学習目標 AAP-2.D: ストリングを操作する式を評価する。[スキル 4.B]

  • AAP-2.D.1 ストリング連結 とは、2つ以上のストリングを前後につなげて新しいストリングを作成することである。
  • AAP-2.D.2 部分ストリング とは、既存のストリングの一部である。

出典: College Board AP コースおよび試験説明書

文字列は文字の順序付けられた配列であり、"hello" のようなものです。プログラムは文字列を結合（連結）したり、その長さを確認したりします。文字列はテキスト——氏名、メッセージ、配列——を表し、プログラムの一般的な入出力として用いられます。

3.5

ブール式
シラバス
Enduring UnderstandingLearning ObjectiveEssential Knowledge

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.

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 = b
    • a ≠ b
    • a > b
    • a < b
    • a ≥ b
    • a ≤ b

    These 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.

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.

出典: College Board AP コースおよび試験説明書

ブール式は true または false に評価されます。比較演算子（=, ≠, <, >, ≤, ≥）および論理演算子 NOT, AND, OR を使用します：

3種類の演算子のファミリー: 算術演算子、関係演算子、論理演算子
3種類の演算子のファミリー: 算術演算子、関係演算子、論理演算子
  • NOT は値を反転させ、
  • AND は両方の側が真の場合のみ真となります。
  • OR は少なくとも一方の側が真の時に真です。

これらの条件がすべての決定とループを駆動します。

探索

ORの真偽表を試す

ブール式は真（1）か偽（0）のどちらかです。ORは少なくとも1つの入力が真の場合に真となります。入力を変化させてすべてのケースを見てみましょう。

3.6

条件分岐
シラバス
Enduring UnderstandingLearning ObjectiveEssential Knowledge

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.

AAP-2.G
Express an algorithm that uses selection without using a programming language. [Skill 2.A]

  • AAP-2.G.1 Selection determines which parts of an algorithm are executed based on a condition being true or false.

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.

出典: College Board AP コースおよび試験説明書

条件分岐（選択） は実行すべきコードを選びます。IF は条件が真の場合にブロックのみを実行し、ELSE は代替案を提供します：

条件に基づいてパスを選択する
条件に基づいてパスを選択する
IF (score ≥ 60)
{
    DISPLAY("Pass")
}
ELSE
{
    DISPLAY("Fail")
}
探索

if / else の決定をたどる

条件分岐は条件が真かどうかに応じて、ある分岐または別の分岐を実行します。値を閾値スライドさせて、どの分岐が実行されるか確認してください。

3.7

重層条件分岐
シラバス

持続的認識 (AAP-2): プログラム内の文の順序と組み合わせが計算結果を決定する。プログラムは反復構造と選択構造を取り入れ、繰り返しを表したり、多様な入力値に対応するために判断を行う。

学習目標 AAP-2.I: 階層化された選択について： a. 階層化された条件分岐文を書く。[スキル 2.B] b. 階層化された条件分岐文の結果を判定する。[スキル 4.B]

  • AAP-2.I.1 階層化された条件分岐文とは、条件分岐文の中に条件分岐文が含まれるものです。

出典: College Board AP コースおよび試験説明書

ネスト条件分岐は、他の条件分岐の中に1つの IF を配置したり（ELSE IF を連鎖させたり）して、2つ以上の経路の中から選択します。最初に一致した分支だけが実行されます：

IF (g ≥ 90)      { grade ← "A" }
ELSE IF (g ≥ 80) { grade ← "B" }
ELSE             { grade ← "C" }
3.8

反復 (Iteration)
シラバス
Enduring UnderstandingLearning ObjectiveEssential Knowledge

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.

AAP-2.J
Express an algorithm that uses iteration without using a programming language. [Skill 2.A]

  • AAP-2.J.1 Iteration is a repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met.

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.

出典: College Board AP コースおよび試験説明書

反復（ループ） とは、指示を繰り返すことです。AP擬似言語には2つの形式があります：

事前条件（WHILE）ループは本体前にテストを行うため、0回実行される可能性がある
事前条件（WHILE）ループは本体前にテストを行うため、0回実行される可能性がある
REPEAT 5 TIMES        // a fixed count
{
    DISPLAY("hi")
}

REPEAT UNTIL (found)  // until a condition becomes true
{
    ...
}

終了条件に一度も到達しないループは無限ループです。

探索

ループを1パスずつトレースする

ループはカウンタが範囲を通過する間にブロックを反復します。ステップ操作で counter と累積和が各パスごとに更新される様子を見てください。

3.9

アルゴリズムの開発
シラバス

持続的認識 (AAP-2): プログラム内の文の順序と組み合わせが計算結果を決定する。プログラムは反復構造と選択構造を取り入れ、繰り返しを表したり、多様な入力値に対応するために判断を行う。

学習目標 AAP-2.L: 複数のアルゴリズムを比較し、同じ副作用や結果をもたらすかどうかを判定する。[スキル 1.D]

  • AAP-2.L.1 アルゴリズムは異なる方法で書かれても、同じタスクを達成できます。
  • AAP-2.L.2 似ているように見えるアルゴリズムでも、異なる副作用や結果をもたらすことがあります。
  • AAP-2.L.3 一部の条件分岐文は、同等のブール式として書くことができます。
  • AAP-2.L.4 一部のブール式は、同等の条件分岐文として書くことができます。
  • AAP-2.L.5 異なる問題解決のために、異なるアルゴリズムを開発したり使用したりすることができます。

学習目標 AAP-2.M: アルゴリズムについて： a. アルゴリズムを作成する。[スキル 2.A] b. 既存のアルゴリズムを組み合わせたり、修改したりする。[スキル 2.B]

  • AAP-2.M.1 アルゴリズムは、アイデアから作成したり、既存のアルゴリズムを組み合わせたり、既存のアルゴリズムを修改したりして作成できます。
  • AAP-2.M.2 既存のアルゴリズムに関する知識は、新しいアルゴリズムを構築する際に役立ちます。主な既存アルゴリズムには以下が含まれます：
    • 2つ以上の数字の最大値または最小値を決定する
    • 2つ以上の数字の和または平均を計算する
    • 整数が他の整数で割り切れるかどうかを特定する
    • ロボットが迷路を通る経路を決定する
  • AAP-2.M.3 既存の正しいアルゴリズムを他のアルゴリズムを構築するための構成要素として使用することは、開発時間の短縮、テストの削減、およびエラーの特定を簡素化するなどの利点があります。

出典: College Board AP コースおよび試験説明書

画面に表示されたPythonソースコード — アルゴリズムは正確で順序付けられた指示である
画面に表示されたPythonソースコード — アルゴリズムは正確で順序付けられた指示である

アルゴリズムとコードは異なるものです。 視覚的・テキストベースのプログラミング言語に加え、アルゴリズムは多様な方法で表現できます：自然言語（日常の文）、フローチャートのような図表、または擬似コードです。これらの形式は人間向けであり、どの言語を選ぶ前に論理を確認し合意を得ることを可能にし、その後のアルゴリズムを任意の言語で記述できるためです。

プログラミング言語で記述する場合、明瞭さと可読性は重要な考慮事項であり、単なる装飾ではありません：意味のある変数名、一貫したインデント、何をするかではなくなぜそれをするかを説明するコメントなどです。プログラムは後で誰か（多くの場合あなた自身）によって読み取られ修正される必要がありますが、だれにも追跡できないアルゴリズムは保守やデバッグができません。

アルゴリズムとは、問題を解決するための有限のステップ列であり、順次処理、選択、および反復から構成されます。異なるアルゴリズムで同じ問題を解くことができ、既存のアルゴリズムを組み合わせたり変更したりできる必要があります（例：条件を満たすリストの値を数える、または最大値を見つける）。手動でアルゴリズムをトレースして正しさを確認します。

標準的な記号を使用してアルゴリズムをレイアウトするフローチャート
標準的な記号を使用してアルゴリズムをレイアウトするフローチャート
3.10

リスト
シラバス
Enduring UnderstandingLearning ObjectiveEssential Knowledge

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.

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]

  • AAP-2.N.1 The exam reference sheet provides basic operations on lists, including:

    • 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.

  • AAP-2.N.2 List procedures are implemented in accordance with the syntax rules of the programming language.

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.

    • Exclusion statement (EK AAP-2.O.1): Traversing multiple lists at the same time using the same index for both (parallel traversals) is outside the scope of this course and the AP Exam.

  • 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:

    • determining a minimum or maximum value in a list
    • computing a sum or average of a list of numbers

  • 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.

出典: College Board AP コースおよび試験説明書

リストとは、一つの名前の下に格納される値の順序付き集合であり、コースにおける主要なデータ抽象です。AP擬似コードのインデックスは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

ループを使ってリストを Traverse し、合計、カウント、検索、または最大値の探索を行います：

FOR EACH x IN scores
{
    total ← total + x
}
3.11

二項探索法
シラバス

持続的認識 (AAP-2): プログラム内の文の順序と組み合わせが計算結果を決定する。プログラムは反復構造と選択構造を取り入れ、繰り返しを表したり、多様な入力値に対応するために判断を行う。

学習目標 AAP-2.P: 二分探索アルゴリズムについて： a. データセット内の値を見つけるために必要な反復回数を知る。[スキル 1.D] b. 二分探索を完了するために必要な要件を説明する。[スキル 1.A]

  • AAP-2.P.1 二分探索アルゴリズムは、並べ替えられた数値データセットの中央から始まり、データの半分を除外します。このプロセスは、望む値が見つかるか、すべての要素が除外されるまで繰り返されます。
    • 除外事項 (EK AAP-2.P.1): 二分探索の具体的な実装は、本コースおよびAP試験の範囲外である。
  • AAP-2.P.2 データは二分探索アルゴリズムを使用するために並べ替えられている必要がある。
  • AAP-2.P.3 並べ替えられたデータに適用する場合、二分探索は順次/線形探索よりも効率的であることが多い。

出典: College Board AP コースおよび試験説明書

電話帳：二項探索法は各ステップで残りのページ数を半分にする
電話帳：二項探索法は各ステップで残りのページ数を半分にする

二項探索法は、整列されたリスト内で値を探す際、各要素をチェックする方法よりもはるかに速いです。中央の要素を確認し、ターゲットが含まれ得ない半分を破棄し、見つかれるまで繰り返します。各ステップで探索範囲が半分になるため、$n$個の要素を持つリストには約$\log_2 n$ステップ必要です。データが最初に整列されていることが必須です。

二項探索法は各ステップで範囲を半分にする（リストは整列されている必要がある）
二項探索法は各ステップで範囲を半分にする（リストは整列されている必要がある）

計算例。 $8$個の要素が並べ替えられたリストを検索する場合、二項探索法は各ステップで探索範囲を半分にする。つまり、$8\rightarrow4\rightarrow2\rightarrow1$回、最大でも$3$回の比較で済む（$\log_2 8=3$）。一方、線形探索では最大で$8$回の比較が必要になる可能性がある。その差は爆発的に拡大する：$1{,}000$個の要素であれば、二項探索法ではわずか$\approx10$回のステップで済むが、線形探索では最大で$1{,}000$回必要となる。さらに$1{,}000{,}000$個の要素であっても、二項探索法なら$\approx20$回だけで十分である。この「半分にする」プロセスこそが、このアルゴリズムを実用的な時間複雑度を持つものとしているのだ。

語彙 練習する
English 日本語
Binary search/ˈbaɪnəri sɜːtʃ/ 二項探索
3.12

プロシージャの呼び出し
シラバス

持続的認識（AAP-3）: プログラマーは問題をより小さく、管理しやすい部分に分解します。手続とパラメータを作成し活用することで、再利用可能なプロセスを一般化できます。手続により、プログラマーは既にテスト済みの既存コードを活用できるため、より速く、かつ自信を持ってプログラムを書くことができます。

学習目標 AAP-3.A: 手続呼び出しについて： a. 手続を呼び出す文を書きなさい。[スキル 3.B] b. 手続呼び出しの結果または効果を確認しなさい。[スキル 4.B]

  • AAP-3.A.1 手続とは、パラメータや返り値を持つ可能性のある、名付けられたプログラミング指令のグループです。

  • AAP-3.A.2 手続は、使用するプログラミング言語によって異なる名称で呼ばれます。例えば メソッド や 関数 などです。

  • AAP-3.A.3 パラメータ は手続の入力変数です。引数 は、手続が呼び出された際にパラメータに割り当てられる値を指定します。

  • AAP-3.A.4 手続呼び出しは、文の順次実行を中断し、プログラムが手続内の文を実行してから継続するようにします。手続の最後の文（または戻り文）が実行されれば、制御フローは手続が呼び出された直後のポイントに戻ります。

  • AAP-3.A.5 試験用参考シートには

    procName(arg1, arg2, ...)

が、

テキスト:

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

ブロック:

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

を呼び出す方法として提供されています； arg1 は parameter1 に、arg2 は parameter2 に割り当てられ、その後も同様に割り当てられます。

  • AAP-3.A.6 試験参考シートには手順が記載されている。

    テキスト:

    DISPLAY(expression)

    ブロック:

    DISPLAY expression

    expression の値を表示し、その後にスペースを出力します。

  • AAP-3.A.7 試験参考書には、

    テキスト:

    RETURN(expression)

    ブロック:

    RETURN expression

ステートメントが記載されており、これは制御の流れをプロシージャの呼び出し元に戻し、expression の値を返すために使用される。

  • AAP-3.A.8 試験参考書には、

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

が記載されており、result に「プロシージャ」に値を渡して呼び出すことで返される値を割り当てる。

テキスト:

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

ブロック:

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

  • AAP-3.A.9 試験用参考シートには手順が記載されている

    テキスト:

    INPUT()

    ブロック:

    INPUT

はユーザーから値を受け取り、入力値を返す。

出典: College Board AP コースおよび試験説明書

プロシージャ（関数） とは、名前がついた再利用可能なコードブロックです。呼び出すことで提供した引数を用いてそのコードを実行し、返却値を返すことがあります：

sum ← Add(3, 4)      // call, passing 3 and 4

プロシージャを使うことで、内部構造を知ることなくコードを利用できます——これが手続的抽象です。

3.13

プロシージャの開発
シラバス

持続的認識（AAP-3）: プログラマーは問題をより小さく、管理しやすい部分に分解します。手続とパラメータを作成し活用することで、再利用可能なプロセスを一般化できます。手続により、プログラマーは既にテスト済みの既存コードを活用できるため、より速く、かつ自信を持ってプログラムを書くことができます。

学習目標 AAP-3.B: プロシージャ抽象の使用がプログラム内の複雑さをどのように管理するかを説明する。[スキル 3.C]

  • AAP-3.B.1 一般的な抽象の一種にプロシージャ抽象がある。これはプロセスに名前を与え、プロシージャが何をしているかを知るだけで、どうやってそれをやっているかを知ることなく使用できるようにする。
  • AAP-3.B.2 プロシージャ抽象は、大きな問題の解決をより小さな部分問題の解決に基づかせることを可能にする。これは、各部分問題を解決するためのプロシージャを作成することで達成される。
  • AAP-3.B.3 コンピュータプログラムを個別のサブプログラムに分割することをモジュラリティと呼ぶ。
  • AAP-3.B.4 プロシージャ抽象は、コードを重複させるのではなく共通の機能を引き出して機能を一般化できる。これにより、プログラムのコード再利用が可能になり、複雑性の管理に役立つ。
  • AAP-3.B.5 パラメータを使用することで手続を一般化でき、異なる入力値や引数を用いて手続を再利用することが可能になる。
  • AAP-3.B.6 プロシージャ抽象を使用すると、コードの可読性が向上する。
  • AAP-3.B.7 プログラムでプロシージャ抽象を使用すると、プロシージャが何を行うかを維持したまま、内部（処理速度の向上、効率化、メモリ使用量の削減など）を変更しても、変更をユーザーに通知する必要がない。

学習目標 AAP-3.C: プロシージャを記述することにより、プログラム内の複雑性を管理するためのプロシージャ抽象を開発する。[スキル 3.B]

  • AAP-3.C.1 試験参考書には、

    テキスト:

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

    ブロック:

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

が記載されており、ゼロ以上の引数を取るプロシージャを定義するために使用される。このプロシージャ内には block of statements が含まれる。

  • AAP-3.C.2 試験参考書には

    テキスト:

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

    ブロック:

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

零個或多個引數的程式（procedure）を定義するために使用されます。この程式は block of statements を含み、expression の値を返します。RETURN 文は程式内の任意の位置に配置でき、その時点で直ちに呼び出し元へ戻ります。

出典: College Board AP コースおよび試験説明書

プロシージャは、パラメータ（入力）、本体、そして optionally RETURN 結果を含めて定義します：

プログラムをプロシージャとサブプロシージャに分解する
プログラムをプロシージャとサブプロシージャに分解する
PROCEDURE Add(a, b)
{
    RETURN(a + b)
}

独自のプロシージャを作成することは、重複を減らし、大きな問題を名付けた部分に分割し、プログラムを可读にしてテストしやすくすることを可能にします——これは抽象化の本質です。

語彙 練習する
English 日本語
procedure (function)/prəˈsiːdʒə/ 手続（関数）
procedural abstraction/prəˈsiːdʒərəl əbˈstrækʃn/ 手続的抽象化である
abstraction/əbˈstrækʃn/ 抽象化
library/ˈlaɪbrəri/ ライブラリ
simulation/ˌsɪmjʊˈleɪʃn/ シミュレーション
Efficiency/ɪˈfɪʃənsi/ 効率性
heuristic/hjuːˈrɪstɪk/ ヒューリスティック
undecidable/ˌʌndɪˈsaɪdəbl/ 判定不能である
Interface/ˈɪntəfeɪs/ インターフェース
3.14

ライブラリ
シラバス

持続的認識（AAP-3）: プログラマーは問題をより小さく、管理しやすい部分に分解します。手続とパラメータを作成し活用することで、再利用可能なプロセスを一般化できます。手続により、プログラマーは既にテスト済みの既存コードを活用できるため、より速く、かつ自信を持ってプログラムを書くことができます。

学習目標 AAP-3.D： 新しいプログラムを作成する際に適切なライブラリや既存コードセグメントを選択する。[スキル 2.B]

  • AAP-3.D.1 ソフトウェアライブラリには、新しいプログラムの作成に利用可能な程式が含まれています。
  • AAP-3.D.2 既存のコードセグメントは、ライブラリや過去に記述したコードなど、内部または外部のソースから取得できます。
  • AAP-3.D.3 ライブラリの使用は、複雑なプログラムの作成作業を簡素化します。
  • AAP-3.D.4 アプリケーション・プログラミング・インターフェース（API）とは、ライブラリ内の程式の振る舞いや使用方法を規定する仕様です。
  • AAP-3.D.5 API/ライブラリのドキュメントは、提供される振る舞いや使用方法を理解するために不可欠です。

出典: College Board AP コースおよび試験説明書

ライブラリとは、他の人が再利用できる既成のプロシージャの集合体です。API（アプリケーションプログラミングインターフェース）は各プロシージャが何をするか、そのパラメータ、そして返却値を文書化しており、コードを見ずに使用できます。ライブラリは時間を節約し、既存で検証済みの上乗せを可能にします。

ドキュメンテーションはライブラリの一部です。 APIやライブラリのドキュメントは、それが提供する振る舞いや使用方法を理解するために不可欠です——各プロシージャがどのようなパラメータを期待し、何を返すか、またエッジケースで何をするかです。これなければソースコードを読む必要があり、抽象化の意義が失われます；これがあれば、内部動作を知らずに正しい使い方をすることができます。

3.15

乱数値
シラバス

持続的認識（AAP-3）: プログラマーは問題をより小さく、管理しやすい部分に分解します。手続とパラメータを作成し活用することで、再利用可能なプロセスを一般化できます。手続により、プログラマーは既にテスト済みの既存コードを活用できるため、より速く、かつ自信を持ってプログラムを書くことができます。

学習目標 AAP-3.E： 乱数を生成する場合： a. 生成可能な値を表す式を書く。[スキル 2.B] b. 式を評価して得られる可能性のある結果を決定する。[スキル 4.B]

  • AAP-3.E.1 試験用参考シートには以下が記載されている

    テキスト:

    RANDOM(a, b)

    ブロック:

    RANDOM a, b

    aからbまでの範囲でランダムな整数を生成して返す。各結果が出る確率は等しい。例えば、RANDOM(1, 3)は1、2、または3を返す可能性がある。

  • AAP-3.E.2 プログラム内で乱数生成を使用する場合、実行回数が異なれば異なる結果が得られることがある。

出典: College Board AP コースおよび試験説明書

RANDOM(a, b) はa からb （両端を含む）までのランダム整数を返すことで、プログラムに予測不可能な結果を生み出させます——ゲーム、サンプリング、シミュレーション用です。各呼び出しで異なる値が返されるため、乱数を使用するプログラムは実行ごとに異なる挙動を示します。

3.16

シミュレーション
シラバス

持続的認識（AAP-3）: プログラマーは問題をより小さく、管理しやすい部分に分解します。手続とパラメータを作成し活用することで、再利用可能なプロセスを一般化できます。手続により、プログラマーは既にテスト済みの既存コードを活用できるため、より速く、かつ自信を持ってプログラムを書くことができます。

学習目標 AAP-3.F： シミュレーションについて： b. シミュレーションと現実世界との関係を比較する。[スキル 1.D] b. シミュレーションと現実世界との文脈を比較する。[スキル 1.D]

  • AAP-3.F.1 シミュレーションは、特定の目的のために、より複雑な物体や現象を抽象化したものである。
  • AAP-3.F.2 シミュレーションとは、異なる値の組み合わせを用いて現象の状態の変化を反映する表現である。
  • AAP-3.F.3 シミュレーションは、推論を下すことを目的として現実世界的事件を模倣し、現実世界における制約なしに現象を検証することを可能にする。
  • AAP-3.F.4 抽象的なシミュレーションを開発するプロセスには、具体的な詳細の削除または機能の単純化が含まれる。
  • AAP-3.F.5 シミュレーションには、採用または除外された現実世界の要素に関する選択から生じるバイアスを含むことがある。
  • AAP-3.F.6 現実世界的事件が実験に不適切な場合（例: 大きすぎる、小さすぎる、速すぎる、遅すぎる、高価すぎる、危険すぎる）、シミュレーションは最も有用である。
  • AAP-3.F.7 シミュレーションは、対象としている物体や現象に関する仮説の立案と精緻化を促進する。
  • AAP-3.F.8 乱数生成器は、現実世界に存在するばらつきをシミュレートするために使用できる。

出典: College Board AP コースおよび試験説明書

シミュレーションとは、現実のプロセスをモデル化して安全かつ安価に研究するためのプログラムです。シミュレーションは現実を単純化（詳細を省略）し、頻繁に乱数を用いて偶然の出来事を模倣します。現実では高コスト、低速、あるいは危険すぎるシナリオをテストできますが、その結果は仮定次第です。

シミュレーションは科学を行う方法であり、単なる絵画ではありません。 安価に多数回実行でき、一度に変数のみを変更できるため、対象となる物体や現象に関する仮説の立案と洗練を促進します：説明を提案し、モデルを実行し、結果と現実を比較し、仮説またはモデルのどちらかを調整します。そのため、シミュレーションの単純化は重要です——省略された要素が問題にならない限り、結果は現実世界に関する仮説を支持するだけです。

3.17

アルゴリズム効率
シラバス

持続的認識 (AAP-4): コンピュータでは解くことができない問題が存在する。また、コンピューターが問題を解ける場合でも、実用的な時間内に解くことができないこともある。

学習目標 AAP-4.A: アルゴリズムの効率性を決定するために： a. 実用的な時間で実行されるアルゴリズムとそうでないものの違いを説明する。[スキル 1.D] b. ヒューリスティック解がより適切な状況を見極める。[スキル 1.D]

  • AAP-4.A.1 問題とは、アルゴリズム的に解くこと（または解けないこと）のできるタスクの一般的な記述である。問題のインスタンスには、特定の入力も含まれる。例えば、「ソート」は一个问题であり、リスト (2,3,1,7) をソートすることはその問題のインスタンスである。
  • AAP-4.A.2 判断問題とは、yes/no の答えを持つ問題である（例: A から B への経路はあるか？）。最適化問題とは、多数の中から「最良」の解を見つけることを目的とした問題である（例: A から B への最短経路は何か？）。
  • AAP-4.A.3 効率とは、アルゴリズムによって使用される計算リソースの量を推定したものである。効率は通常、入力のサイズに対する関数として表される。
    • 除外事項 (EK AAP-4.A.3): アルゴリズムの形式解析（Big-O）および数学的式を用いた形式推論は、このコースおよびAP試験の対象外である。
  • AAP-4.A.4 アルゴリズムの効率は、形式的または数学的な推論によって決定される。
  • AAP-4.A.5 アルゴリズムの効率は、文または文のグループが実行される回数を特定することによって非形式的に測定できる。
  • AAP-4.A.6 同じ問題に対する正しいアルゴリズムであっても、効率性が異なることがある。
  • AAP-4.A.7 多項式効率またはそれより低い効率（一定、線形、平方、立方など）を持つアルゴリズムは、実用的な時間で実行されるとされる。指数関数的または階乗的な効率を持つアルゴリズムは、実用的でない時間で実行されるアルゴリズムの例である。
  • AAP-4.A.8 解決のための効率的なアルゴリズムが存在しないため、ある問題は実用的な時間内に解くことができない。このような場合、近似解が求められる。
  • AAP-4.A.9 ヒューリスティックとは、必ずしも最適解である保証はないが、常に最適解を見つける技術が実用的でない場合に使用される問題解決のアプローチである。
    • 除外事項 (AAP-4.A.9): 具体的なヒューリスティック解は、このコースおよびAP試験の対象外である。

出典: College Board AP コースおよび試験説明書

効率性とは、入力が大きくなるにつれてアルゴリズムがどの程度の時間（またはメモリ）を要するかです。実用的な時間のアルゴリズムは、入力のサイズに対する多項式のように作業量が増加します（例：線形または二次）。一方、非実用的な時間のアルゴリズムは、追加されるごとに倍増するなど、はるかに速く増加し、大きな入力に対して実用性を失います。より高速なアルゴリズムは、これまで不可能だった問題を解けるようにすることがあります。有时、正確な答えを出すのに時間がかかりすぎるため、ヒューリスティック – 十分に良い答えを素見つけるアプローチ – が代わりに使用されます。

アルゴリズムの実行時間が入力サイズ n とともにどのように増加するか
アルゴリズムの実行時間が入力サイズ n とともにどのように増加するか
3.18

判定不可能な問題
シラバス

持続的認識 (AAP-4): コンピュータでは解くことができない問題が存在する。また、コンピューターが問題を解ける場合でも、実用的な時間内に解くことができないこともある。

学習目標 AAP-4.B: コンピュータ科学における判定不能問題の存在を説明する。[スキル 1.A]

  • AAP-4.B.1 判定可能な問題とは、すべての入力に対して正しい出力を生み出すアルゴリズムを作成できる判断問題である（例: 「その数は偶数か？」）。
  • AAP-4.B.2 判定不能問題とは、常に正しいyes-or-noの回答を提供できるアルゴリズムを構築することが不可能な問題である。
    • 除外事項 (EK AAP-4.B.2): 与えられた問題が判定不能かどうかを判定することは、このコースおよびAP試験の対象外である。
  • AAP-4.B.3 判定不能問題であっても、アルゴリズムによる解があるインスタンスは存在するが、すべてのインスタンスを解くアルゴリズムは存在しない。

出典: College Board AP コースおよび試験説明書

ある問題は判定不可能です：どのアルゴリズムも、すべてのケースについて正しいはい/いいえの回答を提供することはできません。これは計算の根本的な限界であり、より速いコンピュータが必要であるという問題ではなく、そのようなアルゴリズムが存在しないことを証明したものです。

試験技能： コードセグメントの結果をトレースによって決定すること、2つのアルゴリズムの効率（合理的 vs 非合理的な時間）を比較すること、プログラムにおける手続的抽象とデータ抽象を認識すること。

3.18

試験対策
  • 変数が値に対する名付けられた格納先であることを知り、代入が段階的にそれを更新する様子をトレースできること。
  • AP 擬似コードを注意深く読む—— a <- expression は代入を行い、リストは試験用参考シート上で1から始まるインデックスを持つ。
  • 変数とリスト（インデックスによってアクセスされる collection）を区別し、リスト操作を正しく使用すること。
  • 適切な優先順位とブール論理を用いて式を評価すること（AND, OR, NOT）。
  • 明確で意味のある変数名を選ぶ——筆記課題では読みやすいコードに報酬が与えられる。

このトピックのインタラクティブ授業

一歩ずつ進め、即時チェック付きの問題で学習します。

過去問

APコンピュータサイエンス・プリンシプルズ の他のトピック

ログインまたはアカウント作成

IGCSE, A-Level & AP