Презентация на тему: Место и значение алгоритмов в вычислительных задачах

13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7
Рис. 4.1. Информация о цене акций Volatile Chemical Corporation после закрытия торгов за 17-дневный период. На горизонтальной оси диаграммы указан день торгов, на вертикальной — цена. В нижней строке таблицы указано изменение цены по сравнению с предыдущим днем.

Можно решить, что прибыль всегда можно максимизировать, либо покупая по наименьшей цене, либо продавая по наибольшей. Например, на рис. 4.1 мож­но было бы максимизировать прибыль, выполняя покупку по наименьшей цене, которая достигается после торгов седьмого дня. Если бы такая стратегия всегда работала, то было бы просто определить, как максимизировать прибыль: най­ти наибольшую и наименьшую цены, а затем слева от наивысшей цены выпол­нить поиск наинизшей, а справа от наинизшей цены выполнить поиск наивыс­шей и взять пару с максимальным отличием. Но на рис. 4.2 показан контрпример, демонстрирующий, что иногда максимальная прибыль достигается и не при по­купке по наинизшей цене, и не при продаже по наивысшей

• Можно решить, что прибыль всегда можно максимизировать, либо покупая по наименьшей цене, либо продавая по наибольшей. Например, на рис. 4.1 мож­но было бы максимизировать прибыль, выполняя покупку по наименьшей цене, которая достигается после торгов седьмого дня. Если бы такая стратегия всегда работала, то было бы просто определить, как максимизировать прибыль: най­ти наибольшую и наименьшую цены, а затем слева от наивысшей цены выпол­нить поиск наинизшей, а справа от наинизшей цены выполнить поиск наивыс­шей и взять пару с максимальным отличием. Но на рис. 4.2 показан контрпример, демонстрирующий, что иногда максимальная прибыль достигается и не при по­купке по наинизшей цене, и не при продаже по наивысшей

Алгоритм Штрассена для умножения матриц

• В отличие от традиционного алгоритма умножения матриц (по формуле ), работающего за время , алгоритм Штрассена умножает матрицы за время , что даёт выигрыш на больших плотных матрицах начиная, примерно, от 64×64.
• Несмотря на то, что алгоритм Штрассена является асимптотически не самым быстрым из существующих алгоритмов быстрого умножения матриц, он проще программируется и эффективнее при умножении матриц относительно малого размера, поэтому именно он чаще используется на практике.