3. Класс NP-полных задач в области теории графов. Задача коммивояжёра. (коммивояжёр — бродячий торговец) заключается в отыскании самого
выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим
возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший,
самый дешёвый, совокупный критерий и т.п.) и соответствующие матрицы расстояний, стоимости и т.п.
Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
Существует масса разновидностей обобщённой постановки задачи, в частности геометрическая задача коммивояжёра (когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра.
---------------------------------------------
4. Судоку.
Судоку - это головоломка-пазл с числами, ставшая в последнее время очень популярной. В переводе с японского <<су>> - <<цифра>>, <<доку>> — <<стоящая отдельно>>. Иногда судоку называют <<магическим квадратом>>, что в общем-то не верно, так как судоку является латинским квадратом 9-го порядка.
У судоку есть всего одно правило. Необходимо заполнить свободные клетки цифрами от 1 до 9 так,
чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3x3 каждая цифра встречалась бы только один раз. От того, сколько клеток уже заполнено, зависит сложность игры. Некоторые головоломки можно решить за несколько минут, на другие можно потратить часы.
Правильно составленная головоломка имеет только одно решение. Неизвестно минимальное количество изначально заполненных клеток в игре судоку, при котором существует единственное решение.
5. Последовательность жонглёра.
Последовательность жонглёра - целочисленная последовательность, которая начинается положительным целым числом [math]a_0[/math] и каждое следующее определяется рекуррентным соотношением
$a_{k+1} = [a_k^{\frac{1}{2}}]$, $a_k \in {\rm\bf Z}_2$;
$a_{k+1} = [a_k^{\frac{3}{2}}]$, $a_k \notin {\rm\bf Z}_2$.
Название происходит от возрастания и убывания последовательности, как шариков в руках жонглера.
Если какое-нибудь $a_k$ принимает значение 1, то все последующие также равны единице. Гипотеза жонглёра состоит в том, что любая последовательность жонглёра достигает 1.
Последовательности жонглёра могут достигать очень больших значений до убыванию 1. Например,
последовательность жонглёра, начиная $c_0 = 37$ достигает максимального значения 24 906 114 455 136. Установлено, что последовательность жонглёра, начиная $c_0 = 48443$ достигает максимального значения на $c_{60}$ с 972463 цифрами и опускается до 1 на $c_{157}$.
