Задачи по прикладной математике

пример .

тогда вычисление прямого преобразования Фурье есть вычисление полинома в точках

1, , , ,.., , .

вычисление обратного преобразования Фурье основано на вычислении полинома с коэффициентами полученными на предыдущем этапе в точках обратным предыдущим

1, , , ,.., , .

и делении итогового результата на число точек.

Пример



Уточним корни прямое преобразование ,обратное преобразование проверим, что данные преобразования и их матрицы при перемножении дают единичную матрицу

.

Задача. Вычислить по схеме Горнера полином , вычислить в точка x=1, х=-1, x=2, x=i, х=-i

общий подход

Теория Быстрого преобразования Фурье - продолжение предыдущего раздела:

Вычисления преобразования Фурье с помощью схемы Горнера во всех точках займет n2 действий, что много и представляет проблему если вектор большой. при частоте 48 килогерц принятой при аудиозаписи в час мы имеем n=50 000c-1 *4000 c=200 000 000 компонент (читатель привыкший считать независимо от обстоятельств точно, наверное убеждён в НАШЕМ часе 60*60=3600 секунд, что примерно 4000). квадрат этого числа 4 1016

Быстрое преобразование Фурье позволяет вычислить за , что как минимум в миллион раз быстрее. Быстрое преобразование Фурье делается на корнях степени и интегрирует идеи быстрого возведения в степень и схемы Горнера быстрого вычисления полиномов в одной точке.

Всё основано на равенстве.

. Мы последовательно разлагаем полином на четный и нечетный. из нечетного полинома выносим x, в результате имеем два полинома от

43. Быстро отсортировать массив из 16 элементов слияниями

44. отсортировать массив из первых 6-7 элементов предыдущего массива пузырьком. Для контроля числа операций проделать каждую операцию в отдельной строке ( всего 15-25 строк).

