Вычислительное мышление
International Baccalaureate · IB Diploma · Computer Science · HL Тема 5 3:31 Английское озвучивание · Английский + китайские субтитры (встроенные)
Главы
Транскрипт
An algorithm 算法 can work for one example and fail at a boundary.
一个算法可能在某个示例上运行正常，却在边界处失败。
Testing should be designed from the specification, not only the happy path.
测试设计应基于规范，而不仅仅是顺利路径。
An algorithm is a finite, unambiguous procedure for a task.
算法是解决任务的有限且无歧义的步骤。
A trace records state changes.
追踪记录状态变化。
A loop invariant describes a property preserved by each iteration and helps justify correctness.
循环不变量描述每次迭代中保持的性质，有助于证明正确性。
An algorithm is a finite procedure solving a stated task.
算法是解决特定任务的有限步骤。
A boundary test is a test at a limit of the allowed input range.
边界测试是在允许输入范围极限处的测试。
State input conditions and expected outputs.
陈述输入条件和预期输出。
Use boundary cases, empty collections where allowed, duplicates, and invalid values.
使用边界情况、允许时的空集合、重复项以及无效值。
Distinguish a wrong algorithm from a wrong implementation or an incomplete requirement.
区分错误的算法与错误的实现或不完备的需求。
In the lab: Trace a search over a small fictional sorted list.
在实验环节，对一个小型虚构的已排序列表进行搜索追踪。
State the indexing convention.
说明索引约定。
For binary search, update bounds so the remaining interval shrinks and reject unsorted input unless sorting is part of the task.
对于二分查找，更新边界使剩余区间缩小；除非排序属于任务内容，否则应拒绝未排序的输入。
Known: a linear search of an eight-item list can require eight comparisons when the sought item is last or absent.
已知：对一个包含八项的列表进行线性搜索，当目标项位于末尾或不存在时，可能需要八次比较。
Doubling the list length doubles the worst-case comparison count under this model.
在此模型下，将列表长度加倍会使最坏情况下的比较次数也加倍。
Binary search reduces the interval by roughly half each step, but requires a suitable ordered structure.
二分搜索每次将区间缩小约一半，但需要合适的有序结构。
Your turn: A linear search scans all 14 items without a match.
轮到你了。 线性搜索遍历全部 14 个项均未找到匹配。
How many item comparisons occur?
共发生多少次项比较？
A successful sample test does not prove correctness for all valid inputs.
成功的样本测试无法证明对所有有效输入均正确。
Do not import Cambridge-specific pseudocode syntax into an IB course without a course source.
若无课程来源，请勿将剑桥特定的伪代码语法引入IB课程。
Not true: One successful sample test proves an algorithm correct for every valid input.
这种说法不正确。 一次成功的样本测试并不能证明算法对所有有效输入都正确。
One passing test shows the algorithm works on that input only.
一次通过测试仅表明该算法在该特定输入上有效。
Correctness needs reasoning over all valid inputs or a proof - edge cases such as empty lists and boundary values are exactly where untested code fails.
正确性需要针对所有有效输入进行推理或给出证明。 边界情况，例如空列表和边界值，正是未经测试的代码容易出错的地方。
An algorithm is a finite, unambiguous procedure for a task.
算法是用于完成某项任务的有限且无歧义的步骤。
State input conditions and expected outputs.
明确输入条件和预期输出。
Watch for: A successful sample test does not prove correctness for all valid inputs.
注意：成功的样本测试并不能证明对所有有效输入都正确。
Evidence that an algorithm is correct follows this order: say which inputs are allowed, trace the steps, try the boundary inputs, and compare each result with the expected output.
证明算法正确的证据按这个顺序：说明允许的输入，追踪步骤，测试边界输入，再把每个结果与预期输出比较。
Trace first-match linear search on for 4 and 9.
对列表 执行首次匹配线性搜索，分别查找目标值 4 和 9。
Give results and comparison counts, including an empty-list boundary.
给出搜索结果与比较次数，并包含空列表边界情况。
For 4 return index 0 after one comparison; for 9 return −1 after three.
对于包含四个元素的列表，在一次比较后返回索引零。 对于包含九个元素的列表，在三次比较后返回负一。
Empty list returns −1 after zero.
空列表在零次比较后返回负一。
Use zero-based indices and stop at the first match.
使用从零开始的索引，并在首次匹配时停止。
The loop tests index 0 first, stops on a match, and returns −1 only after exhausting the list.
循环首先测试索引 0，在匹配时停止，仅在遍历完整个列表后才返回负 1。
Duplicates therefore return the first index.
因此，重复元素会返回第一个出现的索引。
An empty list executes no loop body.
空列表不执行任何循环体。
Retrieve the technical meanings, then vary one input in the original transfer and justify the model condition.
提取技术含义，然后在原始转换中改变一个输入，并论证模型条件。