Лекция
Точные и FPT-алгоритмы
Страница лекции на сайте Computer Science клуба
Разложение чисел на множители
Введение: метод Ферма. Метод Крайчика. Гладкие числа. Оценка сложности метода Крайчика на базе обобщения теоремы Мертенса. Решето...
Локальная лемма Ловаса. Оценки Чернова.
Локальная лемма Ловаса. Оценки Чернова.
Колебания. Предмет теории колебаний. Классификация колебаний по кинематическим признакам. Классификация по физической природе процессов. Классификация по...
Скульптурное украшение Парфенона сохранилось до наших дней лишь частично: множество элементов пострадало из-за попытки превратить здание в христианскую церковь...
Центр масс системы. Импульс системы частиц. Связь импульса системы со скоростью центра масс. Внешние и внутренние силы. Закон изменения импульса системы....
Приближенные алгоритмы
Страница лекции на сайте Computer Science клуба
Алгоритмы расщепления
Страница лекции на сайте Computer Science клуба
Алгоритмы расщепления
Страница лекции на сайте Computer Science Club
Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–...
Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–...
Политика 70–80-х годов.
Приближенные алгоритмы
Страница лекции на сайте Computer Science клуба
Приближенные алгоритмы
Страница лекции на сайте Computer Science клуба
Конечное вероятностное пространство. Числа Рамсея. Монотонная схема для функции голосования. Теорема Эрдеша-Ко–Радо.
Центр масс системы. Импульс системы частиц. Связь импульса системы со скоростью центра масс. Внешние и внутренние силы. Закон изменения импульса системы....
Катков и Суворин.
NP-полные задачи
Страница лекции на сайте Computer Science клуба
Вероятностные алгоритмы
Страница лекции на сайте Computer Science клуба
Протоколы согласования ключа
Почвенничество и западничество.
Рекурсивный спуск для бесконтекстных грамматик, его обобщение для конъюнктивных и булевых грамматик. Достижение линейного времени выполнения. Понятие об ...
Булевы грамматики, семантика единственного решения в сильном смысле. Нормальный вид булевых грамматик. Алгоритм Кокка-Касами–Янгера в редакции для булевых...
Узкое место алгоритма Кокка–Касами–Янгера. Разбор через умножение матриц.
Лекция прочитана для студентов первого курса физического факультета СПбГУ.
Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство...
Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство...
Равносильность двух определений конъюнктивных грамматик. Приведение конъюнктивной грамматики к нормальному виду: удаление пустых конъюнктов, удаление единичных...
Языки вообще. Разбор естественных языков и языков программирования. Формальные языки и действия над ними. Понятие о регулярных выражениях и конечных автоматах.
Бесконтекстные грамматики. Примеры. Определение бесконтекстных грамматик через языковые уравнения и через перезапись. Ограничения бесконтекстных грамматик....
Лекция прочитана для первого курса Физического университета СПбГУ.
Интервал между событиями. Геометрическая интерпретация преобразований Лоренца. Четырехмерное пространство-время Минковского. Световой конус. Мировые линии....
Лекция прочитана первому курсу Физического факультета СПбГУ. На лекции кандидат исторических наук Татьяна Буркова рассказывает о становлении татаро-...
Криптография с открытым ключом II.
Криптосистемы, основанные на частных случаях NP–трудных проблем. Коды, исправляющие ошибки. Линейные коды, коды Гоппы, NP–...
Решётки в криптографии
Арифметичность вычислимых функций. Арифметическая иерархия. m–сведения. Универсальные множества. Теоремы Тарского и Геделя.
Импульс материальной точки и закон его изменения. Импульс силы. Момент импульса материальной точки. Момент силы. Закон изменения момента импульса. Сохранение...
Криптография с открытым ключом I
Теорема Успенского–Райса. Теорема о неподвижной точке. Машины Тьюринга. Предикатные формулы. Неразрешимость исчисления предикатов. Выразимость в арифметике....
Теорема Успенского–Райса. Теорема о неподвижной точке. Машины Тьюринга. Предикатные формулы. Неразрешимость исчисления предикатов. Выразимость в арифметике....
Второй закон Ньютона как основное уравнение динамики материальной точки. Понятие механического состояния. Прямая задача динамики – определение сил по...
Предмет и история криптографии. Криптографические атаки. Криптографические примитивы: хеш–функции, протоколы с секретным и открытым ключом.
Криптография с закрытым ключом
Поточные шифры: линейные сдвиговые регистры, линейная сложность функций, нелинейные сдвиговые регистры. Блочные шифры: ECB, CBC...
Вычислимые функции, разрешимые и перечислимые множества, универсальный алгоритм, перечислимое неразрешимое множество, вычислимые вещественные числа.
Обзор
Страница лекции на сайте Computer Science клуба
Обзор
Страница лекции на сайте Computer Science клуба
Классические алгоритмы интернет поиска наиболее эффективны для нахождения ключевых слов в текстовых документах. В последние годы в интернете растет доля и ...