Лекции Computer Science клуба на Урале

Новости клуба

Новости клуба доступны через Google-группу клуба.

Ближайшие лекции

С 9-го по 11-е декабря в клубе прочтет лекции Александр Шень (Институт проблем передачи информации РАН, Москва).

Аннотация
Целью этого курса является изложить некоторые классические результаты теоретической информатики, которые сочетают в себе (по возможности) разные качества:
-- формулировку и доказательство можно понять за ограниченное время, у нас имеющееся
-- результат достаточно фундаментальный для того, чтобы практическим программистам стоило про него знать
-- результат не общеизвестный (последнее можно будет скорректировать по ходу дела)
Примерный перечень возможных тем:
-- понятие универсальной функции (хранимой программы) и диагональная конструкция алгоритмически неразрешимых проблем (перечислимого неразрешимого множества)
-- конкретные модели и доказательство неразрешимости конкретных задач (подстановки в словах = проблема тождества слов в полугруппах)
-- теорема Клини о неподвижной точке и self-referential конструкции
-- понятие сводимости как средство доказательства неразрешимости и полиномиальной сводимости как средства сравнения сложности
-- case study: потоки в сетях, сведение к ним (двудольного) паросочетания, вероятностный и детерминированный полиномиальные алгоритмы
-- правила доказательства свойств программ: примеры
-- вероятностные алгоритмы: пример анализа времени работы (быстрая сортировка)
-- пример результата из теории сложности: что значит и почему BPP содержится в $ \Sigma_2 $.
-- теория смыкается с практикой: регулярные выражения и конечные автоматы
-- алгебра и computer science: разделение секрета, коды Рида--Соломона
-- алгебра и computer science: IP=PSPACE
-- пример из теории кодирования: границы Гилберта и Шеннона
-- пример из теории информации: шенноновская энтропия как граница для средней длины префиксного (или даже однозначного) кода
-- колмогоровская сложность (пример результата: теорема о сложности пары)
-- PCP: эквивалентность проверки доказательства и gap reduction
-- Доказательства с двумя пруверами: пример, когда квантовая механика позволяет перейти границу для классической
-- псевдослучайные генераторы: почему тестирование равносильно предсказанию

Место проведения лекции: УрФУ (ул. Мира 19), зал ученого совета

О лекторе
Александр Шень, сотрудник Института проблем передачи информации, исследователь Лаборатории фундаментальной информатики в Марселе, преподаватель НМУ, МГУ и 57 московской школы. Научные интересы:алгоритмы, колмогоровская сложность, логика, теория информации. С 1999 по 2001 год был редактором колонки в международном журнале Mathematical Intelligencer, под его редакцией вышел перевод первого издания книги Кормена, Лейзерсона и Ривеста "Алгоритмы: построение и анализ". Александр Шень является автором многих популярных книжек по математике и программированию, почти все они находятся в свободном доступе

Видеозаписи лекций

Online-трансляция лекций

Если по каким-либо причинам вы не сможете посетить лекции, на страничке нашего клуба http://logic.pdmi.ras.ru/csclub/uralcsclubonline, а также на сайте http://uralcsclub.onwebinar.ru/ вы сможете следить за онлайн-трансляцией лекций и задать свои вопросы лектору.

Прошедшие лекции

  • К. Симонова. Тестирование в MS SQL Server Engine. 16.11.2010

    Вы когда-нибудь задумывались, как Microsoft тестирует MS SQL Server (систему управления базами данных) - продукт, успех которого напрямую зависит от качества кода, в котором небольшая ошибка может легко привести к катастрофе и обернуться ущербом в миллионы долларов?
    Отказы оборудования неизбежны, но даже при отказе оборудования система должна быть в состоянии восстановить нормальную работу после устранения неисправности. Как же убедиться, что высокие требования, предъявляемые к функциональности и отказоустойчивости продукта, выполнены?
    Для этого в отделе тестирования MS SQL Server Engine используются несколько типов тестирования (функциональное, стресс тестирование, тестирование на основе модели и пр.) и набор инструментов (testability hooks), которые позволяют проверить требуемые сценарии. Для эффективного тестирования, тестеры участвуют в полном цикле разработки, начиная от дизайна новой функциональности до завершения проекта и принятия решения о готовности продукта. Весь процесс исполнения тестов и анализа ошибок автоматизирован и требует минимального участия тестеров. Об этом и многом другом вы узнаете, посетив доклад.
    Слайды

  • Ю. В. Матиясевич. Что можно делать с вещественными числами и нельзя с целыми. 28-31.10.2010

    Мини-спецкурс состоит из двух формально независимых частей. Взятые вместе, они демонстрируют существенное различие, с алгоритмической точки зрения, вещественных чисел и целых чисел. А именно, в первой части излагается версия алгоритм Тарского, позволяющего установить истинность или ложность любой замкнутой арифметической формулы первого порядка с переменными для вещественных чисел. В качестве "бесплатного" приложения этот алгоритм дает разрешимость "элементарной" геометрии (через введенный Р. Декартом "метод координат"). Во второй части рассказывается про отрицательное решение десятой проблемы Гильберта, в которой он просил найти алгоритм, который позволял бы по произвольному диофантову уравнению узнавать, имеет ли оно решения в целых числах - такого алгоритма не существует.
    Ю.В. Матиясевич. Алгоритм Тарского (PDF)
    Слайды лекций 1-2 Слайды лекций 3-4 Слайды лекций 5-6
    Упражнения к курсу Тексты упражнений


  • В. В. Кулямин. Формализация требований к программам. 27-28.09.2010
    Доклад представляет собой введение в формальные методы программной инженерии. Он рассказывает об основных подходах к формализации требований, способах использования формальных моделей при создании и сопровождении программного обеспечения, приводит примеры такого использования. Указываются и анализируются ограничения формальных методов, мешающие их использованию в промышленной разработке программных систем.
    Слайды