45. Алгоритмом Анатолия Карацубы перемножить 2 8-ми значных числа. Масштабное соотношение . (Использовать формулы

… с



в этом стиле уровня рекурсии

46. Алгоритмом Штрассена перемножить 2 матрицы 4х4

.

уровня рекурсии. Операцию повторить только при (повторном) подсчете НАИБОЛЕЕ сложных в ДАННОМ Условии матриц. ,(и только их). Проверка - прямым перемножением. Презентация теория алгоритмов.

Криптография

В случае непопадания буквы в модуль или её попадания в исключения берётся первая СНАЧАЛА ПОДХОДЯЩАЯ буква ФАМИЛИИ

Все операции умножения заканчиваются взятием модуля. Для облегчения расчетов допускается использование отрицательных чисел. Возводить числа в степень больше 2 без взятия модуля запрещено. Запрещено перемножать более 2х чисел без взятия модуля.

47. (1-1,5 задач)Алгоритмом Евклида обратить , исключения

48. вычислить , где,

49. вычислить алгоритмом Евклида abc-1 mod 997 (где "abc"=100a+10b+c).

50. (~2 задачи) Алгоритмом Масси-Омуры использовав , , закодировать и раскодировать первую букву фамилии в диапазоне от 2 до 29. Если буква не подходит взять первую подходящую от начала фамилии, - сначала проверить вторую (и т.д.) Использовать (для облегчения расчёта применять ). Исключения 25 и 5(при их наступлении взять следующую букву).

Пример (Фамилия Ёжиков). Букве Ё соответствует текст 07.

Последовательно вычисляем первый шифр, (), второй шифр, , третий , и итоговое полученное сообщение .

51. В алгоритме Масси-Омуры. Можно применять модуль , с парой . Обратные вычислить алгоритмом Евклида. (для облегчения расчёта применять ). Букве И соответствует 10.

52. (~1 задача)Алгоритмом Диффи-Хелмана использовав , , закодировать и раскодировать . Использовать (для облегчения расчёта применять ). Можно применять модуль , или

53. (1 задача)Алгоритмом RSA зашифровать и расшифровать первую букву фамилии в диапазоне от 2 до 31. Исключения 11, и 22. Если буква не подходит взять первую подходящую от начала фамилии, - сначала проверить вторую (и т.д.) Исключения 11, 22 и 21 и 12. (для облегчения расчёта применять ).

54. (1-2 задачи) Имитируя алгоритм RSA (практически требуется составной модуль, мы используем простой) закодировать начальные буквы фамилии имени отчества разбить на два блока по три цифры (второй 10-ки, 1й - единицы), первый зашифровать и расшифровать. Зашифровать, возведя в 797 степень, ДЛЯ !ПРОВЕРКИ!! расшифровать, возведя в 5ю: (для облегчения расчёта применять ). Например, Иванов Иван Николаевич, ИИН>101012>002+111>шифруем Т=002. Менделеев Дмитрий Иванович

Шифруем текст Т=450.

55. Другой вариант выпотнить то же с текстом Т=100a+10b+с (где все цифры a,b и c взяты в стандартном представлении - от 1 до 9). Если результат больше 994 - аннулировать цифру a, т.е. убрать - старший разряд.

56. Алгоритм Масси-Омуры для того же блока mod997 , (mod996).

57. Алгоритм Масси-Омуры для того же блока первых букв фамилии и имени mod97 , (mod96).

58. Составить таблицу умножения по модулю , если перейти к выполнению, иначе добавить/вычесть целое число кратное 10 (как правило 10), так чтобы неравенство было выполнено (т.е. последний разряд Никогда НеМЕНЯЕТСЯ…). Найти порождающий элемент (иначе доказать его отсутствие). Для этого и перед этим построить таблицу обращения. Построить таблицу дискретного логарифма ПО ОСНОВАНИЮ ПОРОЖДАЮЩЕГО Элемента. Сделать 2-3 раза перемножения элементов (чтобы сумма оснований превосходила порядок МУЛЬТИПЛИКАТИВНОЙ Группы)

Дискретная математика.

59. Преобразовать последовательность a,b,c,d в уникальный набор неповторяющихся цифр: например , , , наборы, не имеющие повторений, сохраняются, и рассчитать следующие функции Эйлера, , , , ,

a. Какие из модулей удовлетворяют СТАНДАРТНЫМ Требованиям для применения алгоритмов Диффи-Хелмана, Масси-Омуры, RSA.

60. (в пяти вершинном исполнении -очень Дорогая задача).

a. (1+ задача) Построить хроматический полином по пустым графам и кликам для 4-хвершинного графа, пример

b. Вариант 2 Построить хроматический полином по пустым графам и кликам для стандартизованного 5-ти вершинного графа. Переводим граф СТАНДАРТНЫМ ОБРАЗОМ в пяти-рёберный: в графе есть 2 ребра. Рассматриваем позиции 1 и 3 в первой строке, 1 и 3 во второй (счёт от диагонали) позицию 2 в третьей И ЗАМЕНЯЕМ в порядке ОЧЕРЁДНОСТИ избыточные ЭЛЕМЕНТЫ на НЕДОСТАЮЩИЕ.. (Мы рассмотрели нечётные позиции при обходе над-диагонального треугольника слева-направо (номера ) и сверху вниз - РАСТРОВАЯ развёртка). МЫ ЗАМЕНИЛИ первые три НУЛЯ (нечётной под-Последовательности) на ТРИ ЕДИНИЦЫ.

c. Вариант 3 (эта часть решается по указанию преподавателя вместо части b) … для 5-ти вершинного графа, полученного из заполнения верхнетреугольной матрицы инцидентности симметричного графа двоичными записями чисел abcd (числа пишутся в каждое в свою строку так, чтобы последний разряд был в последнем столбце). (Недостаток - этой части неконтролируемый уровень сложности, что преодолено в части b, если числа проведённых и непроведённых рёбер оба равны 5.(всего может быть 10 рёбер в полном графе)).

61. Для функций , , и полученных из чисел abcd в двоичном представлении (каждое число - столбец логических значений функции). (При совпадении увеличить одно из чисел на 1, пока не исчезнет совпадение - таким образом, в любом случае будет 4 функции).

d. Выяснить отношения следствия

e. Написать СКНФ, СДНФ, СПНФ (СПНФ пишется только для первых двух функций: и ).

f. Идентифицировать данные функции, а также их отрицания (максимум 8 функций).

g. Определить какие переменные существенны для 8ми функций из предыдущего пункта

Пусть двоичная запись числа , тогда Пример

62. (в дополнение к предыдущей задаче)Классифицировать функции по всем классам Поста. Найти минимальные базисы, т.е. найти все такие наборы которые перестают быть базисными при вычеркивании каждой входящей в них функции. Например к Шефферовой функции не надо добавлять никакую (она сама базис).

63. Для функций , , и (ИКТ использует 4 функции, остальные факультеты - для краткости три) где функция :

, где двоичная запись числа , (например ) сделать то же самое:

a. Выяснить отношения следствия

b. Написать СКНФ, СДНФ, СПНФ (для двух функций: и ).

c. Рассмотрев данные функции плюс , а также их отрицания (максимум 8 функций), выяснить отношения следствия и эквивалентности

d. определить какие переменные существенны для данных функций (для существенных переменных привести пары доказывающих наборов значений лог. переменных, для не существенных отметить (выписать) пары наборов, отличающихся только значением данной переменной, с указанием общего значения функции.

e. Классифицировать функции по всем классам Поста. Найти минимальные базисы, т.е. найти все такие наборы которые перестают быть базисными при вычеркивании каждой входящей в них функции. Например к Шефферовой функции не надо добавлять никакую (она сама базис).

64. Алгебра высказываний

65. С помощью упрощения соответствующей логической формулы упростить электронную схему, получающейся ЦИКЛИЧЕСКОЙ подстановкой

a. В ЗАВИСИМОСТИ от ЗНАЧЕНИЯ по МОДУЛЮ 6:

Следует иметь ввиду ТРИВИАЛЬНЫЕ формулы на рисунке, также нетривиальную формулу (переменные могут находиться в любых «Степенях»).

Примеры:

Пример преобразований

66. (1 задача)Дан направленный граф, алгоритмом Уоршалла найти матрицу расстояний (замыкание графа)

.

Алгоритм Уоршалла-Флойда работает Матричными преобразованиями

(задача - обеспечение выполнения неравенства треугольника) , критерий прекращения процесса неизменность расстояний после применения алгоритма на очередном шаге

.

Решение примера:

Матрица после 1й итерации

,

матрица после 2-й итерации

.

Проверка показала, что 3я итерация совпадает со 2-й, поэтому алгоритм окончен.

67. (~ 1/1,5 задачи) Аналогично, алгоритмом Уоршалла решить задачу поиска кратчайших расстояний для ненаправленного графа (цепи).

Рисунок рисуется на весь лист - не менее А5.

Проверяется неравенство треугольника для каждого ребра. Если оно не выполняется, данному ре ребру приписывается новый вес как минимальный «двухзвенный» треугольный объезд по формуле . Изначальный граф может иметь любую форму. Для простоты дана форма 7-ми звенного цикла (~бензольного кольца). На первой итерации появятся стяжки инцедентных рёбер. На второй уже все не существующие рёбра (рёбра ? длины) получат варианты конечного объезда.

Далее ещё две итерации потребуется, чтобы определить кратчайшие расстояния (Последними жертвами падут несколько старых стяжек). При уменьшении значения ребра пишется - старое берётся в скобки - рядом пишется новое. Рёбра также могут быть пересмотрены.

68. Транспортная задача (тест) (в этой задаче в abcd параметрах 10-ки не откидываются!!)

a. (Tз4x4) (стоимость до 4х задач - в ИЗРЯДНОЙ зависимости от числа переходов!!, ибо возможно до 4-5ти шагов):

Условие: .

решение:

i. Исходное решение построить методом минимального элемента. Найти потенциалы,

ii. (repeat пока не достигните успеха): построить цикл пересчёта, переходя к новому решению вплоть до нахождения оптимума. (Методом потенциалов вновь и вновь проверять оптимальность - критерий оптимальности - отсутствие отрицательных ЦЕН поставок вне базисного плана после применения потенциалов на очередной итерации).

Вычислить Целевую функцию, записать в ответе значение ЦФ и оптимальный план.

(1,5/2 уз) (решается только один из всех пунктов)

69. Транспортная задача (Исследование операций, та же презентация)1

	Одесса 50(c+a)	Минск 200a	Томск 140(c+b)	Львов 80a
Мкв 180a	11a	10	60	11d
СПб 140b	6d	20c	10a	5(2a+с+d)
Ввост 190c	5a	3b	8c	14+b+c
Ростов 150a	20	5(d+c)	5(a+c+d)	5(c+1+ d)

a. Транспортная задача2(устаревший архивный вариант) (не решается как несбалансированный вариант)

Моделирование Часть1.

70. Задача повышенной сложности.

Найти оптимум в модели использования вмещающего ландшафта. Сформировать двойственную задачу.

Рассчитать цены (труда продовольствия), реальную зарплату - долю зарплаты в ВВП, указать долю доходов от Земли в ВВП.

,

где площади под поля и пастбища, соответствующая биопродуктивность и трудозатраты, - население. Территория Т, для определенности равна 50 единицам площади.

Рассмотреть ситуацию

(в предположении, что ) , (разрешается округлить до целого в большую сторону), а , .

Таким образом, получится ситуация когда . Она характерна для России. В этой ситуации цена рабочей силы отлична от 0. Доп. вопрос - рассчитать эту цену в единицах (насколько сократится население, если отвлечь 1 человека на непроизводительные работы).

Указание: чтобы задача имела решение графическим методом, ограничение рассматривать как точное равенство: вся доступная территория введена в хозяйственный оборот - . Графический метод следует применять в вертикальной полосе на плоскости этого равенства. Построить график в масштабе(т.е. с соблюдением пропорций), считая, или (на выбор).

Исследовать уравнение а)

 б)

