Theoretical Foundations of Computer Science

2019/2020

Учебный год

ENG

Обучение ведется на английском языке

5

Кредиты

Кто читает:

Школа бизнес-информатики

Статус:

Курс обязательный

Когда читается:

1-й курс, 3, 4 модуль

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
  The instructions for students in the LMS. Midterm exams with asynchronous proctoring. Examination format: The exam is taken written (multiple choice questions) with asynchronous proctoring. Asynchronous proctoring means that all the student's actions during the exam will be “watched” by the computer. The exam process is recorded and analyzed by artificial intelligence and a human (proctor). Please be careful and follow the instructions clearly! The platform: The exam is conducted on the StartExam platform. StartExam is an online platform for conducting test tasks of various levels of complexity. The link to pass the exam task will be available to the student in the RUZ. Students are required to join a session 15 minutes before the beginning. The computers must meet the following technical requirements: https://eduhseru-my.sharepoint.com/:b:/g/personal/vsukhomlinov_hse_ru/EUhZkYaRxQRLh9bSkXKptkUBjy7gGBj39W_pwqgqqNo_aA?e=fn0t9N A student is supposed to follow the requirements below: Prepare identification documents (а passport on a page with name and photo) for identification before the beginning of the examination task; 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 browser that will be used to log in to the StartExam program. If one of the necessary requirements for participation in the exam cannot be met, a student is obliged to inform a professor and a manager of a program 2 weeks before the exam date to decide on the student's participation in the exams. 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; Use a calculator; Connection failures: A short-term communication failure during the exam is considered to be the loss of a student's network connection with the StartExam 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 StartExam platform for longer than 1 minute. A long-term communication failure during the exam is the basis for the decision to terminate the exam and the rating “unsatisfactory” (0 on a ten-point scale). In case of long-term communication failure in the StartExam 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.

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

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