Предположим, вы встречаетесь с программистами, которые прошли некоторые профессиональные курсы по программированию (или думали сами), но не изучали математику университетского уровня.
Чтобы показать им всю прелесть TCS, я хотел бы собрать некоторые хорошие результаты / открытые вопросы, поступающие от TCS, которые легко объяснить.
Хороший кандидат для этой цели (ИМХО) покажет, что проблема остановки не решаема. Другой будет показывать нижнюю границу времени сортировки на основе сравнения (хотя это немного отталкивает от того, что, как я ожидаю, они поймут).
Я также могу использовать идеи из объяснения проблемы P = NP для 10-летних , предполагая, что некоторые из них не знакомы с ней.
Итак, вопросы должны быть:
(0. Красиво)
- Объясняется с (максимум) математикой средней школы.
- (желательно) не достаточно тривиально для показа на курсах профессионального программирования (для C ++ / Java / Web / и т. д.).
Ответы:
В дополнение к проблеме остановки, я предлагаю обсудить:
Теорема Райса. Некоторые объяснения в Википедии немного жаргонны, но, как правило, это не сложная теорема или доказательство, чтобы понять что-то другое; он имеет большое значение для реальных концепций, таких как антивирусное программное обеспечение. Доказательство примерно такое же сложное, как и доказательство проблемы остановки (и фактически зависит от неразрешимости проблемы остановки). По сути, просто поймите, что «вычислимая функция» - это машина Тьюринга или компьютерная программа.
источник
Я думаю, что - независимо от вопроса P против NP - теорема Кука-Левина (и связанное с ней понятие NP-полноты) является еще одним очень хорошим кандидатом; если у вас есть (эффективный) решатель для SAT, то у вас есть (эффективный) решатель для любой проблемы в NP .... и вы можете получить нечто удивительное, по крайней мере для меня:
в некотором смысле "эквивалентные проблемы"; так что если ваш босс попросит вас создать программу для упаковки коробок в контейнер ... вы можете дать ему решатель Сапер ... :-)
источник
Забавный и интересный пример - неразрешимость проблемы тайлов тайлов Ванга. Результат непосредственно следует из неразрешимости проблемы Остановки простым моделированием машин Тьюринга с использованием плиток Ванга. Интересно, что неразрешимость проблемы листов для плиток Ванга привела к прекрасному результату, что есть наборы плиток, которые разбивают плоскость только на апериодику.
Ван предположил, что каждый набор плиток, которые располагаются на плоскости, должен иметь периодическое разбиение. Таким образом, гипотеза подразумевает, что проблема листов решаема. Позже Бургер доказал неразрешимость проблемы листов, которая подразумевала существование наборов плиток, которые покрывают плоскость только апериодически.
источник
избранное, собранное здесь и в другом месте
криптографии с открытым ключом / алгоритм RSA , люк функция , Shannons считая аргумент , показывающее большинство функций цепи трудно ; повторяю эту тайну:
AKS Primality тестирование в P , относительно недавний прорыв TCS легко сообщается
P против NP . Один элементарный способ связать функции NP через игры, например, линейный корабль или soduku, с NP полными обобщениями. также см., например, книгу Fortnows . см. также видеоигры как NP завершено
неразрешимость проблемы почтовой корреспонденции
Преобразование цепи Цейтина и SAT (повторные сокращения и полнота NP)
(древний) евклидов алгоритм и наихудший анализ связи с последовательностью Фибоначчи
Соответствие Карри-Говарда между доказательствами и программами . Я не видел элементарной ссылки на это, но в глубине души идея довольно проста и общительна
Четыре цвета через автоматическое доказательство , прорыв для TCS
источник