a. Найти и построить главные изоклины

b. Отметить равновесия

c. Найти собственные вектора и собственные значения, классифицировать и изобразить фазовые портреты в окрестности равновесия, отметить устойчивые и неустойчивые.

d. Вертикальные и горизонтальные изоклины отметить соответствующей вертикальной и горизонтальной штриховкой

Указание.

Изобразить разным цветом и стилем главные изоклины

1. Приравнять все правые части 0

2. Построить изоклины

ii. Решить систему уравнений приравняв правые части к нулю - найти точки равновесия (а геометрически - это точки пересечения изоклин).

iii. Найти коэффициенты линеаризованной системы - для этого (в аналитической форма) вычислить матрицу частных производных от вектор-функции правых частей О.Д.У.

Примечание: получившаяся матрица - это матрица функций.

iv. Т.к. в точках равновесия за отсутствием постоянного слагаемого система приблизительно определяется линейной частью, вычислить записать линеаризованную систему исследовать её на тип равновесия и устойчивость в каждой из найденных точек равновесия.

v. С этой целью решив в каждой точке характеристические уравнения для матрицы системы найти собственные вектора и с. Значения. Собственные значения помогут классифицировать фазовый потрет. (а собственные вектора, в случае их нахождения, помогут уточнить основные направляющие на нём).

