Section outline
-
LK - senior lecturer Pokhodenko B.O. group: MП-10-25
PC - senior lecturer Pokhodenko B.O. group: MП-10-25
Classes are held remotely in the format of web conferences at the link:
On conference Zoomhttps://us05web.zoom.us/j/6801738431?pwd=IIia98NCgF82f5AbTfVJgKnYIjGEoN.1&omn=87202327627
Meeting ID: 680 173 8431
Access code: 5rfLRp
-
Lesson 1. Computer Architecture. Number Systems.
Objective: A deep dive into the fundamentals of how computer systems work, starting with an introduction to the architecture and principles laid down by John von Neumann, which are the foundation for most modern computing devices. Modern architectural solutions used in today's computers will also be considered. In addition, the lesson is devoted to familiarizing yourself with different number systems, which is critical for understanding how computers process and store data.
-
Lesson 2. Introduction to Algorithm Theory
Objective: involves the hierarchical mastery of skills, ranging from a basic understanding of terms to the ability to create formalized solutions. At the lowest level, Knowledge/Remembering, the student should be able to define the concepts of an algorithm and a program, list the properties of an algorithm (such as discreteness, definiteness, mass applicability, resultativity), and name historical examples of algorithms, such as Euclid's algorithm and al-Khwarizmi's algorithm. The next level, Understanding, requires the student to explain the necessity of a high degree of algorithm detail when executed by a computer, interpret the phrase "an algorithm is a technological instruction," and formulate the distinction between an algorithm (a general method) and a program (the recording of an algorithm in a computer language). The Application (Applying) level (3) assumes that the student will demonstrate the practical use of knowledge, particularly apply the principles of algorithm construction to analyze the problem statement and its subject area, and solve a problem by constructing a mathematical model (e.g., for estimating the area of an auditorium) based on input and intermediate data. The fourth level, Analysis (Analyzing), requires the student to compare Euclid's iterative algorithm with ancient Babylonian algorithms, differentiate between the stages of problem statement analysis and its formal solution, and analyze the impact of the absence of mathematical notation in the 9th century on the style of al-Khwarizmi's verbal prescription. At the fifth level, Evaluation (Evaluating), the student must justify the importance of the formal solution to a problem as a stage of algorithm construction, critique the effectiveness of the "Slavic peasant multiplication method" (based on doubling and adding) compared to modern numerical algorithms, and evaluate the importance of the concept of an "algorithm" as one of the fundamental concepts of modern informatics. At the highest level, Creation (Creating), the student must develop (plan) their own algorithm for solving a new mass-oriented problem (e.g., for the operation of IoT sensors) considering all necessary properties and characteristics, and design (create) a formal solution to the problem, including the mathematical model and the relationship between input and output data.
-
Lesson 3. Forms and Means of Algorithm Representation
Objective: involves a hierarchical acquisition of skills, ranging from simple recognition of notation forms to the ability to choose and justify the most effective way to represent an algorithm. At the lowest level, Knowledge/Remembering, the student must define the concept of algorithmization, list all known ways of representing algorithms (verbal, analytical, graphical, statement diagrams, pseudocode, decision tables, program notation), and name the main programming languages (e.g., C++, Python, Visual Basic) and their purpose. The next level, Understanding, requires the student to explain the essence of verbal and analytical descriptions of algorithms, interpret the dependence of the way an algorithm is written on its executor (human or computer), and formulate the difference between the structural diagram of an algorithm and the statement diagram. The Applying level (3) requires the student to demonstrate practical application of knowledge, including using a graphical method (block diagram) to represent an algorithm for solving a simple problem, using pseudocode to record the control logic of a simple mechanism (e.g., an IoT sensor), or converting a verbal description into program code (e.g., in Visual Basic for Applications). The fourth level, Analyzing, requires the student to compare the effectiveness of decision tables with a graphical method for representing an algorithm that has many conditional transitions, distinguish the degree of algorithm detail for a plant manager and a crew worker, and analyze the advantages of programming the algorithm over analytical form in terms of execution speed. At the fifth level, Evaluating, the student must justify the choice of a programmatic representation of an algorithm as the most effective means of representation for complex engineering systems, criticize the shortcomings of verbal descriptions of algorithms (such as ambiguity) for working with computer systems, and also assess the importance of universal languages, such as Visual Basic for Applications, for extending the functionality of software products. At the highest level, Creating, the student must develop (plan) a complex algorithm for controlling a process in a specific subject area (for example, controlling an ITS traffic light), using a combination of graphical methods and pseudocode, and design (create) a unified structured description of the algorithm that minimizes the effort and cost of its implementation.
-
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.
-
Lesson 5. Recursive Functions
Objective: involves a hierarchical acquisition of skills, from understanding basic operations to the ability to construct and analyze complex functions. At the lowest level, Knowing/Remembering, the student must define the concepts of a recursive function and a computable function, list the four basic operations used to construct primitive-recursive functions (substitution, superposition, primitive recursion, minimization operation), and name the mathematician who undermined the belief in the universality of algorithmic methods (Kurt Gödel). The next level, Understanding, requires the student to explain the essence of the operations of superposition and primitive recursion, interpret the implications of Gödel's theorems for algorithm theory, and formulate the distinction between primitive-recursive and general-recursive functions. The Applying level requires the student to demonstrate practical application of knowledge, including applying the primitive recursion operation to construct (e.g., a two-place) addition function f(x, y) = x+y based on basic functions, and solving a problem to determine the value of a function (e.g., f(x, 2)) through the sequential application of the operation h. The fourth level, Analyzing, requires the student to compare the hierarchy of computable functions, distinguish the primitive recursion operation from the minimization operation (which is used to construct general recursive functions), and analyze why not all computable functions are primitive-recursive. At the fifth level, Evaluating, the student must justify the importance of the minimization operation for expanding the class of computable functions, criticize the limitations of primitive-recursive functions in solving some classes of problems, and also evaluate the importance of the theory of recursive functions as one of the three main approaches to rigorous algorithm definition. At the highest level, Creating, the student must design (plan) his own composite recursive function, using the operations of superposition and primitive recursion, to model the computational process, and also design a formal description of the computable function that depends on an arbitrary number of arguments.
-
Lesson 6. Abstract Post Machine. Turing Machine. Markov's Normal Algorithms.
Objective: involves a hierarchical acquisition of skills, ranging from understanding the basics of abstract computational models to being able to compare their equivalence and assess their limitations. At the lowest level, Knowing/Remembering, the student must define the concept of an abstract machine (such as a Post machine and a Turing machine), list the main components that make up a Turing machine (tape, head, control device), and state the essence of the Post Thesis and the Turing Thesis. The next level, Understanding, requires the student to explain the need to create abstract computing machines to formalize the concept of an algorithm, interpret the consequences of the fact that there are problems for which an algorithm cannot be constructed at all, and formulate the difference between a Turing machine and Normal Markov algorithms (simplification of action vs. simplification of control logic). Level Applying (3) requires the student to demonstrate practical application of knowledge, including applying a command from the E. Post machine to perform a simple operation for processing markers on a tape, and solving a problem to determine a class of algorithmically intractable problems using abstract machines. Level Four, Analyzing, requires the student to compare the architectural approaches of the Post machine, the Turing machine, and normal Markov algorithms, distinguish the essence of a universal Turing machine (which imitates the work of any other machine) from a regular one, and analyze why the Turing machine and normal Markov algorithms are considered equivalent in computational power. At the fifth level, Evaluating, the student must justify the importance of the Church-Turing conjecture as fundamental to modern computer science, criticize the limitations of the Post machine compared to the Turing machine in solving complex problems, and evaluate the importance of the universal Turing machine for the development of the concept of programmable computers. At the highest level, Creating, the student must design a set of instructions or commands for an abstract Post machine to implement a specific algorithm, and design a formal description of a Normal Markov algorithm for transforming certain sequences of characters.
-
Lesson 7. Abstract Alphabet and Formal Grammars
Objective: involves a hierarchical acquisition of knowledge from a basic understanding of the structure of a language to the ability to construct formal grammars. At the lowest level, Knowing/Remembering, the student must define the concept of an abstract alphabet, list the main components of a formal grammar (the set of terminal symbols VT, the non-terminal symbols VN, the initial symbol S, and the set of inference rules P), and name the two main types of rules that govern a language: syntax and semantics. The next level, Understanding, requires the student to explain the difference between natural and formal languages (e.g., programming languages), interpret the concept of an alphabetic operator as a mapping that transforms one string of symbols into another, and formulate the difference between terminal and non-terminal symbols. The Applying level requires the student to demonstrate practical use of knowledge, in particular, to apply the inference rules of a simple generative grammar to generate several language chains (e.g., L(G) = {anbn | n > 0}), and to solve a problem of determining the class of a formal language (e.g., context-free) based on its inference rules. The fourth level, Analyzing, requires the student to compare the classification of formal grammars, distinguish between the concepts of syntax (rules for constructing sentences) and semantics (rules for giving meaning), and analyze the impact of recursion on the possibility of constructing an infinite set of words in a language. At the fifth level, Evaluating, the student must justify the importance of formal grammars for creating computer programming languages, criticize the shortcomings of natural languages (such as the presence of exceptions) for use in algorithmic systems, and also evaluate the importance of a computational system consisting of an abstract alphabet and a set of permissible operations for formalizing algorithmic processes. At the highest level, Creating, the student must develop (plan) his own formal grammar to describe the syntax of a new word class, and also design (create) a set of inference rules that allow generating a certain formal language.