Математическая логика и теория алгоритмов

1. Оценить, каким должно быть быстродействие ЭВМ, которая переберет все варианты обхода городов задачи коммивояжера для « = 51 за миллиард лет непрерывной работы. 2. Оценить время непрерывной работы ЭВМ с современными вычислительными возмолсностями для перебора всех указанных в задаче 1 вариантов. 3. Построить алгоритм нахолсдения наибольшего элемента мно­ жества S, содерлсащего п действительных чисел, где п - степень числа 2, на базе стратегии дублирования. Оценить временную сложность построенного алгоритма. 4. Построить алгоритм нахождения наименьшего элемента мно­ жества S, содержащего п действительных неотрицательных чисел, на базе стратегии дублирования. Оценить временную сложность построенного алгоритма. 5. Пусть А массив размера «, состоящий из целых чисел (положительных и отрицательных), причем Ai<A2<...<A „, Построить алгоритм нахождения числа i, для которогоA i 4 (если такое i сущест­ вует). Каков порядок времени работы алгоритма? 6. Построить по стратегии дублирования алгоритм умножения двух полиномов степени п, где п=2к, fce{l,2,3,...}, и определ вычислительную сложность, 7. Доказать, что сложности умножения, деления, обращения и возведения в квадрат (М{п), D{n), R{n) и S{n)) целых двоичн размера п совпадают с точностью до постоянных множителей и имеют порядок 0(n/og2 «), если п ~ степень числа 2. 8. Доказать, что сложности умножения, деления, обращения и возведения в квадрат (М(п), D{n), R{n) и S{n)) полиномов совпадают с точностью до постоянных множителей и имеют порядок 0(nlog2 «), если п - степень числа 2.