Открытые лекции ФКН. День третий

2, 6 и 8 апреля состоятся Открытые лекции, приуроченные к Дням компьютерных наук и празднованию пятилетия факультета. Для посещения лекций необходима регистрация.

Программа на 8 апреля

11:00-12:00, ауд. 205

Александр Петренко, профессор базовой кафедры "Системное программирование" Института системного программирования РАН: "Приоритеты компьютерных наук – опыт анализа Тьюринговских лекций" 

Тьюринговская лекция – самая престижная награда за научные достижения в области информатики. Эти достижения составляют базис, на котором строятся современные информационные технологии. Анализ истории появления, признания и освоения наиболее значимых научных результатов позволяет лучше понять современные приоритеты компьютерных наук. 

12:00-13:00, room 509
Vladimir Protasov, professor of big data and information retrieval school: "Derivative-free optimisation: evolution of ideas"

How to compute the minimum of a multivariate function? Find zeros of its derivatives. What if we are not able to differentiate? Such problems arise naturally in many important applications. Surprisingly enough, even without derivatives there are efficient methods of minimisation, provided the function is convex. For univariate functions, an optimal method was presented in 1953 by J.Kiefer (Fibonacci algorithm), but its extension to functions of many variables turned out to be a challenging problem. The first approach used the ideas of cutting plane originated with A.Levin and D.Newman (1965) and developed by the Shor-Nemirovsky-Yudin ellipsoid algorithm in late seventies. Derivative-free versions of those methods (1996) has a perfect theoretical complexity estimate but is hardly applicable in high dimensions. New progress in this problem required new geometrical constructions and new conceptual ideas.

13:00-14:00, ауд. 205
Владимир Подольский, доцент департамента больших данных и информационного поиска: "Сложность плотных линейных операторов"

Пусть нам дан вектор x булевых переменных, и мы хотим вычислить булев линейный оператор Ax с квадратной булевой матрицей A. Другими словами, для всех строк A мы хотим вычислить дизъюнкцию тех переменных x, для которых соответствующая координата строки равна 1. Вычисление начинается с переменных и за один шаг разрешается вычислить дизъюнкцию двух ранее вычисленных выражений (таким образом, мы строим булеву схему, состоящую из операций дизъюнкции). Есть матрица A разреженная (содержит O(n) единиц), оператор легко вычислить за O(n) операций. Мы покажем, что то же самое можно сделать для очень плотных матриц (содержащих O(n) нулей). Этот результат переносится на вычисления операторов над любыми коммутативными полугруппами. Мы также показываем, что аналогичное утверждение неверно для полуколец, являющихся существенно некоммутативными.

14:00-15:00, ауд. 509
Михаил Вялый, профессор департамента больших данных и информационного поиска: "Комбинаторные нижние оценки для сложности описания регулярных языков"

Сложность описания (descriptional complexity) – большая область теории формальных языков. Основной вопрос в этой области: как соотносится длина описания одного и того же языка при разных способах
описания. Хороших общих методов поиска ответа на такой вопрос не существует, отчасти из-за большого разнообразия конкретных моделей построения языков. 

В лекции будет рассказано об одной задаче из этой области, связанной со сравнением недетерминированных автоматов и автоматов со счётчиками. В общем случае автоматы со счётчиками сильнее и распознают нерегулярные языки. Однако, если рассматривать "коммутативную версию" этих моделей вычисления, то их выразительная сила совпадает (теорема Парика). Остаётся вопрос о том, насколько различается
сложность описания одного и того же "коммутативного языка" в этих моделях. Недавно было доказано, эта сложность может значительно различаться. 

Для доказательства нижних оценок потребовалась комбинаторная задача о закрашивании правильных скобочных выражений. Это интересный и свежий вопрос о таком хорошо известном объекте как правильные скобочные выражения. Вполне возможно, что задача о закрашивании скобок найдет и другие приложения. Рассказу об этой задаче также будет уделено внимание на лекции. 

15:00-16:00, ауд. 205
Ирина Ломазова, профессор департамента программной инженерии: "Эквивалентность ресурсов в сетях Петри"

Сети Петри – удобный, наглядный, и в то же время математически строгий формализм для моделирования и анализа распределенных систем. Фишки в сетях Петри задают разметку сети и служат для представления управляющего состояния системы и/или ресурсов, которые потребляются/производятся в ходе выполнения некоторого действия. Соответственно часть разметки сети можно интерпретировать как ресурсы, обеспечивающие будущее поведение системы. 

В лекции будет дано несколько способов определения эквивалентности ресурсов в сетях Петри. Содержательно, два ресурса будем считать эквивалентными, если замена одного из них на другой в любой достижимой разметке не меняет наблюдаемого поведения сети. Мы приведем результаты о разрешимости эквивалентности ресурсов, представим алгоритм для вычисления конечной аппроксимации этого отношения и обсудим применение эквивалентности ресурсов для редукции множества достижимых состояний и адаптивного управления системой.

16:00-17:00, ауд. 509
Алексей Осадчий, профессор департамента анализа данных и искусственного интеллекта: "От нейрокартирования к нейроинтерфейсам и обратно"

Современные технологии неинвазивной нейровизуализации позволяют с миллиметровой точностью и без нарушения целостности тканей исследовать нейрональные процессы, протекающие на миллисекундном временном масштабе в головном мозге человека при выполнении широкого спектра задач – от базовых моторных функций до сложных процессов принятия решений. Помимо аппаратных средств, построение пространственно-временных карт активности головного мозга невозможно без математических методов обработки сигналов сенсоров. Мой рассказ – о методиках анализа электро- и магнитоэнцефалографических данных, разрабатываемых в нашей лаборатории, и их применения к широкому кругу задач: фундаментально-научных, диагностических, реабилитационных и развлекательных.

17:00-18:00, ауд. 205
Panos Pardalos, Academic Supervisor:HSE Campus in Nizhny Novgorod / Laboratory of Algorithms and Technologies for Networks Analysis: "Sustainable interdependent networks"

Sustainable interdependent networks have a wide spectrum of applications in computer science, electrical engineering, and smart infrastructures. We are going to discuss the next generation sustainability framework as well as smart cities with special emphasis on energy, communication, data analytics and financial networks. In addition, we will discuss solutions regarding performance and security challenges of developing interdependent networks in terms of networked control systems, scalable computation platforms, and dynamic social networks. 

18:00-19:00, ауд. 509
Valery Kalyagin, Professor:HSE Campus in Nizhny Novgorod / Faculty of Informatics, Mathematics, and Computer Science: "Uncertainty of decision making in random variables networks"

Random variables network is a graph with n nodes, associated with a random vector of dimension n. Nodes of the graph are associated with random variables (components of the random vector) and weights of edges are given by some measure of association (dependency, similarity) between them. Data mining in random variables network is an important problem with numerous applications. In this paper we consider the clustering problem in random variables network. The main question is how to handle uncertainty of clustering algorithms generated by uncertainty of the data. We suggest an approach based on decision theory and construct a robust (distribution free) clustering algorithms in random variables networks.

19:00-20:00, ауд. 205
Ricardo Gomez, CERN fellow: "The need for computer sciences in High Energy Physics"

In the last decade the complexity of High Energy Physics experiments has increased dramatically as well as the amount of data that has to be handled. Moreover, the upgrades that are being planned will increase data volumes by more than two orders of magnitude. Consequently, more sophisticated computing techniques for data analysis have to be developed to keep the data manageable. In this lecture the current use of Computer Science techniques in High Energy Physics and the future challenges ahead of us will be presented.

 Афиша (PDF, 525 Кб)