• A
• A
• A
• АБB
• АБB
• АБB
• А
• А
• А
• А
• А
Обычная версия сайта
Бакалавриат 2019/2020

Теоретические основы информатики

Статус:
Направление: 38.03.05. Бизнес-информатика
Кто читает: Школа бизнес-информатики
Когда читается: 1-й курс, 3, 4 модуль
Формат изучения: без онлайн-курса
Язык: английский
Кредиты: 5

Course Syllabus

Abstract

Theoretical computer science the part of computer science concerned with fundamental mathematical questions about computers, programs, algorithms, data, and information processing systems in general. Computers and programs are inherently mathematical objects, and an understanding of their mathematical basis is essential to the appreciation of the foundations of computer science.The discipline covers the complete field of theoretical computer science, including mathematical foundations of computer science, formal methods of reasoning about programs and data, and formal semantics of programs and data, including formal semantics for natural language, pictures, and sound.

Learning Objectives

• Development of the theoretical foundations of computer science, necessary for the programme specialty, understanding and development of applied information technologies and systems.
• Formation of students' purposefulness, organization, diligence, responsibility, readiness for responsible and purposeful decision of tasks.

Expected Learning Outcomes

• to know the concept of information, basic properties and types (forms) of information
• To know methods of representation (coding) of information
• to know basic models of the processes of transmission; the basic principles of cryptographic protection of information
• to know basic models of the processes storage, retrieval
• To know basic models of information processing

Course Contents

• Information
The concept of information, its basic properties and features. Concept of communication and its forms, signs, alphabets, the concept of a formal language. The Hartley Formula. Information and data. Finite probability the source of the messages. The entropy of the source.
• Information representation
Encoding of source and text messages. Uniform and non-uniform coding. The tree code. Unambiguous decoding, prefix codes. Markov Method. Conditions for the existence of prefix code with given word lengths, Kraft’s theorem. Methods for constructing prefix codes. Shannon-Fano coding. The average length of the code words. The lower limit of the average length of the code word. Optimal encoding, properties of optimal codes construction of optimal code. Huffman coding method. Data compression.
• Information transfer
Information transfer. The main methods of message transmission (serial, parallel, synchronous and asynchronous). Transfer process model (binary symmetric channel.) The reliability of message transmission, ways to improve reliabilities. Principles for the use of codes detecting and correcting errors. Hamming distance. The relationship of the minimum distance of the code from it characteristics. Correcting capabilities of codes, boundaries, Hamming and Warshamov-Gilbert. The concept of linear group code. Building a linear group code for a given test matrix. Properties of the linear group code. Decoding using syndrome. 4 Protection of information during transmission, the main threats and methods of protection against them. Basics of digital steganography. Symmetrical, asymmetric and combined cryptosystems. Electronic digital signature and principles of its use. Digital certificates.
• Information storage and retrieval
The main types of search tasks. Description of queries and search objects. Models for information retrieval. Data storage structures and access methods. Relationship storage methods and search efficiency. Fundamentals of database technology. Models data, relational data model. Relational algebra. Requests in the form relational expressions. Equivalence, complexity, and query optimization. Basics writing queries in SQL language.
• Information processing
The concept of the algorithm and its properties. Formal methods of describing algorithms. Distributed information processing and problems of interaction of parallel processes. Methods of description and analysis of distributed processing. Petri nets. The main problems solved with the use of Petri nets (limitation, activity, reachability, coverability). The reachability tree and matrix method analysis of Petri nets. The language of Petri nets.

Assessment Elements

• Homework assignment
• Control work module 3
• Control work module 4
• Seminars activity
• Online - test

Interim Assessment

• Interim assessment (4 module)
0.15 * Control work module 3 + 0.15 * Control work module 4 + 0.2 * Homework assignment + 0.3 * Online - test + 0.2 * Seminars activity