Modern trends in discrete mathematics and computer science — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
м
 
(не показаны 53 промежуточных версий 4 участников)
Строка 1: Строка 1:
−
[[Категория:Спецкурсы кафедры МК]]
+
[[Категория:Спецкурсы кафедры МК (архив)]]
 +
 
 +
[[Категория:Лекционные курсы кафедры МК (архив)]]
  
 
Compulsory course for master students, 2-nd year, groups 618/1 and 618/2.  
 
Compulsory course for master students, 2-nd year, groups 618/1 and 618/2.  
Строка 9: Строка 11:
 
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.
 
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.
  
−
== Lecture 1. '''[[Media: LectEng1.pdf| Theory and practice of software obfuscation.]]''' ==
+
= Preliminary program and materials =
 +
 
 +
== Lecture 1. '''Theory and practice of software obfuscation.''' ==
 +
 
 +
[[Media: LectEng1.pdf|Presentation.]]
  
 
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.  
 
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'''.
+
Lecturer: '''Vladimir Zakharov'''.
 +
 
 +
[[Media: paper-zakharov.pdf|Статья для составления реферата.]]
 +
 
 +
== Lecture 2. '''Formal correctness proofs for sequential programs.''' ==
 +
 
 +
[[Media: LectEng2.pdf|Presentation.]]
 +
 
 +
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]]
 +
 
 +
Essay topics:
 +
* [3], p.127-144. Explain the main ideas of the procedural extension of while programs and corresponding proof systems, and the relationship between the extension and the "real" programming.
 +
* [3], p.245-261. Explain the main ideas of the parallel extension of while programs and corresponding proof systems, and the relationship between the extension and the "real" programming.
 +
 
 +
Link to [3]: https://drive.google.com/open?id=1EAD7Ax9sU32E-9qZldmkrWRABQC1Awah
 +
 
 +
== Lectures 3,4. '''Constraint satisfaction problem: the algebraic approach.''' ==
 +
 
 +
[[Media: lect3-4-eng-selezn.pdf|Presentation]].
 +
 
 +
The topic of the lecture is the constraint satisfaction problem (for short, CSP). CSP is a universal formalization for a wide variety of problems in discrete mathematics and computer science. A characterization of the CSP complexity has recently been obtained by the algebraic approach. The aim of the lecture is to describe the algebraic approach to CSP and the results established by its applying.
 +
 
 +
Lecturer: [[Селезнева Светлана Николаевна | Svetlana N. Selezneva]]
 +
 
 +
== Lecture 5. '''Closed classes in k-valued and partial k-valued logics.''' ==
 +
 
 +
The lecture provides an overview of the results on the description of lattice fragments of closed classes (with respect to superposition) in k-valued and partial k-valued logics and describes the latest achievements in this field. Results will be presented on precomplete classes in k-valued and partial k-valued logics, on closed classes in partial k-valued logic, containing a given precomplete class of k-valued logic.
 +
 
 +
Literature:
 +
# [[Media: Lau.pdf|Lau, D.]]. Function algebras on finite sets. A basic course on many-valued logic and clone theory. Springer Monographs in Mathematics. Springer-Verlag Berlin-Heidelberg 2006. P. 619-628. Обозначения см. на стр. 655-661.
 +
# [[Media: Алексеев_Вороненко.pdf|Алексеев В.Б., Вороненко А.А.]].  О некоторых замкнутых классах в частичной двузначной логике, Дискрет. матем., 1994, том 6, выпуск 4, 58–79
 +
 
 +
Задания:
 +
 
 +
1. Сформулировать решаемую задачу и основные полученные результаты из раздела 20.7 (страницы 619-627) книги Lau.
 +
 
 +
2. Сформулировать результаты по мощности множества классов, содержащих заданный замкнутый класс булевых функций, по статье Алексеев, Вороненко и разделу 20.8 (стр. 627-628) книги Lau.
 +
 
 +
Lecturer: V.B. Alekseev.
 +
 
 +
== Lecture 6. '''Algebras of minimal multiplicative complexity.''' ==
 +
 
 +
[[Media: LectEng4.pdf|Presentation.]]
 +
 
 +
We prove that an associative algebra A has minimal rank if and only if the Alder–Strassen bound is also tight for the multiplicative complexity of A, that is, the multiplicative complexity of A is 2 dimA - t(A) where t(A) denotes the number of maximal twosided ideals of A. This generalizes a result by E. Feig who proved this for division algebras. Furthermore,we show that if A is local or superbasic, then every optimal quadratic computation for A is almost bilinear.
 +
 
 +
Lecturer: '''Bekhan Chokaev'''.
 +
 
 +
[[Media: paper-chokaev-1.pdf|Статья 1.]]
 +
 
 +
[[Media: paper-chokaev-2.pdf|Статья 2.]]
 +
 
 +
== Lecture 7. '''Some new bounds of Shannon functions for cardinality of test sets for logical circuits.''' ==
 +
 
 +
This lecture gives an overview of the current state of art in the theory of control of logic circuits, which is connected with the study of the behavior of the Shannon functions of test lengths (that is, the lengths of minimal tests for the most difficult to test functions).
 +
 
 +
== Lecture 8. '''13С metabolic flux analysis.''' ==
 +
 
 +
Isotopic experiments with heavy carbon atoms (13C metabolic flux analysis) are a common method for analyzing the rates of metabolic reactions, the so-called “fluxes” (13C metabolic flux analysis). In the framework of the lecture, it is supposed to consider the main approaches to modeling the redistribution of heavy carbon atoms in the process of cell activity, as well as the main methods for solving the problem of determining metabolic fluxes.
 +
 
 +
[[Media: paper-shupletsov-1.pdf|Статья 1.]]
  
−
# '''Formal correctness proofs for sequential programs.'''
+
[[Media: paper-shupletsov-2.pdf|Статья 2.]]
−
#* Лекция посвящена изучению и обсуждению дедуктивных методов верификации (проверки корректности) последовательных императивных программ. В лекции рассматриваются полезные свойства формальных систем верификации программ и примеры их применения к проверке правильности небольших программ.
+
−
# '''Constraint satisfaction problem: an algebraic approach.'''
+
−
#* Задача удовлетворения ограничений состоит в выяснении выполнимости системы отношений. При этом отношения принадлежат заранее известному множеству S и зависят от произвольных переменных. В русскоязычной литературе она также называется задачей обобщенной выполнимости. Многочисленные вопросы информатики (в частности, в распознавании образов, анализе программ, представлении знаний, базах данных) и дискретной математики (например, раскраски графов) естественным образом выражаются в терминах этой задачи. Перспективным подходом к ее решению считается алгебраический подход. Он состоит в рассмотрении функций, сохраняющих все отношения из множества S. В зависимости от вида этих функций можно показать либо полиномиальность, либо NP-полноту соответствующей задачи. В двух лекциях предполагается определить задачу удовлетворения ограничений, показать примеры ее применения, описать алгебраический подход к ее решению и рассказать о полученных с его помощью результатах, в том числе совсем новых.
+
−
# '''Closed classes in k-valued and partial k-valued logics.'''
+
−
#* В лекции приводится обзор результатов по описанию фрагментов решетки замкнутых классов (относительно суперпозиции) в k-значной и частичной k-значной логиках и рассказано о последних достижениях в этой области. Будут представлены результаты о предполных классах в k-значной и частичной k-значной логиках, о замкнутых классах в k-значной логике, содержащих класс Слупецкого или все полиномы, о замкнутых классах в частичной k-значной логике, содержащих заданный предполный класс k-значной логики.
+
−
# '''Read-once functions.'''
+
−
#* Основной объект изучения - булевы функции, представимые формулами без повторения аргументов. Рассматриваются вопросы тестирования и расшифровки функций (в том числе мощными оракулами). Также рассматривается схемное распознавание свойства бесповторности и сертификатное доказательство повторности функций.
+
−
# '''Some new bounds of Shannon functions for cardinality of test sets for logical circuits.'''
+
−
#* В лекции будет рассказано о современном состоянии той части теории контроля логических схем, которая связана с изучением поведения функций Шеннона длин тестов (то есть длин минимальных тестов для самых труднотестируемых функций).
+
−
# '''13С metabolic flux analysis.'''
+
−
#* Изотопные эксперименты с тяжелыми атомами углерода (13С metabolic flux analysis) являются распространенным методом анализа скоростей метаболических реакций, так называемых «потоков» (13С metabolic flux analysis). В рамках лекции предполагается рассмотреть основные подходы к моделированию перераспределения тяжелых атомов углерода в процессе жизнедеятельности клетки, а также основные методы решения задачи определения метаболических потоков.
+
  
−
== Literature ==
+
= Literature =
  
−
# Варновский Н.П., Захаров В.А., Кузюрин Н.П., Шокуров А.В. Современное состояние исследований в области обфускации программ: определения стойкости обфускации // Труды института системного программирования, 2014б т. 26, вып. 3, с. 167-191.
+
# Варновский Н.П., Захаров В.А., Кузюрин Н.П., Шокуров А.В. Современное состояние исследований в области обфускации программ: определения стойкости обфускации // Труды института системного программирования, 2014, т. 26, вып. 3, с. 167-191.
 
# Cappaert J. Code Obfuscation Techniques for Software Protection. PhD Thesis, 2012, Leuven University.
 
# Cappaert J. Code Obfuscation Techniques for Software Protection. PhD Thesis, 2012, Leuven University.
 +
# Apt K.R., Boer F.S., Olderog E.-R. Verification of sequential and concurrent programs. Third, extended edition. Springer, 2010.
 +
# Kleene S.C. Mathematical logic. 1967.
 +
# Creignou N., Khanna S., Sudan M. Complexity classifications of Boolean constraint satisfaction problems. 2001.
 +
# Bulatov A., Jeavons P., Krokhin A. Classifying the complexity of constraints using finite algebras // SIAM J. Comput. 2005. V. 34, N 3. P. 720-742.
 +
# Lau, D. Function algebras on finite sets. A basic course on many-valued logic and clone theory. Springer Monographs in Mathematics. Springer-Verlag Berlin-Heidelberg 2006.
 +
# Peter B¨urgisser, Michael Clausen, and M. Amin Shokrollahi. Algebraic Complexity Theory. Springer, 1997.
 +
# Yurij A. Drozd and Vladimir V. Kirichenko. Finite Dimensional Algebras. Springer, 1994.
 +
# A. Alder and V. Strassen. On the algorithmic complexity of associative algebras. Theoret. Comput. Sci., 15:201–211, 1981.
 +
# Valery B. Alekseyev. On the Complexity of Some Algorithms of Matrix Multiplication. J. Algorithms, 6(1):71-85, 1985.
 +
# Markus Bl¨aser. Lower bounds for the multiplicative complexity of matrix multiplication. Comput. Complexity, 8:203-226, 1999.
 +
# Markus Bl¨aser. Lower bounds for the bilinear complexity of associative algebras. Comput. Complexity, 9:73-112, 2000.
 +
# Markus Bl¨aser. A 2:5n2-lower bound for the multiplicative complexity of n х n-matrix multiplication. In Proc. 18th Int. Symp. on Theoret. Aspects of Comput. Sci. (STACS), Lectures Notes in Comput. Sci. 2010, 99-110, 2001.

Текущая версия на 23:06, 7 октября 2024


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.

Preliminary program and materials

Lecture 1. Theory and practice of software obfuscation.

Presentation.

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.

Presentation.

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

Essay topics:

  • [3], p.127-144. Explain the main ideas of the procedural extension of while programs and corresponding proof systems, and the relationship between the extension and the "real" programming.
  • [3], p.245-261. Explain the main ideas of the parallel extension of while programs and corresponding proof systems, and the relationship between the extension and the "real" programming.

Link to [3]: https://drive.google.com/open?id=1EAD7Ax9sU32E-9qZldmkrWRABQC1Awah

Lectures 3,4. Constraint satisfaction problem: the algebraic approach.

Presentation.

The topic of the lecture is the constraint satisfaction problem (for short, CSP). CSP is a universal formalization for a wide variety of problems in discrete mathematics and computer science. A characterization of the CSP complexity has recently been obtained by the algebraic approach. The aim of the lecture is to describe the algebraic approach to CSP and the results established by its applying.

Lecturer: Svetlana N. Selezneva

Lecture 5. Closed classes in k-valued and partial k-valued logics.

The lecture provides an overview of the results on the description of lattice fragments of closed classes (with respect to superposition) in k-valued and partial k-valued logics and describes the latest achievements in this field. Results will be presented on precomplete classes in k-valued and partial k-valued logics, on closed classes in partial k-valued logic, containing a given precomplete class of k-valued logic.

Literature:

  1. Lau, D.. Function algebras on finite sets. A basic course on many-valued logic and clone theory. Springer Monographs in Mathematics. Springer-Verlag Berlin-Heidelberg 2006. P. 619-628. Обозначения см. на стр. 655-661.
  2. Алексеев В.Б., Вороненко А.А.. О некоторых замкнутых классах в частичной двузначной логике, Дискрет. матем., 1994, том 6, выпуск 4, 58–79

Задания:

1. Сформулировать решаемую задачу и основные полученные результаты из раздела 20.7 (страницы 619-627) книги Lau.

2. Сформулировать результаты по мощности множества классов, содержащих заданный замкнутый класс булевых функций, по статье Алексеев, Вороненко и разделу 20.8 (стр. 627-628) книги Lau.

Lecturer: V.B. Alekseev.

Lecture 6. Algebras of minimal multiplicative complexity.

Presentation.

We prove that an associative algebra A has minimal rank if and only if the Alder–Strassen bound is also tight for the multiplicative complexity of A, that is, the multiplicative complexity of A is 2 dimA - t(A) where t(A) denotes the number of maximal twosided ideals of A. This generalizes a result by E. Feig who proved this for division algebras. Furthermore,we show that if A is local or superbasic, then every optimal quadratic computation for A is almost bilinear.

Lecturer: Bekhan Chokaev.

Статья 1.

Статья 2.

Lecture 7. Some new bounds of Shannon functions for cardinality of test sets for logical circuits.

This lecture gives an overview of the current state of art in the theory of control of logic circuits, which is connected with the study of the behavior of the Shannon functions of test lengths (that is, the lengths of minimal tests for the most difficult to test functions).

Lecture 8. 13С metabolic flux analysis.

Isotopic experiments with heavy carbon atoms (13C metabolic flux analysis) are a common method for analyzing the rates of metabolic reactions, the so-called “fluxes” (13C metabolic flux analysis). In the framework of the lecture, it is supposed to consider the main approaches to modeling the redistribution of heavy carbon atoms in the process of cell activity, as well as the main methods for solving the problem of determining metabolic fluxes.

Статья 1.

Статья 2.

Literature

  1. Варновский Н.П., Захаров В.А., Кузюрин Н.П., Шокуров А.В. Современное состояние исследований в области обфускации программ: определения стойкости обфускации // Труды института системного программирования, 2014, т. 26, вып. 3, с. 167-191.
  2. Cappaert J. Code Obfuscation Techniques for Software Protection. PhD Thesis, 2012, Leuven University.
  3. Apt K.R., Boer F.S., Olderog E.-R. Verification of sequential and concurrent programs. Third, extended edition. Springer, 2010.
  4. Kleene S.C. Mathematical logic. 1967.
  5. Creignou N., Khanna S., Sudan M. Complexity classifications of Boolean constraint satisfaction problems. 2001.
  6. Bulatov A., Jeavons P., Krokhin A. Classifying the complexity of constraints using finite algebras // SIAM J. Comput. 2005. V. 34, N 3. P. 720-742.
  7. Lau, D. Function algebras on finite sets. A basic course on many-valued logic and clone theory. Springer Monographs in Mathematics. Springer-Verlag Berlin-Heidelberg 2006.
  8. Peter B¨urgisser, Michael Clausen, and M. Amin Shokrollahi. Algebraic Complexity Theory. Springer, 1997.
  9. Yurij A. Drozd and Vladimir V. Kirichenko. Finite Dimensional Algebras. Springer, 1994.
  10. A. Alder and V. Strassen. On the algorithmic complexity of associative algebras. Theoret. Comput. Sci., 15:201–211, 1981.
  11. Valery B. Alekseyev. On the Complexity of Some Algorithms of Matrix Multiplication. J. Algorithms, 6(1):71-85, 1985.
  12. Markus Bl¨aser. Lower bounds for the multiplicative complexity of matrix multiplication. Comput. Complexity, 8:203-226, 1999.
  13. Markus Bl¨aser. Lower bounds for the bilinear complexity of associative algebras. Comput. Complexity, 9:73-112, 2000.
  14. Markus Bl¨aser. A 2:5n2-lower bound for the multiplicative complexity of n х n-matrix multiplication. In Proc. 18th Int. Symp. on Theoret. Aspects of Comput. Sci. (STACS), Lectures Notes in Comput. Sci. 2010, 99-110, 2001.
Источник — «https://mk.cs.msu.ru/index.php?title=Modern_trends_in_discrete_mathematics_and_computer_science&oldid=11395»