Разделы презентаций


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

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

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

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

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

Слайд 2Базис системы
Вопросы поиска и сортировки возникают при численном моделировании квантовых

задач при формировании базисных функций системы, а также при построении

матриц операторов в выбранном базисе
Система из трех ящиков и двух одинаковых шаров. Базис системы:







В системе всего 6 возможных состояний

















Базис системыВопросы поиска и сортировки возникают при численном моделировании квантовых задач при формировании базисных функций системы, а

Слайд 3Матрица оператора
Неразличимые шары:



Пусть есть некоторое устройство A, которое перекладывает один

шар из третьего ящика во второй:


Матрица, отражающая работу этого

устройства:





















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

Слайд 4Матрица оператора
Двукратное действие устройства A описывается квадратом матрицы:




Таким образом, введен

некоторый оператор в базисе, и построена матрица, соответствующая этому оператору
В

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























Матрица оператораДвукратное действие устройства A описывается квадратом матрицы:Таким образом, введен некоторый оператор в базисе, и построена матрица,

Слайд 5Упорядоченный базис
Процедура поиска нужного состояния будет эффективной и быстрой лишь

в том случае, если состояния, входящие в базис, пронумерованы в

соответствии с определенной схемой:







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
























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

Слайд 6Сортировка вставками
Элементы неупорядоченного массива просматриваются по одному, и каждый следующий

элемент вставляется в подходящее место среди ранее упорядоченных:






Временные затраты при

сортировке вставками составляют порядка N2 операций
Этот способ сортировки является неэкономным

























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

Слайд 7Сортировка выбором
Сначала из неупорядоченного массива выбирается наименьший (или наибольший) элемент

и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший)

элемент из оставшихся и т.д.:







Как и метод вставок, этот способ сортировки требует порядка N2 операций


























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

Слайд 8Сортировка обменами
Два элемента меняются местами, если они расположены не по

порядку, этот процесс повторяется до тех пор, пока не будут

перебраны все возможные пары элементов:








Временные затраты при этом способе сортировки составляют порядка N2/2 операций



























Сортировка обменамиДва элемента меняются местами, если они расположены не по порядку, этот процесс повторяется до тех пор,

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



























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

Слайд 10Оптимизированный метод
Весь массив делится на блоки длиной


Внутри каждого из кластеров

проводится обычная сортировка

Далее на каждом шаге выбирается минимальный элемент среди

наименьших элементов каждого блока

Весь алгоритм требует порядка N3/2 операций
Существуют алгоритмы, доводящие время сортировки до Nlog2N операций































Оптимизированный методВесь массив делится на блоки длинойВнутри каждого из кластеров проводится обычная сортировкаДалее на каждом шаге выбирается

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика