IGCSE, A-Level & AP IGCSE, A-Level & AP Предпросмотр листа

Algorithms and Programming (Алгоритмы и программирование)

AP Принципы информатики · Тема 3

Просмотр слайдов Тренировать
Видеоурок по этой теме Открыть страницу видео
9:17

Algorithms and Programming (Алгоритмы и программирование)

Представьте телефонную книгу с миллионом имен, и вам нужно найти одно. Проверяйте их по очереди, и можно стоять весь день. Есть способ найти его примерно за…

Английское озвучивание · Английский + китайские субтитры (встроенные)

Приведенный ниже код использует псевдокод AP CSP — нейтральный к языкам справочник для экзамена. Присваивание записывается a ← expression, а индексы списков начинаются с 1.

3.1

Переменные и присваивания
Программа

Принципиальное понимание (AAP-1): Чтобы находить конкретные решения обобщаемых задач, программисты представляют и организуют данные различными способами.

Цель обучения AAP-1.A: Представить значение с помощью переменной. [Навык 3.A]

  • AAP-1.A.1 Переменная — это абстракция внутри программы, способная хранить значение. Для каждой переменной выделено место в памяти для хранения одного значения, однако это значение может быть списком или другим COLLECTION (набором), который, в свою очередь, содержит несколько значений.
  • AAP-1.A.2 Использование осмысленных имен переменных способствует читаемости кода программы и пониманию того, какие значения представлены переменными.
  • AAP-1.A.3 Некоторые языки программирования предоставляют типы данных для представления информации, которые ссылаются на переменные. Эти типы включают числа, логические значения (Boolean), списки и строки.
  • 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

Переменная содержит одно значение за раз; повторное присваивание заменяет его. Переменные позволяют программе хранить ввод, запоминать результаты и использовать их повторно.

Исследовать

Понаблюдайте за тем, как переменная хранит и изменяет свое значение

Переменная — это именованная ячейка, которая хранит одно значение одновременно. Присваивание копирует значение в ячейку; повторное присваивание перезаписывает то, что там находилось ранее.

Словарь Тренировать
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 элемента 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 Конкатенация строк объединяет две или более строк последовательно, чтобы создать новую строку.
  • AAP-2.D.2 Подстрока — это часть существующей строки.

Источник: Описание курса и экзамена College Board AP

Строка — это упорядоченная последовательность символов, например, "hello". Программы соединяют строки (конкатенация) и находят их длину. Строки представляют текст — имена, сообщения, последовательности — и являются распространенным входом и выходом программы.

3.5

Булевы выражения
Программа

Ключевое понимание (AAP-2): Порядок следования и комбинация инструкций в программе определяют вычисленный результат. Программы используют конструкции итерации и выбора для представления повторений и принятия решений для обработки различных входных значений.

Цель обучения AAP-2.E: Для отношений между двумя переменными, выражениями или значениями: a. Записывать выражения с использованием операторов сравнения. [Навык 2.B] b. Оценивать выражения, использующие операторы сравнения. [Навык 4.B]

  • AAP-2.E.1 Булево значение может быть истинным (true) или ложным (false).

  • AAP-2.E.2 Справочный лист для экзамена содержит следующие реляционные операторы: =, ≠, >, <, ≥ и ≤.

    Текст и Блок:

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

    Они используются для проверки соотношения между двумя переменными, выражениями или значениями. Результат сравнения с использованием реляционного оператора является логическим значением (Boolean). Например, a = b возвращает true, если a и b равны; в противном случае он возвращает false.

Цель обучения AAP-2.F: Для отношений между булевскими значениями: a. Записывать выражения с использованием логических операторов. [Навык 2.B] b. Оценивать выражения, использующие логические операторы. [Навык 4.B]

  • AAP-2.F.1 Справочный лист для экзамена содержит логические операторы NOT, AND и OR, которые возвращают логическое значение (Boolean).

  • AAP-2.F.2 Справочный листок для экзамена предоставляет

    Текст:

    NOT condition

    Блок:

    NOT condition

    который вычисляется как ⟨true⟩, если ⟨condition⟩ является ⟨false⟩; в противном случае он вычисляется как ⟨false⟩.

  • AAP-2.F.3 Справочный листок для экзамена предоставляет

    Текст:

    condition1 AND condition2

    Блок:

    condition1 AND condition2

который возвращает true, если оба condition1 и condition2 являются true; в противном случае он возвращает false.

  • AAP-2.F.4 Справочный листок для экзамена содержит

    Текст:

    condition1 OR condition2

    Блок:

    condition1 OR condition2

который возвращает true, если condition1 является true или если condition2 является true, или если оба condition1 и condition2 являются true; в противном случае он возвращает false.

  • AAP-2.F.5 Операндом логического оператора является либо булево выражение, либо одно булево значение.

Источник: Описание курса и экзамена College Board AP

Булево выражение вычисляется в true или false. Оно использует реляционные операторы (=, ≠, <, >, ≤, ≥) и логические операторы NOT, AND, OR:

Три семейства операторов: арифметические, реляционные и логические
Три группы операторов: арифметические, относительные и логические
  • NOT инвертирует значение,
  • AND истинно только тогда, когда обе стороны истинны,
  • OR истинно, когда хотя бы одна часть истинна.

Эти условия управляют каждым решением и циклом.

Исследовать

Попробуйте таблицу истинности OR

Булево выражение истинно (1) или ложно (0). Операция ИЛИ истинна, когда хотя бы один вход истинен; измените входы, чтобы рассмотреть все варианты.

3.6

Условные конструкции
Программа

Ключевое понимание (AAP-2): Порядок следования и комбинация инструкций в программе определяют вычисленный результат. Программы используют конструкции итерации и выбора для представления повторений и принятия решений для обработки различных входных значений.

Цель обучения AAP-2.G: Описать алгоритм, использующий выбор (selection), без применения языка программирования. [Навык 2.A]

  • AAP-2.G.1 Выбор определяет, какие части алгоритма выполняются, основываясь на том, является ли условие true или false.

Цель обучения AAP-2.H: Для выбора: a. Писать условные операторы. [Навык 2.B] b. Определять результат выполнения условных операторов. [Навык 4.B]

  • AAP-2.H.1 Условные операторы, или «операторы if», влияют на последовательное управление потоком, выполняя различные операторы в зависимости от значения булева выражения.

  • AAP-2.H.2 Справочный листок для экзамена содержит

    Текст:

    IF(condition) { <block of statements> }

    Блок:

    IF condition block of statements

в котором код в block of statements выполняется, если булево выражение condition возвращает true; никаких действий не предпринимается, если condition возвращает false.

  • AAP-2.H.3 Справочный листок для экзамена содержит

    Текст:

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

    Блок:

    IF condition first block of statements ELSE second block of statements

в котором код в first block of statements выполняется, если булево выражение condition возвращает true; в противном случае выполняется код в second block of statements.

Источник: Описание курса и экзамена College Board AP

Условная конструкция (выбор) выбирает, какой код выполнить. IF выполняет блок только тогда, когда его условие истинно; ELSE предоставляет альтернативу:

Выбор (Selection) выбирает между путями на основе условия
Выбор (Selection) выбирает между путями на основе условия
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

Вложенная условная конструкция помещает одну IF внутрь другой (или цепочку ELSE IF) для выбора среди более чем двух путей. Выполняется только первая совпадающая ветка:

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

Итерация
Программа

Ключевое понимание (AAP-2): Порядок следования и комбинация инструкций в программе определяют вычисленный результат. Программы используют конструкции итерации и выбора для представления повторений и принятия решений для обработки различных входных значений.

Цель обучения AAP-2.J: Описать алгоритм, использующий итерацию, без применения языка программирования. [Навык 2.A]

  • AAP-2.J.1 Итерация — это повторяющаяся часть алгоритма. Итерация повторяется заданное количество раз или до тех пор, пока не будет выполнено определенное условие.

Цель обучения AAP-2.K: Для итерации: a. Писать операторы итерации. [Навык 2.B] b. Определять результат или побочный эффект операторов итерации. [Навык 4.B]

  • AAP-2.K.1 Операторы итерации изменяют последовательное управление потоком, повторяя набор операторов ноль или более раз, пока не будет достигнуто условие завершения.

  • AAP-2.K.2 Справочный листок для экзамена содержит

    Текст:

    REPEAT n TIMES { <block of statements> }

    Блок:

    REPEAT n TIMES block of statements

в котором block of statements выполняется n раз.

  • AAP-2.K.3 Справочный листок для экзамена содержит

    Текст:

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

    Блок:

    REPEAT UNTIL condition block of statements

в котором код в block of statements повторяется до тех пор, пока булево выражение condition не вернет true.

  • AAP-2.K.4 В итерации REPEAT UNTIL(condition) возникает бесконечный цикл, когда условие завершения никогда не вернет true.
  • AAP-2.K.5 В итерации REPEAT UNTIL(condition), если условие изначально возвращает true, тело цикла не выполняется вовсе, поскольку проверка условия происходит перед началом цикла.

Источник: Описание курса и экзамена College Board AP

Итерация (цикл) повторяет инструкции. Псевдокод AP имеет две формы:

Цикл с предварительным условием (WHILE) проверяет условие перед телом, поэтому он может выполниться ноль раз
Цикл с предварительным условием (WHILE) проверяет условие перед телом, поэтому он может выполниться ноль раз
REPEAT 5 TIMES        // a fixed count
{
    DISPLAY("hi")
}

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

Цикл, который никогда не достигает своего условия остановки, является бесконечным циклом.

Исследовать

Трассировка цикла по одному проходу

Цикл повторяет блок, пока его счетчик проходит диапазон. Пройдитесь по шагам, чтобы следить за обновлением счетчика и накопленной суммы на каждом проходе.

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 Знание существующих алгоритмов может помочь в создании новых. К числу таких алгоритмов относятся:
    • определение максимального или минимального значения двух или более чисел
    • вычисление суммы или среднего значения двух или более чисел
    • определение, делится ли целое число на другое целое число нацело или нет
    • определение пути робота через лабиринт
  • AAP-2.M.3 Использование существующих правильных алгоритмов в качестве строительных блоков для создания нового алгоритма имеет преимущества, такие как сокращение времени разработки, уменьшение объема тестирования и упрощение выявления ошибок.

Источник: Описание курса и экзамена College Board AP

Исходный код на Python на экране — алгоритмы это точные, упорядоченные инструкции
Исходный код на Python на экране — алгоритмы это точные, упорядоченные инструкции

Алгоритм — это не то же самое, что и код. Помимо визуальных и текстовых языков программирования, алгоритм может быть представлен различными способами: с помощью естественного языка (обычных предложений), в виде диаграммы, такой как блок-схема, или с использованием псевдокода. Эти формы предназначены для людей — они позволяют проверить логику и согласовать её до выбора какого-либо конкретного языка, после чего один и тот же алгоритм можно записать на любом языке.

Когда вы пишете его на языке программирования, ясность и читаемость являются важными соображениями, а не просто украшением: осмысленные имена переменных, единообразное отступы и комментарии, объясняющие почему, а не что. Программу должны будут читать и изменять позже другие люди — часто это будете вы сами, а алгоритм, который никто не может понять, невозможно поддерживать или отлаживать.

Алгоритм — это конечная последовательность шагов, решающих задачу, состоящая из последовательности, выбора и итерации. Разные алгоритмы могут решать одну и ту же задачу, и вы должны уметь комбинировать и модифицировать существующие алгоритмы (например, подсчитать значения в списке, удовлетворяющие условию, или найти максимальное). Протрассируйте алгоритм вручную, чтобы убедиться, что он верен.

Блок-схема отображает алгоритм с использованием стандартных символов
Блок-схема отображает алгоритм с использованием стандартных символов
3.10

Списки
Программа

