2 semester

1

Course title

Modeling and optimization

2

Term, study programme

1st year, 1-31 81 08 Computer Mathematics and System Analysis

3

Semester

2

4

Credits

7

5

Lecturer

Cherginets Dmitry Nikolaevich

6

Course Objective

Formation of theoretical principles of linear programming and integer linear programming, as well as development of skills for applying theoretical knowledge in solving applied problems.

7

Prerequisites

Algebra and Number Theory, Optimization Methods

8

Course content

Hachiyan’s method for linear programming. Rounding of polytopes. The reduced basis of the lattice. Linear Diophantine equations and systems. Introduction to integer linear programming. The complexity of integer linear programming. Lenstra’s algorithm for integer linear programming. The knapsack problem. Merkle–Hellman knapsack cryptosystem. Shamir attack. Cutting-plane method. The branch and bound method. Practical tasks.

9

Recommended Literature

  1. Схрейвер, А. Теория линейного и целочисленного программирования: в 2 т.: пер. с англ. Т. 1. – Москва: Мир, 1991.
  2. Схрейвер, А. Теория линейного и целочисленного программирования: в 2 т.: пер. с англ. Т. 2. – Москва: Мир, 1991.
  3. Grötschel, M.  Geometric Algorithms and Combinatorial Optimization / M. Grötschel, L. Lovàsz, A. Schrijver. –  Springer, 1988.
  4. Маховенко, Е.Б. Теоретико-числовые методы в криптографии / Е.Б. Маховенко. – М.: Гелиос АРВ, 2006. – 320с.
  5. Шевченко, В.Н. Линейное и целочисленное линейное программирование / В.Н. Шевченко, Н.Ю. Золотых. — Нижний Новгород: Изд-во Нижегородского госуниверситета им. Н.И. Лобачевского, 2004.

10

Teaching Methods

Mixed with elements of distance learning, Problem-based learning, Research-based learning

11

Teaching language

Russian

12

Requirements, current control

Presentation and discussion of laboratory results. Exam score consist of the current mark (40%) and the oral exam mark (60%).

13

Method of certification

Credit, Exam