Infopaket

Theory of programming

ОК.32

Обов’язкова дисципліна для ОП

First

2022/2023

5 Semester

4

PLO 1. Apply knowledge of the basic forms and laws of abstract thinking, the basics of the methodology of scientific knowledge, the forms and methods of extracting, analyzing, processing and synthesizing information in the subject area of ​​computer science. PLO 5. Design, develop and analyze algorithms for solving computational and logical problems, evaluate the efficiency and complexity of algorithms based on the application of formal models of algorithms and calculated functions.

1. Know: basic concepts, means and methods of programming, their application in computer science; to know programming languages ​​and 1st-order logic, their capabilities for describing subject areas. 2. To be able to: describe in formal languages ​​of the 1st order statements regarding certain subject areas and properties of programs; establish the truth of propositional formulas, formulas of the 1st order. 3. Possess elementary skills: programming in modern languages, testing programs, checking the feasibility of formulas.

Part 1. Basic concepts of programming theory and their formalization Topic 1. Introduction to the subject. Basic methodological principles of building formal program models. SIPL language. Independent work: Analysis of definitions of programming languages. Topic 2. Formalization of the SIPL language. Topic 3. Algebras of data and programs. Topic 4. Partial and complete correctness of programs. Topic 5. Subject areas and methods of their description. Development of basic concepts of programming. Topic 6. Clarification of basic concepts of programming. Topic 7. Software systems of different levels of abstraction. Specification and programming languages. Part 2. Syntax and semantics of programs. Recursive programs. Topic 8. The main methods of presenting the syntax of programming languages: BNF and their modifications. Formal languages ​​and grammars. Chomsky's hierarchy of grammars. Operations on languages. Automatic formalisms of language perception. Topic 9. Context-free grammars and languages ​​and their properties. Normal forms. Equations in algebras of formal languages. Topic 10. Solvable and unsolvable problems of the theory of formal languages. Topic 11. Functional semantics of programs, compositional semantics, denotational semantics, axiomatic semantics. Abstract data types. Topic 12. Recursion in programming languages. Complete ordered sets. Theorems about the smallest fixed point. Application of the theory of the smallest fixed point. Topic 13. Methods of semantic analysis of programs. Topic 14. Modern methods of program development and their formalization.

Basic 1. M.S. Nіkіtchenko. Teorіia programuvannia. Chastina 1. Navchal-nii posіbnik. – Nіzhin. Vidavnitstvo NDU іmenі M.V. Gogolia, 2010.– 119 s. Additional 1. Eric C.R. Hehner. a Practical Theory of Programming. - Springer-Verlag Publishers, New York, 2021. – 243 r. 2. M. Balaban. Principles of Programming Languages. - Ben-Gurion University of the Negev Faculty of Natural Science Department of Computer Science, 2017. – 418 r. 3. Semantics - Advances in Theories and Mathematical Models. - IN-TECH, 2012. – 284 r. 4. J. V. Tucker, K. Stephenson. Data, Syntax and Semantics: An Introduction to Modelling Programming Languages. - University of Wales Swansea, 2006. – 840 p. 5. I.A. Basarab, N.S.Nikitchenko, V.N. Red-ko. Kompozitsionnye bazy dannykh. - K., Libіd-, 1992.– 182 s. 6. Dzh. Khopkroft, R. Motvani, D. Ul-man. Vvedenie v teoriiu avtomatov, iazykov i vychislenii.– M.: Vil-iams, 2002.– 528 s.

Lectures, practical classes, consultations, independent work

- semester assessment: 1. Control work 1: RN 1.1, RN 1.2 — 10 points/6 points. 2. Control work 2: PH 1.1, PH 1.3 - 15 points/9 points. 3. Project task: RN 1.1, RN 1.2, RN 2.1, RN1.3, RN 3.1 - 10 points/6 points. 4. Homework: RN 1.1, RN 1.2, RN 2.1, RN1.3, RN 4.1 - 15 points/9 points 5. Current assessment: RN 2.1., RN 3.1, RN 4.1 – 10 points/6 points. - final evaluation (in the form of an exam): - the maximum number of points that can be obtained by a student: 40 points/ 24 points; - learning outcomes that will be evaluated: PH1.1, PH1.2, PH1.3, PH2.1, PH3.1, PH4.1; - form of implementation and types of tasks: written work. Types of tasks: 4 written questions. 1 question (theoretical): PH1.1, PH3.1, PH4.1; 2 questions (theoretical): PH1.2, PH3.1, PH4.1; 3 questions (practical): PH1.3, PH3.1, PH4.1; 4 questions (practical): PH2.1, PH3.1, PH4.1; A student can get from 1 to 10 points for a detailed answer to each task. ..

Ukrainian