Bachelor 2020/2021

Theoretical Foundations of Computer Science

Type: Compulsory course (HSE University and University of London Parallel Degree Programme in Management and Digital Innovation)

Area of studies: Business Informatics

Delivered by: Bachelor's Programme in Digital Product Management

Where: Graduate School of Business

When: 1 year, 1, 2 module

Mode of studies: offline

Instructors: Alexander A. Gorbunov

Language: English

ECTS credits: 5

Contact hours: 50

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

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 1
• Control work module 2
• Seminars activity
• Exam Test
  Examination format: The exam is taken written. The platform: The exam is taken on Ms Teams platform. Students are required to join a session 15 minutes before the beginning. The computers must meet the following technical requirements: https://docs.microsoft.com/ru-ru/microsoftteams/hardware-requirements-for-the-teams-app A student is supposed to follow the requirements below: Check your computer for compliance with technical requirements no later than 5 days before the exam; Sign in with your corporate account (@edu.hse.ru); Check your microphone, speakers or headphones, webcam, Internet connection (we recommend connecting your computer to the network with a cable, if possible); Prepare the necessary writing equipment, such as pens, pencils, pieces of paper, and others. Disable applications on the computer's task other than the MS Teams application or the browser that will be used to log in to the MS Teams platform. Students are not allowed to: Turn off the video camera; Use notes, textbooks, and other educational materials; Leave the place where the exam task is taken (go beyond the camera's viewing angle); Look away from your computer screen or desktop; Use smart gadgets (smartphone, tablet, etc.) Involve outsiders for help during the exam, talk to outsiders during the examination tasks; Read tasks out loud. Students are allowed to: Write on a piece of paper, use a pen for making notes and calculations; Turn on the microphone to answer the teacher’s questions; Ask a teacher for additional information related to understanding the exam task; Connection failures: A short-term communication failure during the exam is considered to be the loss of a student's network connection with the MS Teams platform for no longer than 1 minute. A long-term communication failure during the exam is considered to be the loss of a student's network connection with the MS Teams platform for longer than 1 minute. A student cannot continue to participate in the exam, if there is a long-term communication failure appeared. The retake procedure is similar to the exam procedure. In case of long-term communication failure in the MS Teams platform during the examination task, the student must notify the teacher, record the fact of loss of connection with the platform (screenshot, a response from the Internet provider). Then contact the manager of a program with an explanatory note about the incident to decide on retaking the exam.
• Attendance

Interim Assessment

• Interim assessment (2 module)
  0.1 * Attendance + 0.15 * Control work module 1 + 0.15 * Control work module 2 + 0.3 * Exam Test + 0.15 * Homework assignment + 0.15 * Seminars activity

Bibliography

Recommended Core Bibliography

• Sedgewick, R., & Wayne, K. (2017). Computer Science : An Interdisciplinary Approach. Boston: Addison-Wesley Professional. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1601647

Recommended Additional Bibliography

• M.N. Bhattacharjee. (2018). Computer Science: Few Newer Perspectives. [N.p.]: EBH Publishers [India]. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1934515