Modern trends in discrete mathematics and computer science — различия между версиями
(→Lectures 3,4. Constraint satisfaction problem: an algebraic approach.) |
(→Lectures 3,4. Constraint satisfaction problem: an algebraic approach.) |
||
| Строка 31: | Строка 31: | ||
== Lectures 3,4. '''Constraint satisfaction problem: an algebraic approach.''' == | == Lectures 3,4. '''Constraint satisfaction problem: an algebraic approach.''' == | ||
| − | The topic of the lecture is the constraint satisfaction problem (CSP). CSP is a universal formalization for a wide variety of problems in Discrete Mathematics and Computer Science. Recently, a characterization of the CSP complexity has been obtained by an algebraic approach. The aim of the lecture is describing the algebraic approach to CSP and the results established by its applying. | + | The topic of the lecture is the constraint satisfaction problem (CSP). CSP is a universal formalization for a wide variety of problems in Discrete Mathematics and Computer Science. Recently, a characterization of the CSP complexity has been obtained by an algebraic approach. The aim of the lecture is describing the algebraic approach to CSP and discussing the results established by its applying. |
Lecturer [[Селезнева Светлана Николаевна | Svetlana N. Selezneva]] | Lecturer [[Селезнева Светлана Николаевна | Svetlana N. Selezneva]] | ||
Версия 19:09, 13 февраля 2018
Compulsory course for master students, 2-nd year, groups 618/1 and 618/2.
Lectures — 16 h.
Responsible lecturer Vladimir Zakharov.
This course is intended to introduce the audience to some topics in discrete mathematics and its applications in software engineering, VLSI designing and biochemistry which are in line with the modern development of computer science and applied mathematics.
Содержание
- 1 Preliminary program and materials
- 1.1 Lecture 1. Theory and practice of software obfuscation.
- 1.2 Lecture 2. Formal correctness proofs for sequential programs.
- 1.3 Lectures 3,4. Constraint satisfaction problem: an algebraic approach.
- 1.4 Lecture 5. Closed classes in k-valued and partial k-valued logics.
- 1.5 Lecture 6. Read-once functions.
- 1.6 Lecture 7. Some new bounds of Shannon functions for cardinality of test sets for logical circuits.
- 1.7 Lecture 8. 13С metabolic flux analysis.
- 2 Literature
Preliminary program and materials
Lecture 1. Theory and practice of software obfuscation.
This lecture is devoted to the software obfuscation problem, its applications in software protection, information hiding and cryptography, to the practical techniques of program obfuscation with the help of structures and techniques from discrete mathematics, automata theory, coding theory. Much attention is payed to formal definitions of obfuscation security. It wil be shown that a secure obfuscation of some programs is impossible in the framework of a "black box" model, but , nevertheless, certain classes of simple programs admit secure obfuscation.
Lecturer: Vladimir Zakharov.
Lecture 2. Formal correctness proofs for sequential programs.
This lecture is devoted to formal verification of sequential imperative programs. The main topic of the lecture is the notion of formal system (logical calculus) applied to correctness proof for imperative programs. Several valuable properties of such formal systems and proofs for simple-but-useful programs are to be discussed.
Lecturer: Vladislav Podymov.
Lectures 3,4. Constraint satisfaction problem: an algebraic approach.
The topic of the lecture is the constraint satisfaction problem (CSP). CSP is a universal formalization for a wide variety of problems in Discrete Mathematics and Computer Science. Recently, a characterization of the CSP complexity has been obtained by an algebraic approach. The aim of the lecture is describing the algebraic approach to CSP and discussing the results established by its applying.
Lecturer Svetlana N. Selezneva
Lecture 5. Closed classes in k-valued and partial k-valued logics.
Lecture 6. Read-once functions.
Lecture 7. Some new bounds of Shannon functions for cardinality of test sets for logical circuits.
Lecture 8. 13С metabolic flux analysis.
Literature
- Варновский Н.П., Захаров В.А., Кузюрин Н.П., Шокуров А.В. Современное состояние исследований в области обфускации программ: определения стойкости обфускации // Труды института системного программирования, 2014б т. 26, вып. 3, с. 167-191.
- Cappaert J. Code Obfuscation Techniques for Software Protection. PhD Thesis, 2012, Leuven University.