Ключевое понимание (AAP-2): Порядок следования и комбинация инструкций в программе определяют вычисленный результат. Программы используют конструкции итерации и выбора для представления повторений и принятия решений для обработки различных входных значений.

Цель обучения AAP-2.N: Для операций со списками: a. Писать выражения, использующие индексацию списков и процедуры работы со списками. [Навык 2.B] b. Вычислять значения выражений, использующих индексацию списков и процедуры работы со списками. [Навык 4.B]

  • AAP-2.N.1 Справочный листок экзамена предоставляет базовые операции со списками, включая:

    • доступ к элементу по индексу

      Текст:

      aList[i]

      Блок:

      aList i

      получает элемент из aList по индексу i. Первый элемент aList находится по индексу 1 и достигается с помощью записи aList[1].

    • присваивание переменной значения элемента списка

      Текст:

      x ← aList[i]

      Блок:

      x ← aList i

      присваивает значение aList[i] переменной x.

    • присваивание значения элементу списка

      Текст:

      aList[i] ← x

      Блок:

      aList i ← x

      присваивает значение x ⟨aList[i]⟩.

      Текст:

      aList[i] ← aList[j]

      Блок:

      aList i ← aList j

      присваивает значение aList[j] ⟨aList[i]⟩.

    • вставка элементов по заданному индексу

      Текст:

      INSERT(aList, i, value)

      Блок:

      INSERT aList, i, value

      сдвигает вправо все значения в aList с индексами, большими или равными i. Длина списка увеличивается на 1, а ⟨value⟩ помещается на индекс i в ⟨aList⟩.

    • добавление элементов в конец списка

      Текст:

      APPEND(aList, value)

      Блок:

      APPEND aList, value

      увеличивает длину ⟨aList⟩ на ⟨1⟩, а ⟨value⟩ помещается в конец ⟨aList⟩.

    • удаление элементов

      Текст:

      REMOVE(aList, i)

      Блок:

      REMOVE aList, i

      удаляет элемент с индексом ⟨i⟩ в ⟨aList⟩ и сдвигает влево все значения с индексами, большими чем ⟨i⟩. Длина ⟨aList⟩ уменьшается на ⟨1⟩.

    • определение длины списка

      Текст:

      LENGTH(aList)

      Блок:

      LENGTH aList

      вычисляется как количество элементов, присутствующих в ⟨aList⟩ на данный момент.

  • AAP-2.N.2 Процедуры работы со списками реализуются в соответствии с синтаксическими правилами языка программирования.

Цель обучения AAP-2.O: Для алгоритмов, включающих элементы списка: a. Писать операторы итерации для обхода списка. [Навык 2.B] b. Определять результат алгоритма, включающего обход списка. [Навык 4.B]

  • AAP-2.O.1 Обход списка может быть полным, когда доступны все элементы списка, или частичным, когда доступны только часть элементов.

    • Исключающее утверждение (EK AAP-2.O.1): Одновременный обход нескольких списков с использованием одного и того же индекса для обоих (параллельные обходы) выходит за рамки данной учебной программы и экзамена AP.

  • AAP-2.O.2 Операторы итерации могут использоваться для обхода списка.

  • AAP-2.O.3 Справочный листок экзамена предоставляет

    Текст:

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

    Блок:

    FOR EACH item IN aList block of statements

    Переменная ⟨item⟩ получает значение каждого элемента ⟨aList⟩ последовательно, по порядку, от первого до последнего. Код в ⟨block of statements⟩ выполняется один раз для каждой присвоенной переменной ⟨item⟩.

  • AAP-2.O.4 Знание существующих алгоритмов, использующих итерацию, может помочь в создании новых алгоритмов. Некоторые примеры существующих алгоритмов, часто используемых со списками, включают:

    • определение минимального или максимального значения в списке
    • вычисление суммы или среднего значения списка чисел

  • AAP-2.O.5 Алгоритмы линейного или последовательного поиска проверяют каждый элемент списка по порядку, пока не будет найдено желаемое значение или проверены все элементы списка.

Источник: Описание курса и экзамена 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

