알고리즘, 추적 및 정합성 증거
도입됨| English | 의미 |
|---|---|
| algorithm/ˈælɡərɪθəm/ | 알고리즘 |
| boundary test/ˈbaʊndəri test/ | 경계 테스트 |
이 현상을 설명할 수 있는 이유는 무엇인가?
- 알고리즘은 한 예제에서는 작동하지만 경계에서 실패할 수 있습니다. 테스트는 happy path뿐만 아니라 사양(specification)에 기반하여 설계되어야 합니다.
- 예측을 먼저 제시하십시오. 비교하고자 하는 양이나 특성을 명시한 뒤, 두 설명을 구별할 수 있는 증거가 무엇인지 결정하십시오.
모델 만들기
- 알고리즘은 작업에 대한 유한하고 모호하지 않은 절차입니다. 트race는 상태 변경을 기록합니다. 루프 불변식(loop invariant)은 각 반복에서 유지되는 성질을 기술하며 correctness를 정당화하는 데 도움이 됩니다.
- 알고리즘(algorithm): 명시된 과제를 해결하는 유한한 절차; 경계 테스트(boundary test): 허용된 입력 범위의 한계에서 수행되는 테스트.
일반 이진 탐색(binary search)을 목록에 적용하기 전에 어떤 조건이 만족되어야 합니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
이진 탐색은 비교 규칙에 따라 정렬된 목록에서만 중간 요소와 비교하여 반을 제거합니다. 중복 값은 허용되며, 목록 길이는 무관합니다.
각 전문 용어에 대한 정확한 의미를 매칭하시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
정의를 사용하여 유사한 양과 과정을 구분하시오.
검증 가능한 증거 선택하기
- 입력 조건과 예상 출력을 명시하십시오. 경계 사례, 허용되는 경우의 빈 집합, 중복 및 유효하지 않은 값을 사용하십시오. 잘못된 알고리즘을 잘못된 구현 또는 불완전한 요구 사항과 구분하십시오.
- 작은 가상의 정렬된 목록에 대한 탐색을 추적하십시오. 인덱싱 관례를 명시하십시오. 이진 탐색의 경우 남은 구간이 줄어도록 범위를 업데이트하고, 정렬이 과제의 일부가 아닌 한 정렬되지 않은 입력은 거부하십시오.
이 경우 조사 또는 모델이 더 타당하게 만들 수 있는 두 가지 습관은 무엇인가?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
조건과 가정을 명시하면 다른 사람이 정확히 작업을 재현할 수 있으며, 근거 증거를 기록하면 결론을 검증할 수 있습니다. 반대되는 결과를 숨기는 것은 잘못된 결론을 반박할 수 있는 증거를 제거하는 것이며, 한 번의 측정으로는 더 넓은 주장을 입증할 수 없습니다.
알려진 값으로부터 시작하기
- 알려진 값과 그 단위를 명시하십시오. 이 사례에 가정이 부합하는 식을 선택한 후 대입하기前面으로 변형하십시오.
- 알려진 사실: 8개 항목의 목록에 대한 일차 탐색은 찾는 항목이 마지막이거나 존재하지 않을 때 8번의 비교가 필요할 수 있습니다. 이 모델에서 목록 길이를 두 배로 늘리면最差情况의 비교 횟수도 두 배가 됩니다. 이진 탐색은 각 단계마다 구간을 약 절반으로 줄이지만 적절한 순서 구조가 필요합니다.
일차 탐색은 일치하는 14 항목 없이 모든 항목을 스캔합니다. 몇 번의 항목 비교가 발생합니까? 동일한 순서를 사용하십시오: 알려진 양 → 모델 → 관계 → 대입 → 단위 및 해석.
일차 탐색(linear search)가 일치하지 않는 14 개 항목을 모두 스캔했을 때, 총 몇 개의 항목 비교가 이루어지는가?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
결과값은 14 번의 비교입니다.已知: ⟨⟩14개 항목에 대한 선형 탐색으로 일치하는 요소가 없음. 부재가 확실해지기 전까지 모든 항목을 비교해야 하므로 비교 횟수 = 14. 실패한 탐색은 항상 전체 길이에 해당하는 비용을 요구합니다.
결론及其 한계 확인하기
- 성공적인 샘플 테스트는 모든 유효한 입력에 대해 정확성을 증명하지 않습니다. 교재 소스가 없는 한 Cambridge 특유의 가상어법 구문을 IB 과정에 도입하지 마십시오.
- 원래 관찰로 돌아가십시오. 결과가 어떤 것을 지지하며, 어떤 조건을 전제로 하며, 경쟁 설명을 검증하는 방법 하나를 제시하십시오.
한 번의 성공적인 샘플 테스트는 알고리즘이 모든 유효 입력에 대해 옳음을 증명한다. 이 주장은 틀렸다: 한 번의 통과 테스트는 해당 입력에서만 작동함을 보여줄 뿐이다. correctness는 모든 유효 입력에 대한 추론이나 증명이 필요하며, 빈 리스트나 경계 값과 같은 가장자리ケース(Edge Cases)는 테스트되지 않은 코드가 실패하는 곳이다.
알고리즘, 추적 및 정확성 증거: 입력 조건과 예상 출력을 명시하십시오. 경계 사례, 허용되는 경우의 빈 집합, 중복 및 유효하지 않은 값을 사용하십시오. 잘못된 알고리즘을 잘못된 구현 또는 불완전한 요구 사항과 구분하십시오.
하나의 성공적인 샘플 테스트는 모든 유효한 입력에 대해 알고리즘이 올바르다는 것을 증명할 수 없습니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
하나의 통과 테스트는 해당 입력에서만 알고리즘이 작동함을 보여줄 뿐입니다. correctness(올바름성)는 모든 유효 입력에 대한 논리적 검증이나 증명으로 확인되어야 하며, 빈 목록이나 경계값 같은 예외 사례에서 테스트되지 않은 코드가 오류를 발생시킵니다.
지정된 문제를 해결하는 유한한 절차: 기술 용어를 쓰십시오.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
알고리즘(algorithm)은 명시된 과제를 해결하는 유한한 절차를 의미합니다.