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.
-
Lesson 8. Abstract Automata
Objective: involves hierarchical mastery of skills, starting from understanding the basics of the abstract automaton model and ending with the ability to construct and evaluate the equivalence of different types of automata. At the lowest level, Knowledge/Remembering, the student must define the concepts of an abstract automaton and a finite automaton, list the components that define a non-initial automaton (K, X, Y, ), and name the two main types of automata: recognizers and converters. The next level, Understanding, requires the student to explain the need for the emergence of automaton theory in connection with the creation of technical means of automatic control and computing systems, interpret the differences between Milley and Moore automata (where in Milley the output signal occurs simultaneously with the input signal, and in Moore - with a delay of 1 clock cycle), and formulate the concepts of deterministic and non-deterministic automata. The Applying level assumes that the student will demonstrate the practical use of knowledge, in particular, will apply the transition function delta and the output function gamma to calculate the next state and output symbol of the automaton, use a tabular or graphical method to specify the finite automaton, and also solve the problem of determining the language recognized by the finite automaton. The fourth level, Analyzing, requires the student to compare the structure and operation of Mealy and Moore automata, distinguish the computational capabilities of different types of automata according to the complexity of the work stream (e.g., MT, LOA, MP automaton, CA), and analyze the conditions under which two finite automata are considered equivalent. At the fifth level, Evaluating, the student must justify the importance of the theorem on the closed set of regular languages with respect to operations (iteration, product, union), criticize the limitations of the finite automaton (FA) compared to the Turing machine (TM) due to the lack of a work stream, and evaluate the equivalence of Mealy and Moore automata. At the highest level, Creating, the student must design an algorithm to minimize a finite state machine 15, as well as design a finite state machine graph that recognizes a given regular language.
-
Lesson 9. Introduction to the Basics of Programming
Objective: involves hierarchical learning of knowledge from basic terminology and software classification to the ability to analyze the evolution of programming paradigms and languages.
At the lowest level, Knowing/Remembering, the student must define the concept of software (software) and programming languages, list the three main classes of software (system, application, software development tools), and name the three types of control structures used in structured programming (sequential execution, branching, looping). The next level, Understanding, requires the student to explain the differences between declarative (what?) and imperative (how?) programming, interpret Wirt's formula "algorithms + data structures = programs", and formulate the essence of the principle of program modularity. The Applying level (3) requires the student to demonstrate practical application of knowledge, including applying the principles of structured programming to explain (analyze) how to avoid "BS programs" (bowl of spaghetti), using the concept of bytecode and the JVM to explain the mechanism of cross-platform portability of the Java language, and providing examples of programming languages for each of the three main imperative paradigms (procedural, object, object-oriented). The fourth level, Analyzing, requires the student to compare the approaches of Pascal (standardization of the virtual machine) and C (flexibility of hardware use) to the computing environment, distinguish between procedural and object-oriented programming (OOP) as technologies (algorithmic component versus structured data organization), and analyze the relationship of C# to C, C++, and Java, and its role in solving the problem of interlanguage interoperability. At the fifth level, Evaluating, the student must justify the importance of a high degree of module independence to reduce the "ripple effect" and increase program reliability, criticize the concept of Fortran for the lack of conditional loops, which hindered support for structured programming, and evaluate the role of Anders Heijlsberg in creating C# based on existing "fundamental" languages. At the highest level, Creating, the student must design an architectural solution that combines multi-paradigmism to solve a complex problem (for example, a combination of functional and object-oriented approaches, as supported by Python), and design a set of properties for a new software module that maximizes its independence.
-
Lesson 10. Object-Oriented Programming.
Objective: involves systematic mastery of concepts from a basic understanding of the object paradigm to the ability to design complex class hierarchies. At the Knowing/Remembering level, the student must name and define the four main features of object-oriented programming (encapsulation, polymorphism, inheritance, and abstraction), as well as list the composition of project files, such as source, header, and object code. At the Understanding level, the student is expected to explain Björn Stroustrup's metaphor for OOP as "a highly intellectual synonym for good programming" and formulate the essence of the data hiding mechanism through encapsulation to protect the integrity of objects. The Applying level requires the student to demonstrate the use of inheritance to create new classes based on existing ones, to apply the property of polymorphism to provide code flexibility through the same interface for different data types, and to use a debugger to monitor the values of variables during program execution. At the Analyzing level, the student must compare procedural programming with object-oriented programming, distinguish the roles of the compiler and linker in the process of creating an executable file, and analyze how the class hierarchy facilitates code reuse. At the Evaluating level, it is necessary to justify the viability of the object-oriented paradigm as a "long-liver" in the software industry, criticize the excessive specificity of procedural algorithms compared to object models, and evaluate the effectiveness of using abstraction to highlight only the significant characteristics of an object in the context of the problem being solved. At the highest level of Creating, the student must develop (plan) the architecture of a software project in the form of a hierarchy of classes that minimizes dependencies between components, and design (create) an object model of a real system, integrating encapsulation and polymorphism mechanisms to ensure the scalability of the solution.
-
Lesson 11. Software Development Process
Objective: Provides a systematic learning experience from understanding the software product life cycle to the ability to manage development methodologies. At the lowest level, Knowing/Remembering, the student must identify the four key components of a software development system according to the USDP unified process (people, process, project, product), list the seven standard steps of software development (from understanding the nature of the software to maintenance), and name the main roles (Product Owner, Scrum Master, Team) and events (Sprint, Standup, Review, Retrospective) in the Scrum methodology. The next level, Understanding, requires the student to explain the essence of the waterfall model as a sequential execution of the analysis, design, coding, and testing phases, interpret the difference between static, semi-static, and dynamic data structures, and formulate the core values of agile development, such as the priority of a working product over exhaustive documentation. Level Applying (3) requires the student to demonstrate the ability to use the Watts-Humphrey Capability Maturity Model (CMM) to classify an organization's maturity at one of five levels (from initial to optimized), apply Scrum principles to organize the team's work during a sprint, and determine the type of data structure required to effectively solve a specific algorithmic problem. Level Four, Analyzing, requires the student to compare traditional (heavyweight) methodologies with agile (Agile), highlighting their advantages and disadvantages depending on the stability of requirements, delimiting the stages of the software life cycle, identifying potential risks in the transition from design to implementation, and analyzing the impact of the human factor ("Personnel") on the success of an IT project. At the fifth level, Evaluating, the student must justify the appropriateness of choosing a specific development model (for example, V-model or spiral) for critical systems, criticize the chaotic nature of processes at the "Starting" maturity level of the CMM, and also evaluate the effectiveness of conducting daily stand-ups to monitor project progress. At the highest level, Creating, the student must develop (plan) an adapted development process for a startup, combining elements of Scrum and extreme programming, and design a plan for the organization's transition to a higher level of process maturity, implementing the necessary standards and quality control tools.
-
Lesson 12. Basic Concepts of .NET
Objective: Provides a systematic understanding of the fundamental principles of building modern software platforms and the features of data management in the runtime environment. At the lowest level of Knowledge/Remembering, the student must identify key historical stages in the development of programming languages, such as the emergence of the C language in 1972 and the .NET platform in 2002, as well as name the two main types of types in the CTS system - value types and reference types. The Understanding level requires the student to explain the prerequisites for the emergence of object-oriented programming due to the limitations of the C language in working with large projects and to formulate the fundamental difference in the behavior of data when copying: creating a duplicate value for value types versus creating an additional reference to the same object in memory for reference types. At the Applying level, the student must demonstrate an understanding of memory mechanisms by applying object rules to predict changes in the program, for example, realizing that changing a property through one reference variable will affect all other references to the same object. The fourth level, Analyzing, requires the student to analyze the impact of the advent of the Internet on the transformation of programming languages into tools for creating distributed Internet applications and to distinguish the logical structure of data types (numbers, characters, boolean types) and their physical organization in the CTS system. At the Evaluating level, it is necessary to justify the advantages of using a unified type system (CTS) to ensure interoperability between different programming languages within the same platform and to criticize the disadvantages of manual memory management and pointers inherent in the C language compared to the safety of managed code in .NET. At the highest level of Creating, the student must develop (plan) the optimal data structure for a specific application, rationally combining value types for simple calculations and reference types for complex objects, as well as design a conceptual diagram of a portable software module that takes advantage of the .NET architecture to work in different operating environments.
-
Lesson 13. Fundamentals of the C# Language (1)
Objective: This involves a gradual mastery of the fundamental elements of syntax from basic definitions to the ability to construct complex expressions. At the lowest level of Knowing/Remembering, the student should define the concept of strong typing, list the basic built-in data types (such as int, bool, double, decimal), and state the size in bits and range of values for signed and unsigned integer types. The Understanding level requires the student to explain the concept of variable scope and its accessibility within a code block, interpret the difference between implicit and explicit type casting, and state the difference between prefix and postfix forms of increment and decrement. At the Applying level, the student must demonstrate the ability to use literals with appropriate suffixes (e.g., U, L, F, M) to explicitly specify the type of a constant, apply arithmetic and logical operations to calculate values, and solve the problem of initializing variables of different categories (value types and reference types). The fourth level of Analyzing requires the student to analyze the precedence of operations in complex expressions (e.g., z = x++ + y), distinguish cases when data loss is inevitable during type casting, and compare system type names (e.g., Int32) with their aliases in the C# language. At the Evaluating level, it is necessary to justify the choice of a particular data type (e.g., decimal instead of double) depending on the requirements for calculation accuracy, criticize the use of implicit casting in potentially dangerous areas of the code, and evaluate the impact of the correct use of parentheses on the readability and logic of program code execution. At the highest level of Creating, the student must develop (plan) a code structure with optimal use of scopes to prevent name conflicts, as well as design (create) a sequence of operations using different data types and transformations to implement a given mathematical algorithm.
-
Lesson 14. Fundamentals of the C# Language (2)
Objective: Provides comprehensive mastery of program flow control tools from understanding branching syntax to the ability to design complex loop structures. At the lowest level of Knowledge/Remembering, the student must determine the purpose of the if, switch, while, do-while, for, and foreach statements, as well as list the keywords for controlling loop exit, such as break, continue, and goto. The next level of Understanding requires the student to explain the logic of execution of the full and abbreviated forms of the if construct, interpret the difference between loops with preconditions and postconditions, and formulate the features of the foreach loop when iterating over collections. The Applying level requires the student to demonstrate the use of the switch operator for multivariate selection, apply the break and continue statements to change the standard loop execution logic, and solve a problem of finding the maximum of two numbers using branching. At the Analyzing level, the student must compare the effectiveness of using different types of loops to solve a specific problem, distinguish cases where labels and the goto operator are appropriate from situations where this worsens the code structure, and also analyze the impact of logical conditions on the number of iterations in a loop. At the Evaluating level, the student must justify the choice of the switch construct instead of multiple if-else to improve code readability, criticize the use of infinite loops without proper exit conditions, and assess the importance of structured programming to prevent the creation of confusing code. At the highest level, Creating, the student must develop (plan) an algorithm with nested loops and branches to process complex data structures, and design (create) a coherent program control logic that ensures the correct processing of all possible input states.
-
Lesson 15. Fundamentals of the C# Language (3)
Objective: Provides a comprehensive understanding of the principles of working with arrays as object data structures that integrate the methods of the .NET platform base classes for efficient information processing. At the lowest level of Knowledge/Remembering, the student must define the concept of an array as a reference-type data type, name the base class System.Array from which arrays inherit their properties, and list the main ways to initialize one-dimensional and multidimensional arrays. The Understanding level requires the student to explain the logic of memory allocation for arrays in the Heap area using the new operator, interpret the features of accessing elements by index, starting from zero, and formulate the difference between rectangular and jagged multidimensional arrays. At the Applying level, the student must demonstrate the ability to use the foreach loop to iterate through array elements, use the Length property to control array boundaries, and solve a practical problem of copying an array using the Clone() method. The fourth level, Analyzing, requires the student to analyze the advantages and limitations of using the Array.Sort(), Array.Reverse(), and Array.Clear() methods when manipulating data, distinguish the behavior of an address variable and the array object itself in memory, and compare different types of multidimensional arrays in terms of their ease of use. At the Evaluating level, it is necessary to justify the choice of a specific method of the System.Array class to optimize sorting or data clearing algorithms, criticize attempts to access array elements outside its boundaries, and evaluate the role of the object-oriented implementation of arrays in C# to ensure security and development flexibility. At the highest level of Creating, the student must develop (plan) an architecture for processing large data sets using multidimensional structures, and design (create) a software module that integrates several standard methods of the Array class to implement a holistic array transformation algorithm.