ENTRANCE EXAMINATION IN COMPUTER SCIENCE AND ICT

FOR APPLICANTS TO BACHELOR’S PROGRAMMES

Entrance test procedure

1. The entrance test is conducted in accordance with the current Rules for admission to the bachelor's and specialty programs and the MIPT entrance tests regulations.
2. The entrance examination in computer science and ICT has written and oral parts.
3. The entrance examination consists of two parts.
4. The written part includes tasks with a short answer and tasks with a detailed answer. The first part lasts 120 minutes.
5. The oral part of the entrance test includes:
   • discussion of solutions in the written part;
   • an interview on the examination paper ;
   • there can be additional tasks or questions.
6. The exam paper for the oral part contains 2 questions from different sections of the program. The oral part is conducted as an interview, without preparation time.
7. The oral part lasts up to 30 minutes.

 

Technical features of the remote exam

1. Practical part

During the practical part, remote monitoring will be carried out through the MIPT proctoring system located at: http://exams.mipt.ru.

An applicant must register in the proctoring system before the entrance exam and check the technical feasibility of connecting to the proctoring system. Failure to connect to the proctoring system is equivalent to failure to appear on the practical part.

2. Oral part

The oral part is conducted using the MIPT proctoring system (http://exams.mipt.ru) or one of the commonly used group communication tools (Hangouts, Google Meet, Zoom, etc.).

List of Topics

1. Introduction

1.1. Information and information processes. Data

Information as one of the main all-encompassing terms in modern science. Information transfer in various types of systems. The role of information and related processes in the world around us.

Data is information in a formalized form that is suitable for storage, transfer, and processing. Information processes are processes related to data storage, conversion, and transfer.

Data representation. Data for storage and processing in automated computer systems VS data intended for human perception: differences in representation.

Data structuring.

Systems. System components and their interaction. Character, sign, signal. Information interaction in the system. Open-loop and closed-loop control systems. Mathematical and computer modeling of control systems.

2. Mathematical foundations of computer science

2.1. Texts and encoding

Uniform and non-uniform codes. Prefix codes. Fano сondition. Reverse Fano condition. Decoding algorithms with prefix codes.

Examples of codes used for encoding texts: ASCII, UNICODE standard. Encoding Cyrillic and other national alphabets; code pages.

Data compression. Frequency of characters with non-uniform codes. Optimal Huffman encoding. Use of programs-archivers. The LZW algorithm.

Data transfer. Source, receiver, communication channel, signal, encoding and decoding device.

Bandwidth and noise immunity of the communication channel. Encoding of messages in modern data transferring media.

Distortion of information in communication channels. Codes with the ability to detect and fix errors.

Methods for protecting information transferred through communication channels. Cryptography (encryption algorithms). Steganography.

Basic school topics to revise:

Alphabet, text, length of text. The number of different texts of a given length in a given alphabet. Encoding characters in one alphabet using code words in another alphabet; code table, decoding.

2.2. Discretization

Measurements and discretization. Frequency and bit depth of measurements. The versatility of discrete representations of information.

Discrete representation of audio data. Multichannel recording. The size of the file obtained as a result of audio recording.

Discrete representation of graphical information. Color model. RGB and CMYK models. HSB and CMY models. Depth of coding.

Compression of data when storing graphic and audio information.

2.3. Numeral systems

Properties of positional notation: the number of digits, divisibility rule (whether a number is divisible by the base of the numeral system).

Algorithm for converting decimal notation to notation a positional system with a given base. Algorithms of number notation in a positional numeral system with a given base, algorithms of calculating a number according to a line containing this number in a positional numeral system with a given base.

Arithmetic operations in positional numeral systems.

Short and expanded form of writing mixed numbers in positional notation. Converting a mixed number to positional numeral system with a given base.
Representation of integers and real numbers in computer memory. Computer arithmetic.

Basic school topics to revise:

Positional numeral systems. Expansion of a number by degrees of the base of the numeral system. Binary notation.

Octal notation. Triads of the octal system. An algorithm for converting from binary to octal and back again.
Hexadecimal notation. Tetrads of the hexadecimal system. An algorithm for converting from binary to hexadecimal and back.

2.4. Concepts of combinatorics, set theory, and mathematical logic

Operations "implication" and "equality". Logic functions.
Rules of logic algebra. Equivalent transformations of logical expressions. Logical equations.
Building a logical expression with given truth table. Disjunctive normal form. Conjunctival normal form.

Logical elements of computers. Building schemas from basic logic elements. Trigger. Adder.
Discrete two-player games with complete information. Winning strategy.

Basic school topics to revise:

Calculation of the number of options: formulas for multiplying and adding the number of options. Logical operators. Logical operators NOT, AND, OR. Tables of truth of logical expressions of a set and operations with them. Euler-Venn diagrams.

2.5. Discrete objects

Directed and undirected graphs; cycle and acyclic graphs; starting vertice (source) and ending vertice (drain) in a directed acyclic graph; distance between vertices.

Algorithmic problems related to graph analysis (examples: the problem of constructing an optimal path between vertices of a directed acyclic graph; the problem of determining the number of different paths between vertices).

Trees. Subtrees; traversal of the tree in depth. Ordered trees (trees that have ordered edges that come out of a single node).

Use of trees in solving algorithmic problems (examples: analysis of recursive algorithms, analysis of arithmetic and logic expressions).

Using graphs, trees, and lists to describe objects and processes in the world around us.

Basic school topics to revise:

List. First element, last element, previous element, next element. Insert, delete, and replace an element.

Graph. Vertex, edge, path. Directed and undirected graphs. Length (weight) of the edge and path. The concept of a minimal path. The adjacency matrix of the graph (0/1 matrix) and the weight matrix (specifying edge lengths).

Tree. Root, leaf, vertex (node). Previous vertex, the next vertices. Subtrees. Tree height. Binary tree.

3. Algorithms and programming

3.1. Algorithms and data structures

The algorithms for studying a square equation with integer and real coefficients.

The algorithms for analyzing and converting number notations in the positional numeral system.

The algorithms associated with the divisibility of integers. Euclid's algorithm for finding the greatest common divisor of two natural numbers.

The algorithms for linear (single-pass) processing of a sequence of numbers without using additional memory that depends on the sequence length (calculating the maximum, sum, linear search, etc.). Processing of sequence elements that meet a certain condition (calculating the sum of such elements, their maximum, etc.).

Recursive algorithms. Notating them without using recursion. Сalculation of the elements of a recursive sequence. The construction and analysis of the tree of recursive calls.

Algorithms for processing arrays. Inserting and deleting elements in the array.

Sorting one-dimensional arrays. Quadratic sorting algorithms (example: bubble sorting). Merging two sorted arrays into a single array without using sorting. Recursive implementation of sorting by merging two sorted sub-arrays.

Calculating the value of a polynomial of a given degree at a given point (the values of the coefficients of the polynomial are set by an array).

Algorithms for analyzing strings.

Graphing a function defined by a formula, program, or table of values.

Algorithms for approximate solution of equations. Algorithms for approximate calculation of lengths and areas. Approximate calculation of the figure area using the Monte Carlo method. Building trajectories set by differential schemes. Tackling optimization problems. Algorithms for computational geometry. The probabilistic algorithms.

Saving and using intermediate results. Dynamic programming method.

Data structures: lists, dictionaries, trees, and queues. Hash tables.

3.2. Programming languages

Subroutines (procedures, functions). Parameters of subroutines. Recursive procedures and functions.

Logic variables. Character and string variables. String operations.

Two-dimensional arrays (matrices). Multidimensional arrays.

Tools for working with data in external memory. Files.

Detailed introduction to one of the universal procedural programming languages. Notation of algorithmic constructions and data structures in the selected programming language. Overview of procedural programming languages.

The concept of non-procedural programming languages and programming paradigms. Learning a second programming language.

Basic school topics to revise:

The main algorithmic constructions: "following" (sequential execution of commands)," branching" and "loop". Table values (arrays). One-dimensional arrays. Two-dimensional arrays.

Encoding of basic algorithmic structures in the selected programming language. Assignment operator. Constants and variables. Variable: name and value. Types of variables: integer and real ones.

3.3. Program design

Stages of solving problems on the computer.

Structural programming. Checking the loop condition before executing the loop body and after executing the loop body: the postcondition and precondition of the loop. The loop invariant.

Top-down and bottom-up program design. Development of programs that use subroutines.

Subroutine libraries and their use.

The concept of object-oriented programming. Objects and classes. Encapsulation, inheritance, polymorphism.

Fast software development environments. Graphical design of the user interface. Using modules (components) in programming.

Basic school topics to revise:

Checking the health of the program using trace tables.

3.4. Elements of the theory of algorithms

Formalization of the algorithm concept. The Turing machine is an example of an abstract universal computational model. The Church – Turing Thesis.

Other universal computing models (example: the Post machine). Universal algorithm. Computable and uncomputable functions. The stopping problem and its unsolvability.

Abstract universal generative models (example: grammars).

Calculation complexity: the number of operations performed, memory used, and their dependence on the size of the source data.

Complexity of the merge sorting algorithm (MergeSort).

Examples of algorithm analysis tasks: determining the input data for which the algorithm gives the specified result; finding the result of the algorithm without its full step-by-step execution.

The proof of the correctness of programs.

Basic school topics to revise:

Server. The need for a formal description of the server. Algorithm as a plan for managing the server(s).

3.5. Mathematical modeling

Practical work with a computer model on the selected topic. Conducting a computational experiment. Analysing reliability (plausibility) of experimental results.

Representation of modeling results in a form that is convenient for human perception. Graphical representation of data (diagrams, tables, graphs).

Building mathematical models for solving practical problems.

Simulation modeling. Modeling of queuing systems.

Discretization and numerical methods in mathematical modeling of continuous processes.

Use of simulation environments (virtual laboratories) for conducting computer experiments in education.

Use of educational computer-aided design systems.

Basic school topics to revise:

Concept of a mathematical model. Problems solved using mathematical (computer) modeling.
Modeling cycle: building a mathematical model, its software implementation, checking the model's compliance with the object or process of modeling using simple examples (testing), conducting a computer experiment, analyzing its results, refining the model

4. Information and computer technologies and their use in data analysis

4.1. Computers, hardware and software

Computer hardware. Personal computer.

Multiprocessor systems. Supercomputers. Distributed computing systems and big data processing. Mobile digital devices and their role in communications. Embedded computer. Microcontrollers. Automatic production.

Adequacy of the computer configuration to the tasks being solved. Trends in computer hardware development.

Software for computers and computer systems. Various types of software and their purpose: system software (operating systems, embedded software, programming systems), application software (word processors, browsers, etc.). software for mobile devices.

Installing and uninstalling software. System administration.

Computer viruses and malware. The use of antivirus tools.

Preventive maintenance of computer hardware and software.

Legal rules for using computer programs and working online. Legislation of the Russian Federation concerning software.

Precautions and rules for working on the computer. Hygiene, ergonomics, resource saving, technological requirements at a computer workplace. Designing an automated workplace in accordance with the purposes of its use.

4.2. Representing and analyzing data

Creating text documents. Inserting graphic objects and tables. Use of pre-made templates and making your own templates.

Search and replace tools. Spell and grammar checking. Pagination. Inserting footnotes and links, document structure mode, making a hypertext document. Bibliographic description of documents. Collective work with documents.

Tools for entering text. OCR. Speech recognition. Computer text layout. Desktop publishing capabilities.

Tools for creating and editing mathematical texts.

Technical means for entering graphic images. Cropping images. Color model. Image correction. Working with multi-layer images.

Working with vector graphic objects. Grouping and transforming objects.

Technologies for entering and processing audio and video information.

Image, audio, and video file formats.

Multimedia presentations. Making animation, animation adjustment.

Computer 3D modeling. Computer-aided design systems.

Processing technology for numerical information. Entering and editing data. Autocomplete. Cell formatting. Standard functions. Types of links in formulas. Solving computational problems from various areas.

Computer-based data representation and analysis. Data visualization.

Technology of carrying out a research project: setting a task, selecting research methods, drafting a project and work plan, preparing initial data, conducting research, making conclusions, making a report. Verification (verification of reliability and consistency) of initial data and validation (verification of validity) of research results.

Statistical data processing. Processing of the results of the experiment.

Data analysis using machine learning methods. Big data.

4.3. Databases

Concept and purpose of a database (DB). Types of database. Database management systems (DBMS). Tables. Record and field. Key field. Data type. Request. Types of query. Queries with parameters. Sorting. Filtration. Calculated field.

Shapes. Reports.

Multi-table databases. Links between tables. Normalization.

4.4. Networks

The Internet. Domain names system. Internet Services. WWW technology. Cloud services. Internet protocols. IP addresses and subnet masks.

Search engines in computer networks. Rules for making queries.

Personal information space of a user. Network community. Publication of materials on the Internet. Use of information systems on the Internet. Ecommerce.

Making web sites. HTML language, cascading style sheets (CSS). Dynamic HTML. Hosting websites.

4.5. Norms of working with ICT

Standards in Informatics and ICT. State electronic services and services. Mobile application. Open educational resources. Information culture.

Rules of behavior and information security online. Electronic digital signature. Netiquette.
Legal support of information security of the Russian Federation. Information security tools in computers, automated information systems, and computer networks.