1).Информация (от лат. informatio — осведомление, разъяснение, изложение) —. В узком смысле этого слова — сведения (сообщения, данные) независимо от формы их представления. В настоящее время не 4 страница

23,24) Другой полезный прием можно показать на задаче поиска максимального и минимального значения в массиве. Состоит он в том, что при любом поиске в массиве искать следует не значение искомого элемента, максимума, минимума и т.п., а его индекс. Тогда решая одну задачу, мы по сути дела решаем сразу две: определяем не только наличие искомого элемента, значение максимума или минимума, но и их местоположение в массиве. Программа при этом не только не усложняется, но зачастую становится даже короче: imax:=1; imin:=1; for i:=2 to N do if a[i]<a[imin] then imin:=i else if a[i]>a[imax] then imax:=i Заметим, что использование в качестве начальных значений для минимума и максимума не значение первого элемента массива, а максимальное и минимальное значение в типе элементов, может привести к ошибке. Так, следующая программа не находит значение максимума для убывающего массива целых чисел (!!!): max:=-MaxInt-1;{это минимальное число типа integer} min:=MaxInt;{это максимальное число типа integer} for i:=1 to N do if a[i]<min then min:=a[i] else if a[i]>max then max:=I Казалось бы на этом рассмотрение алгоритмов поиска в неупорядоченном массиве можно завершить. Однако именно с одновременного поиска минимума и максимума можно начать класс алгоритмов поиска, более эффективных, чем приведенные выше стандартные алгоритмы

25) Сортировка – это процесс расстановки элементов «в некотором порядке». Элементы размещаются так, чтобы, во-первых, вычисления требующие определенного порядка расположения данных, могли выполняться эффективно, во-вторых, результаты имели осмысленный вид, в третьих, последующие процессы бы пригодные исходные данные. Внутренние методы – это такие методы, которые могут применяться с приемлемой производительностью только к тем спискам данных, которые целиком помещаются в основной (оперативной) памяти процессора Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства. Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения. Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо. Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо. Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

26) быстрая сортировка Это основной алгоритм сортировки, ибо в большинстве случаев он дает наилучшие результаты (придумал Hoare). Основная идея заключается в следующем. Выберем некий элемент M внутри диапазона, например в середине. Затем все элементы большие этого числа переносятся в одну сторону, а меньшие в другую. На практике это выглядит так: ищем первый элемент меньший (или равный) выбранного элемента M от начала диапазона, ищем первый элемент больший (или равный) выбранного элемента M от конца диапазона, меняем их местами. Продолжаем это до тех пор, пока больший элемент и меньший лежат по разные стороны. После этого вызываем алгоритм рекурсивно для двух новых диапазонов, границами которых служат последние индексы найденных меньшего и большего элементов. Пузырьковая сортировка Это самый простой и медленный способ сортировки. Также называет методом перестановок. Основная идея заколючается в том, чтобы менять местами два соседних элемента, если их расположение не удовлетворяет условию сортировки. Таким образом, за первый проход самый большой элемент будет в конце (или в начале) сортируемого множества. Дополнительно можно проверять наличие обмена элементов на каждом проходе, чтобы не делать лишние проходы. По сути быстрая сортировка является модификацией этого метода. Сортировка методом вставки Здесь основная идея в том, чтобы вставить следующий не отсортированный элемент в нужную позицию уже отсортированного диапазона. На практике это выглядит так: сортируем первые два элемента смотрим третий элемент и вставляем его в нужную позицию по отношению к первым двум Продолжаем процесс до конца сортируемого множества. Сортировка методом Шелла Это довольно трудный для понимания метод, основанный на сортировке простыми вставками (придумал Shell). Оснавная идея состоит в том, чтобы сортировать методом вставки не сразу все элементы, а по частям. Часто используется следующая последовательность. В первом проходе в сортировке участвует каждый 16 элемент, на втором проходе каждый 8, на третьем каждый 4, на втором каждый второй, и в конце обязательно проводится обычная сортировка вставками. Помимо приведенной последовательности (...,16,8,4,2,1), могут использоваться и другие последовательности. Сортировка выборкой В этом алгоритме основная идея заключается в том, чтобы на каждом проходе найти наименьший или наибольший элемент и поменять его с первым или последним не отсортированным элементом в зависимости от условия сортировки. Существуют и другие методы сортировки как пиромидальная и слиянием, однако в большинстве случаев метода быстрой сортировки вполне достаточно

