Лабо Ж.-В.Понселе: Н.Верещагин
Лаборатория Ж.-В.Понселе: Н.ВерещагинИсследователь в лаборатории с февраля 2005 г.
Постоянный место работы:
Кафедра математической логики и теории алгоритмов, Факультет механики и математики, Московский государственный университет, Москва, 119899 Россия.
ФАКС: +7 095 939 3031
E-mail: ver AT mech.math.msu.su
Общий
Личный
Родился 27.10.1958 в Москве, Россия.
Текущая принадлежность
Профессор Московского государственного университета им. М.В. Ломоносова Факультет механики и математики Кафедра математической логики и теории алгоритмов
Текущая область исследований
Вычислительная сложность, Колмогоровская сложность
Прочая деятельность
Член программного комитета 18-я конференция IEEE по вычислительной сложности, 2003 г., Орхус (Дания) и
18-й Международный симпозиум по теоретическим аспектам Информатика, 2001, Дрезден (Германия).
Материалы конференции
- 2004
- 31-й Международный коллоквиум по автоматам, языкам и Программирование, ICALP, Турку, Финляндия
- 2005, 2004, 1999
- Симпозиум по теоретическим аспектам компьютерных наук, STACS
- 2002
- 47-й симпозиум IEEE по основам информатики, ФОКС.
- 2001, 2000, 1999, 1998, 1997, 1993, 1992
- Ежегодная конференция IEEE по вычислительной сложности.
- 2003, 1996
- Dagstuhl-семинары «Структура и сложность» и «Колмогоровская сложность и приложения», Замок Дагштуль, Германия
- 1995
- Восьмая ежегодная конференция по вычислительному обучению Theory, Санта-Круз, Калифорния, США
- 1995
- Третий Израильский симпозиум по теории вычислений и систем, Тель-Авив, Израиль (два выступления)
- 1994
- Мастерская COLORET, Амстердам, Нидерланды
- 1992
- Конференция по логическим основам информатики. Тверь, Россия.
- 1991
- Мемориальная конференция Суслина. Саратов, Россия.
- 1988
- 9-я Всесоюзная конференция по математической логике, Ленинград, Россия.
- 1985
- 18-я Всесоюзная алгебраическая конференция, Кишинев, Молдова
- 1982
- 6-я Всесоюзная конференция по математической логике, Тбилиси, Грузия.
Международный опыт
- 2005, 2004, 2003, 2002, 2001
- Месячный исследовательский визит в КВИ, Амстердам. Приглашены Х. Бурман и П. Витани.
- 2004, 2003, 2002, 2001, 2000
- Месячный исследовательский визит в Университет Прованса, Франция. Приглашен Бруно Дюран.
- 2003
- Конференция IEEE по вычислительной сложности, Орхус (Дания). Член программного комитета.
- Дагштуль-семинар «Колмогоровская сложность и ее приложения»
- 2004, 2002
- Дагштуль-семинар «Алгебраические методы в квантовых и классические вычисления»
- 2001
- 18-й Международный симпозиум по теоретическим аспектам Информатика, Дрезден, Германия. Член программного комитета.
- 1999
- 3-месячный исследовательский визит в Ecole Normale Supérieure в Лионе, Франция. Приглашен Бруно Дюран.
- 1998
- 13-я ежегодная конференция IEEE по вычислительной технике Сложность, Буффало, США.
- 1998
- 3-месячная исследовательская поездка в Вюрцбургский университет, Германия. Приглашен Клаусом Вагнером.
- 1997/1998
- 6-месячный исследовательский визит в Ecole Normale Supérieure в Лионе, Франция.
- 1997
- Месячная исследовательская поездка в Университет Рутгерса, США. Приглашен Эриком Аллендером.
- 1997
- 12-я ежегодная конференция IEEE по вычислительным Теория сложности, Ульм, Германия.
- 1997
- Месячная исследовательская поездка в Амстердамский университет. По приглашению П. ван Эмде Боаса и P.M.B. Витаний.
- 1997
- 10-дневный исследовательский визит в Университет Иоганна Гутенберга, Майнц, Германия. Приглашен Клеменсом Лаутеманном.
- 1996
- Дагштуль-семинар «Структура и сложность»
- 1995
- Третий Израильский симпозиум по теории вычислительной техники and Systems, Тель-Авив, Израиль, январь 1995 г.
- 1994
- Двухнедельная исследовательская поездка в Университет Рочестера, штат Нью-Йорк, США. Приглашен Лейн Хемаспаандра.
- 1994
- ЦВЕТ мастерская, Амстердам, Нидерланды
- 1994
- 9-я ежегодная конференция IEEE по структуре в сложности Theory, Амстердам, Нидерланды
Семинары проводятся
Московский государственный университет, механико-математический факультет
- Колмогоров Семинар по сложности описания и сложности вычислительной техники (совместно с А.Л.Семеновым и А.Х.Шеном), 1984—, выпускник.
- Профессиональный семинар по математической логике и теории алгоритмов (совместно с В. А.Успенским, А.Л.Семеновым, А.Х.Шеном, А.А.Разборовым), 1984—, бакалавриат.
Последние публикации
Учебники
- А. Шен и Н. Верещагин.
Математическая логика и теория вычислений. Элементы теории множеств.
Московский центр непрерывного математического образования, 1999, 127 стр.
(Русский)
Английский перевод: Теория основных множеств. Американское математическое общество. Студенческая математическая библиотека, вып. 17. 2002 г. - А. Шен и Н. Верещагин. Математическая логика и теория вычислений.
Вычислимые функции.
Московский центр непрерывного математического образования, 1999, 174 страницы.
(Русский)
Английский перевод: Вычислимые функции. Американское математическое общество. Студенческая математическая библиотека, вып. 19. 2003 г. - А. Шен и Н. Верещагин. Математическая логика и теория вычислений. Языки и исчисления. Московский центр непрерывного математического образования, 1999, 286 стр. (Русский)
- В. А. Успенский, Н.К. Верещагин, В.Е. Плиско. Введение в математическую логику. Издательство МГУ, 1991, Наука, 2004. 136 с.
Глава в книге
- Н. Верещагин. Релятивизируемость в теории сложности.
Глава в книге Л.Д. Беклемишев, М. Пентус,
Н. Верещагин, Доказуемость, Сложность, Грамматика,
AMS Translations, Series 2, v.
192 , 1999, стр. 87–172.
Публикации в рецензируемых журналах
- Н. Верещагин и П. Витаний. «Колмогорова Функции структуры с приложением к основам выбора модели» IEEE Transactions on Information Theory 50:12 (2004) 3265-3290. Предварительная версия: проц. 47-й симпозиум IEEE. Найденный. вычисл. наук, 2002, 751—760.
- Б. Дюран, Н. Верещагин. «Стохастичность Колмогорова-Лавленда для конечных строк «. Письма по обработке информации, 91 (2004 г.) 263-269.
- О. Митина и Н. Верещагин. «Как использовать несколько зашумленных каналов с неизвестной вероятностью ошибки» Информация и вычисления 182 (2003) 229-241. Предварительный версия появилась под названием «Как воспользоваться советами экспертов в случае, когда фактические значения предполагаемых событий остаются неизвестный.» проц. Восьмая ежегодная конференция по вычислительному обучению Теория (5-8 июля), 1995, Санта-Круз, Калифорния, 91-97.
- Н.К. Верещагин, Д.П. Скворцов, Е.З. Скворцова, А.В. Чернов. Варианты реализуемости пропозициональных формул. и логика слабого закона исключенного третьего. Труды МИАН 242 (2003) 67-85. Предварительная версия появилась в: Труды Computer Science Logic’02, Конспект лекций по информатике, 2002, т. 2471, стр. 74–88.
- Б. Дюран, В. Кановей, В. Успенский, Н. Верещагин. «Сделай сильнее определения случайности существуют?» Теоретическая информатика 290: 3 (2003) 1987–1996.
- К. Макарычев, Ю.А. Макарычев, А. Ромащенко, Н. Верещагин. «Новый класс неравенства не шеннонского типа для энтропий Коммуникации в информации и системах, 2:2 (2002) 147-166.
- Н. Верещагин. «Колмогоровская сложность, обусловленная большими целыми числами». Теоретическая информатика 271 (2002) 59—67.
- Н. Верещагин и М. Вьюгин. «Независимые программы минимальной длины для перевода между заданные строки». Теоретическая информатика 271 (2002) 131–143. Предварительная версия в: проц. 15-го ежегодного IEEE Конференция по вычислительной сложности, Флоренция, июль 2000 г., стр. 138–144.
- А. Ромащенко, А. Шень, Н. Верещагин. «Комбинаторная интерпретация колмогоровской сложности», Теоретическая информатика 271 (2002) 111–123. Предварительная версия в: проц. 15-й ежегодной конференции IEEE по вычислительной сложности, Флоренция, июль 2000 г., стр. 131–137.
- А. Чернов, Ан. Мучник, А. Ромащенко, А. Шень, Н. Верещагин. Верхняя полурешетка двоичных строк с отношением «x просто зависит от y». Теоретическая информатика 271 (2002) 69—95}. Предварительная версия в: 14-я ежегодная конференция IEEE по вычислительной сложности, Атланта, 4-6 мая, 1999, 114–122.
- А. Шен и Н. Верещагин. «Логические операции и колмогоровская сложность». Теоретическая информатика 271 (2002) 125–129.
- Д. Хаммер, А. Ромащенко, А. Шен и Н. Верещагин. «Неравенства для энтропии Шеннона и колмогоровской сложности». Журнал компьютерных и системных наук 60 (2000) 442-464.
- Р. Раз, Г. Тардос, О. Вербицкий, Н. Верещагин. «Игры Артура-Мерлина в логических деревьях решений». Журнал компьютерных системных наук 59 (1999) 346-372,
- Б. Дюран, А. Шен, Н. Верещагин. «Описательная сложность вычислимых последовательностей». Теоретическая информатика 171 (2001), с. 47—58; Предварительная версия: Proc. 16-го анн. Симп. на Теоретические аспекты информатики, Трир, Германия, март 1999, LNCS 1563, стр. 153–162.
Публикации материалов выборочных конференций
- Х. Бурман, Х. Клаук,
Н. Верещагин, П. Витаний.
«Индивидуальная сложность общения».
21-й ежегодный симпозиум по теоретическим аспектам
компьютерных наук, STACS 2004, Монпелье, Франция, 25-27 марта,
2004, Материалы.