2. Исследовать на устойчивость

ДО

ОДУ

3. Исследовать на устойчивость при разных значениях параметра

.

4. Решить уравнение , положив указать решение для данных начальных условий. Указание разделение переменных + разложение дробей должны дать дробнолинейные функции. при интегрировании это даст (в будущем экспоненты) логарифмы

5. Для системы Чернавского найти все равновесия исследовать на устойчивость и определить тип ) . Построить портрет (использовать изоклины - см. 1е задание).

6. В модели обучения Капустина . 1)Численно найти границу областей притяжения и 2) бифуркацию слияния нижнего среднего равновесия в более общей модели

Алгоритмы. Часть 2.

Пример решения ПЕРЕМНОЖЕНИЯ 8-ми-значных чисел алгоритмом Анатолия Карацубы.

71. Создать нормальный алгоритм Маркова,

a. Распознающий Язык Дика Правильных СКОБОЧНЫХ выражений. Скобочные выражения получаются из первых 3х уникальных чисел в последовательности (если есть повтор, добавить , при 2-кратном повторе применить ТИПОВОЕ правило создание уникальной комбинации) переводом .

b. Провести операции над числами. Числа берутся в 1-ричной записи: 3=111, 7=1111111

Вычесть

Сравнить

Умножить на 3

Умножить (Универсальным алгоритмом)

Сложить (только методом перегонки * на край)

Часть универсального умножения стоит как все остальные(несколько зависит от сложности расчёта). В каждом случае нужно провести

72. (за 4 задачи)(Теорема Кука и одноименная презентация). Рассмотреть машину Тьюринга С языком a,b,c,d mod8(трехсимвольные цепочки). Свести к КНФ. Требуемая , где Указания: Переменные , s- состояния, - координата, - время ( всегда последний индекс), конкретно, ,где переменные координаты, переменные состояния зависят от ВАШЕЙ машины Тьюринга - пример для двух промежуточных состояний, переменные алфавита, .

Наиболее сложная под-коньюнкция отражает специфику машины Тьюринга, в том числе в тупиковых ситуациях (тупиковая ситуация означает невыполнение Коньюнкции). Остальные формулы базируются на конструкции типа: или - одно единственное значение истины для всех .



- аналогично,

, - контролирует неизменность символа в отсутствии Каретки, - переход в принимающее состояние.

Размещено на Allbest.ru