Введение в теорию информации. Лекция 8
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
12.04.15
Дата публикации:
06.07.15
Код для блога:
Лекция 8. Приложения колмогоровской сложности.
Метод несжимаемых слов. Оценка сложности распознавания языка палиндромов на одноленточной машине Тьюринга. Теорема об иерархии для автоматов с несколькими читающими головками. Нижние оценки для схемной сложности. Сравнение вероятностного метода и метода несжимаемых слов.
Другие лекции курса
9