Topic 4

Lesson 4. Types of Algorithmic Processes. Algorithmic Systems.

Objective: involves the hierarchical acquisition of knowledge and skills from the basic classification of algorithms to the ability to analyze their complexity and equivalence. At the lowest level, Knowing/Remembering, the student must define the concepts of an algorithmic system and a computable function, list all the main types of algorithmic processes, such as linear, branched, cyclic, mechanical, and heuristic, and name the three basic control structural fragments: composition, alternative, and iteration.3 The next level, Understanding, requires the student to explain the difference between polynomial and exponential algorithms, interpret the essence of NP-hard problems using the example of the traveling salesman problem, and formulate the main requirements that are imposed on algorithms (e.g., determinism, efficiency, memory requirements). The Applying level requires the student to demonstrate practical application of knowledge, including applying the formula T=k * t to calculate the time complexity of an algorithm, using the structural algorithmization method to represent a simple branched or cyclic algorithm, and giving an example of a solvable set. The fourth level, Analyzing, requires the student to compare the three main approaches to constructing a strict definition of algorithms (recursive functions, Turing machines, normal Markov algorithms), distinguish between the guessing and checking stages in a nondeterministic algorithm, and analyze why Turing machines and normal Markov algorithms are considered equivalent. At the fifth level, Evaluating, the student must justify why polynomial algorithms are considered "well-solvable", criticize the shortcomings of using infinite algorithms (such as calculating weather forecasts) in practical activities, and also evaluate the importance of the theorem on the possibility of reducing one algorithmic model to another. At the highest level, Creating, the student must develop (plan) an approximate or heuristic algorithm for solving an NP-hard problem, as well as design an algorithmic system, including an abstract alphabet and a finite set of permissible operations, to solve a specific class of problems.