27) Сортировка выбором — алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n ^2), предполагая что сравнения делаются за постоянное время. Шаги алгоритма: 1. находим минимальное значение в текущем списке 2. производим обмен этого значения со значением на первой неотсортированной позиции 3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента. Существует также двунаправленный вариант сортировки методом выбора, в котором на каждом проходе отыскиваются и устанавливаются на свои места и минимальное, и максимальное значения.

28) Простая обменная сортировка (в просторечии называемая "методом пузырька") для массива a[1], a[2],..., a[n] работает следующим образом. Начиная с конца массива сравниваются два соседних элемента (a[n] и a[n-1]). Если выполняется условие a[n-1] > a[n], то значения элементов меняются местами. Процесс продолжается для a[n-1] и a[n-2] и т.д., пока не будет произведено сравнение a[2] и a[1]. Понятно, что после этого на месте a[1] окажется элемент массива с наименьшим значением. На втором шаге процесс повторяется, но последними сравниваются a[3] и a[2]. И так далее. На последнем шаге будут сравниваться только текущие значения a[n] и a[n-1]. Понятна аналогия с пузырьком, поскольку наименьшие элементы (самые "легкие") постепенно "всплывают" к верхней границе массива.

29) Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов. Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше. Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O (n log n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы. Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два: Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат. В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки. Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью. Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим. Объём данных не позволяет им разместиться в ОЗУ. Также алгоритмы классифицируются по: потребности в дополнительной памяти или её отсутствии потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствии таковой

30)Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти: Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = | A |. Для типичного алгоритма хорошее поведение — это O (n log n) и плохое поведение — это O (n ^2). Идеальное поведение для упорядочения — O (n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в Ω(n log n) сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O (n log log n log log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О -обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O (log^2 n) операций. При этом число n должно быть заранее известно; Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O (log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O (1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

22)Эффективность метода поиска зависит от того, на сколько он быстро решает поставленную задачу, учитывает известные особенности хранения данных, а также свойства хранимой информации. Таким образом, под интеллектуальностью метода будем понимать его возможность использовать дополнительную информацию о данных. К такой дополнительной информации можно отнести следующие особенности данных, которые заранее известны: 1) как много копий в хранимых данных или сколько различных элементов; 2) искомый элемент однозначно присутствует или отсутствует в массиве; 3) особенности данных, носящие функциональный характер или свойства взаимного расположения элементов. Первая особенность данных напрямую показывает, с какой вероятностью возможно найти искомый элемент при первом же сравнении данных с ключом на равенство. Поэтому эта особенность дает информацию о том, как часто использовать операцию сравнения «равенство» (=), и ее необходимо учитывать. Вторая особенность позволяет сделать вывод о том, стоит ли вообще использовать «равенство» (=) для сравнения данных с ключом. Если элемент присутствует, то использование операции «равенства» оправдано, иначе – нет (например, для поиска места вставки (insert) уместно использовать операции «>,<,>=,<=»). Третья особенность позволяет использовать различные методы поиска, основанные на численных методах, которые учитывают функциональные зависимости между данными. Интеллектуальные методы должны использовать эту информацию для более быстрого поиска и соответственно удовлетворять следующим требованиям: − если известна дополнительная информация о данных, то интеллектуальный метод поиска должен ее учитывать; − если известна дополнительная информация об искомом элементе, то интеллектуальный метод поиска должен ее учитывать; − если нет дополнительной информации о данных и элементе, то интеллектуальный метод поиска должен это учитывать; − если есть возможность анализа данных, то интеллектуальный метод должен ее производить до его применения поиска. Все необходимые действия для поиска очень сходны с интеллектуальной деятельностью человека, так как перед тем, как что-либо искать, он анализирует предмет поиска, хранимые данные и их свойства. Поэтому методы поиска, обладающие сходными свойствами с методами поиска человека, можно называть интеллектуальными, или с элементами интеллекта. К таковым возможно отнесение методов поиска, которые используют стратегию поиска, сходную со стратегией человека, основанную на анализе размера массива: − если размер массива достаточно велик, то уместно делать проверку на отсутствие ключа в массиве; − если размер средний, возможно присутствие копий, то элемент, скорее присутствует в массиве и проверку на отсутствие элемента следует убрать, а добавить проверку на совпадение с ключом; − если размер массива мал, то просто просмотрим все элементы для поиска ключа. Методы поиска должны быть достаточно адаптивны к требованиям интеллектуальности, то есть в интеллектуальном методе должна быть возможность легко добавить еще какой-либо метод, который лучше работает c массивом определенного размера.

Дата добавления: 2015-09-28