Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Легко найти, что число обходов п городов равно М=(п-1)! / 2. Известно [30], что число 50! имеет около 65 десятичных знаков. Пусть для выбора одного варианта обхода городов и вычисления величины S по формуле (7.3) требуется to= 0,001 секунд. Оцените, каким должно быть быстродействие ЭВМ, которая переберет все варианты обхода городов задачи коммивояжера для п = 5\ за миллиард лет не­ прерывной работы. 2. Оценить время непрерывной работы ЭВМ с современными вычисли­ тельными возможностями для перебора всех указанных в задаче 1 вариантов. 3. Построить алгоритм нахождения наибольшего элемента множества S, содержащего п действительных чисел, где п - степень числа 2, на базе страте­ гии дублирования. Оценить временную сложность построенного алгоритма. 4. Построить алгоритм нахождения наименьшего элемента множества S, содержаш,его п действительных неотрицательных чисел, на базе стратегии дуб­ лирования. Оценить временную сложность построенного алгоритма. 5. Пусть А массив размера п, состояш,ий из целых чисел (положительных и отрицательных), причём Aj<A2<... <А„. Построить алгоритм нахождения числа /, для которого Ai =i (если такое i суш,ествует). Каков порядок времени работы алгоритма. 6. Построить по стратегии дублирования алгоритм умножения двух поли­ номов степени п, где n=2k, kE{l,2,3,...}, и определить вычислительную слож­ ность. 234