Книга: Золотой билет
На Востоке
В СССР проблемами теоретической кибернетики занимались многие выдающиеся ученые. Мы подробно остановимся на трех из них; все они являются представителями различных подходов к методу перебора.
1. Сергей Всеволодович Яблонский первым применил перебор для поиска минимальных схем, реализующих дискретные функции. К сожалению, его самонадеянность в сочетании с огромным влиянием, которое он приобрел в научной среде, тормозили развитие теории вычислительной сложности.
2. Андрей Николаевич Колмогоров – крупнейший ученый в истории русской науки – предложил в качестве меры сложности алгоритмическую информацию.
3. Ученик Колмогорова Леонид Анатольевич Левин независимо от Кука сформулировал проблему равенства классов P и NP и пришел к понятию NP-полноты. На родине защитить диссертацию он не смог по политическим причинам.
- Глава 5. Хроника предшествующих событий
- Путешествия по малоизвестным маршрутам
- Первый звук
- Правило марсианина
- Листинг 8.2. Общий код, используемый во всех приведенных ниже вариантах тестов
- Что вы узнаете
- Пример 4-7. Использование команды shift
- Технологии
- Листинг 8.1. Применение отложенной загрузки, кэширования и освобождения графических ресурсов
- A7.6. Мультипликативные операторы
- 9.5. Инженерия разработки программного продукта