RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Санкт-Петербургский логический семинар
30 июня 2020 г. 18:30, г. Санкт-Петербург, online
 


What, if anything, can be done in linear time?

Yu. Gurevich

University of Michigan
Видеозаписи:
MP4 109.1 Mb
Материалы:
Adobe PDF 262.4 Kb

Количество просмотров:
Эта страница:139
Видеофайлы:9
Материалы:12
Youtube Video:

Yu. Gurevich


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке



Аннотация: The answer to the title question seems to be “Not much.” Even sorting $n$ items takes $n \times \log ( n )$ swaps. But, in fact, quite a bit can be done in linear time. We start with an illustration of linear-time techniques. Then we sketch the linear-time decision algorithm for propositional primal infon logic. Finally we mention useful extensions of that logic decidable in deterministic or probabilistic linear time.

Материалы: gurevich_spb_2020_slides.pdf (262.4 Kb)

Язык доклада: английский

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020