الصفوف 9–12Computationمُخطَّط له
Algorithms, correctness and efficiency
Searching and sorting, proving algorithms correct with loop invariants, counting steps, and comparing growth rates such as logarithmic, linear and quadratic time.
math.comp.algorithms-and-efficiency
لم يُكتب درس هذا الموضوع بعد. المخطط أدناه جزء من خريطة المنهج ولم تجرِ مراجعته.
يعتمد على
عدد المتطلبات السابقة الإلزامية (حتى الأساس): 15
ستتعلّم
- Implement linear search, binary search and a simple sort, and trace them on examples.
- Prove an algorithm correct using a loop invariant, for example binary search or Euclid's algorithm.
- Count the steps of simple algorithms and compare growth rates n, n log n and n².
تعريف
- A loop invariant is a statement that holds before the first iteration of a loop and is preserved by every iteration.
- The running time of an algorithm is the number of basic steps it takes, as a function of the size of its input.
مبرهنة
- Binary search on a sorted list of n items uses at most ⌊log₂ n⌋ + 1 comparisons.
- Every comparison-based sorting algorithm needs at least log₂(n!) comparisons in the worst case, which grows like n log n.
- An algorithm is correct if, for every valid input, it terminates and produces the specified output.
مفاهيم خاطئة شائعة
- Thinking that testing on a few inputs proves an algorithm correct.
- Believing faster computers make algorithmic efficiency irrelevant.
يقود إلى
اكتشافات اختيارية
- Computational complexity Some problems seem to require far more time than others; whether P equals NP is a famous open problem.
- ← Divisibility, Euclid's algorithm and unique factorisation
- ← Recurrences and generating functions
مسارات التعلّم
قراءات إضافية
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms