Отступление Экспериментальное исследование эффективности алгоритмов

Нажмите для полного просмотра!

Отступление Экспериментальное исследование эффективности алгоритмов, слайд №2

Отступление Экспериментальное исследование эффективности алгоритмов, слайд №3

Отступление Экспериментальное исследование эффективности алгоритмов, слайд №4

Отступление Экспериментальное исследование эффективности алгоритмов, слайд №5

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Отступление Экспериментальное исследование эффективности алгоритмов. Доклад-сообщение содержит 5 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Построение и анализ алгоритмов Лекция 2 Отступление Экспериментальное исследование эффективности алгоритмов

Слайд 2

Описание слайда:

Некоторые соображения Генерация (для чего: в среднем, в худшем случае). Среднее по какому ансамблю? Повторяющиеся элементы? - зависит от задания… Тип, диапазон (например, 1..n)? “n!” ? (см.далее) Что измерять? Число операций, время. Как измерять? (при малых и больших значениях n), (см.код Бентли, в папке «программа»/ tm1.cpp) Контроль правильности результата… (отличие выборочных тестов от массовой генерации)

Слайд 3

Описание слайда:

Генерация случайных перестановок Для того, чтобы сгенерировать случайную перестановку можно использовать следующую индукционную схему: на i-ом шаге первые i элементов составляют равновероятную (среди всех i!) случайную перестановку: База. Один элемент является единственной случайной перестановкой из одного элемента. Предположение. Предположим, что на (i − 1)-ом шаге первые (i − 1) элементов составляют равновероятную случайную перестановку. Переход. Перейдем от (i − 1)-го шага к i-му: возьмем случайный индекс от 1 до i, поставим i-ый элемент на место этого индекса, а тот элемент, который стоял по этому индексу до операции, поставим на место номер i. Очевидно, что таким образом можно получить всевозможные перестановки первых i элементов и при этом они будут равновероятны.

Слайд 4

Описание слайда:

Исходный код процедуры перемешивания /** * Перетасовывает данные случайным образом за O(n). * * @param randseed Зерно случайного генератора */ void shuffle( intrandseed ) { sedge t; int rind; int i; /* инициализация генератора случайных чисел: */ srand( randseed ); for(i=0; i

Слайд 5

Описание слайда:

Для желающих (продвинуться) «A Theoretician's Guide to the Experimental Analysis of Algorithms» в файле «experguide.pdf». Есть также «ACM Journal on Experimental Algorithmics». (Algorithms. Data Structures . Experiments. Analysis)