Обойдите список с помощью цикла для суммирования, подсчета, поиска или нахождения максимума:

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

    который используется для определения процедуры, принимающей ноль или более аргументов. Процедура содержит block of statements и возвращает значение expression. Оператор RETURN может出现在 в любом месте внутри процедуры и вызывает немедленный возврат из процедуры обратно в вызывающий оператор.

Источник: Описание курса и экзамена College Board AP

Вы определяете процедуру с именем, параметрами (входами) и телом, а также опционально 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/ нерешаемая проблема
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 (Application Program Interface) документирует, что делает каждая процедура, какие у нее параметры и какой результат — так что вы можете использовать ее, не видя исходного кода. Библиотеки экономят время и позволяют строить решения на основе уже существующей, протестированной работы.

Документация является частью библиотеки. Документация к API или библиотеке необходима для понимания предоставляемых ею возможностей и способов их использования — что ожидает каждая процедура в качестве параметров, что возвращает и что происходит на границах. Без нее вам пришлось бы читать исходный код, что противоречит цели абстракции; с ней вы можете правильно использовать процедуру, не зная, как она работает внутри.

Словарь Тренировать
English Русский
Interface/ˈɪntəfeɪs/ Интерфейс
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: Для симуляций: a. Объяснять, как компьютеры могут использоваться для моделирования реальных явлений или исходов. [Навык 1.A] 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 Задача принятия решений — это задача с ответом «да»/«нет» (например, существует ли путь от A до B?). Задача оптимизации — это задача, цель которой заключается в поиске «лучшего» решения среди многих (например, какой путь от A до B самый короткий?).
  • AAP-4.A.3 Эффективность — это оценка количества используемых алгоритмом вычислительных ресурсов. Эффективность обычно выражается как функция размера входа.
    • Исключение (EK AAP-4.A.3): Формальный анализ алгоритмов (Big-O) и формальное рассуждение с использованием математических формул выходят за рамки данной программы и экзамена AP.
  • AAP-4.A.4 Эффективность алгоритма определяется через формальное или математическое рассуждение.
  • AAP-4.A.5 Эффективность алгоритма может быть оценена неформально путем определения количества выполнений Statement или группы Statements.
  • 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 Неразрешимая задача — это задача, для которой невозможно построить алгоритм, всегда способный дать правильный ответ «да» или «нет».
    • Исключение (EK AAP-4.B.2): Определение того, является ли данная задача неразрешимой, выходит за рамки данной программы и экзамена AP.
  • AAP-4.B.3 Неразрешимая задача может иметь некоторые экземпляры, имеющие алгоритмическое решение, но не существует алгоритмического решения, способного решить все экземпляры задачи.

Источник: Описание курса и экзамена College Board AP

Некоторые задачи являются нерешаемыми: не существует алгоритма, который мог бы дать правильный ответ «да/нет» для каждого случая таких задач. Это фундаментальное ограничение вычислений — дело не в необходимости более быстрого компьютера, а в доказательстве невозможности существования такого алгоритма.

Навык для экзамена: уметь определять результат кодового фрагмента путём его трассировки, сравнивать эффективность двух алгоритмов (разумное vs неразумное время) и распознавать процедурную и структурную абстракцию в программе.

3.18

Советы для экзамена
  • Знать, что переменная — это именованный контейнер для значения, и отслеживать, как присваивание обновляет её шаг за шагом.
  • Внимательно прочитайте псевдокод AP — a <- expression выполняет присваивание, а списки на справочном листе экзамена имеют 1-индексацию.
  • Отличать переменную от списка (набора элементов, доступных по индексу) и корректно использовать операции со списками.
  • Вычислять выражения с правильным приоритетом операций и булевой логикой (AND, OR, NOT).
  • Выбирать понятные, осмысленные имена переменных — письменные задания оценивают читаемость кода.

Интерактивные уроки по этой теме

Пройдите его шаг за шагом с упражнениями мгновенной проверки.

Архив экзаменационных работ

Больше тем в AP Принципы информатики

Войти или создать аккаунт

IGCSE, A-Level & AP