Лекции Computer Science клуба на Урале
Новости клуба
Новости клуба доступны через Google-группу клуба.Ближайшие лекции
С 9-го по 11-е декабря в клубе прочтет лекции Александр Шень (Институт проблем передачи информации РАН, Москва).
Аннотация
Целью этого курса является изложить некоторые классические результаты теоретической информатики, которые сочетают в себе (по возможности) разные качества:
-- формулировку и доказательство можно понять за ограниченное время, у нас имеющееся
-- результат достаточно фундаментальный для того, чтобы практическим
программистам стоило про него знать
-- результат не общеизвестный (последнее можно будет скорректировать
по ходу дела)
Примерный перечень возможных тем:
-- понятие универсальной функции (хранимой программы) и диагональная
конструкция алгоритмически неразрешимых проблем (перечислимого
неразрешимого множества)
-- конкретные модели и доказательство неразрешимости конкретных задач
(подстановки в словах = проблема тождества слов в полугруппах)
-- теорема Клини о неподвижной точке и self-referential конструкции
-- понятие сводимости как средство доказательства неразрешимости и
полиномиальной сводимости как средства сравнения сложности
-- case study: потоки в сетях, сведение к ним (двудольного) паросочетания,
вероятностный и детерминированный полиномиальные алгоритмы
-- правила доказательства свойств программ: примеры
-- вероятностные алгоритмы: пример анализа времени работы (быстрая сортировка)
-- пример результата из теории сложности: что значит и почему BPP
содержится в 
.
-- теория смыкается с практикой: регулярные выражения и конечные автоматы
-- алгебра и 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
Доклад представляет собой введение в формальные методы программной инженерии. Он рассказывает об основных подходах к формализации требований, способах использования формальных моделей при создании и сопровождении программного обеспечения, приводит примеры такого использования. Указываются и анализируются ограничения формальных методов, мешающие их использованию в промышленной разработке программных систем.
Слайды
Русский
English