Сортировка и поиск Базис. Матрица оператора. Проблема поиска в базисе. Способы сортировки

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

Содержание ▲

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

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

Слайд 1

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

1.2. Сортировка и поиск Базис. Матрица оператора. Проблема поиска в базисе. Способы сортировки

Слайд 2

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

Базис системы Вопросы поиска и сортировки возникают при численном моделировании квантовых задач при формировании базисных функций системы, а также при построении матриц операторов в выбранном базисе Система из трех ящиков и двух одинаковых шаров. Базис системы: В системе всего 6 возможных состояний

Слайд 3

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

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

Слайд 4

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

Матрица оператора Двукратное действие устройства A описывается квадратом матрицы: Таким образом, введен некоторый оператор в базисе, и построена матрица, соответствующая этому оператору В моделях сильной связи действие оператора A эквивалентно квантовому переходу частицы с одного узла пространственной решетки на другой При моделировании квантовых систем часто приходится формировать матрицы линейных операторов в базисах, состоящих из очень большого количества состояний, поэтому, если процедура поиска нужного состояния в базисе не организована эффективным образом, процесс формирования матриц может занять длительное время

Слайд 5

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

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

Слайд 6

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

Сортировка вставками Элементы неупорядоченного массива просматриваются по одному, и каждый следующий элемент вставляется в подходящее место среди ранее упорядоченных: Временные затраты при сортировке вставками составляют порядка N2 операций Этот способ сортировки является неэкономным

Слайд 7

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

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

Слайд 8

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

Сортировка обменами Два элемента меняются местами, если они расположены не по порядку, этот процесс повторяется до тех пор, пока не будут перебраны все возможные пары элементов: Временные затраты при этом способе сортировки составляют порядка N2/2 операций

Слайд 9

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

Блок-схема алгоритма сортировки обменами

Слайд 10

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

Оптимизированный метод Весь массив делится на блоки длиной Внутри каждого из кластеров проводится обычная сортировка Далее на каждом шаге выбирается минимальный элемент среди наименьших элементов каждого блока Весь алгоритм требует порядка N3/2 операций Существуют алгоритмы, доводящие время сортировки до Nlog2N операций