Длинные конечно, но выбрать нужное можно!!!
| Вид материала | Программа |
- Межрегионального Маркетингового Центра «Владимир-Москва» было проведено исследование, 69.27kb.
- 9. Православное учение о человеке, 3218.12kb.
- 9. Православное учение о человеке, 6232.66kb.
- Коммерческий акт №, 22.66kb.
- Как выбрать санки. , 126.61kb.
- Самостоятельная работа Философская концепция мыслителя (2004) Самостоятельная работа, 784.22kb.
- Самостоятельная работа 10. Философская концепция мыслителя Эта самостоятельная работа, 807.98kb.
- Цели и задачи логистики, 43.75kb.
- Игра по литературе «Эрудит» (11 класс), 137.84kb.
- 9. Упрощенная система налогообложения, 98.06kb.
1 2
Длинные конечно, но выбрать нужное можно!!!
1. Что называется алгоритмом?
Слово «алг-м» происходит от имени великого восточного математика аль-Хорезми, кот в 19 в. сформулировал правила вып-я 4-х ариф-х действий. Сейчас под алгор-ом понимают точн предписание, опр-щее процесс достижения поставленной цели. Алг-м м представлять собой некот послед-ть вычисл-й, а может-послед-ть действий нематем хар-ра. Но в люб случае д.б. четко опр-ны начальн усл-я и то, что треб-ся получить. Алгоритм-это некот конечн послед-ть точн предписаний (правил), однозначно определяющая процесс преобраз-я исход-х и промежут-х рез-в в конечн рез-т при реш-и всех задач данного типа.
2. Что называется программой?
Программа - последовательность машинных команд, предназначенная для достижения конкретного результата
Программа, работающая на компьютере, нередко отождествляется с самим компьютером, т. к. человек, использующий программу, "вводит в компьютер" исходные данные, как правило, при помощи клавиатуры, а компьютер "выдает результат" на экран, на принтер или в файл. На самом деле, преобразование исходных данных в результат выполняет процессор компьютера. Процессор преобразует исходные данные в результат по определенному алгоритму, который, будучи записан на специальном языке, называется программой. Таким образом, чтобы компьютер выполнил некоторую работу, необходимо разработать последовательность команд, обеспечивающую выполнение этой работы, или, как говорят, написать программу.
3. Какие типы ошибок может содержать программа? Приведите примеры.
Ошибки, которые могут быть в программе, принято делить на три группы:
-синтаксические;
-ошибки времени выполнения;
-алгоритмические.
Синтаксические ошибки, их также называют ошибками времени компиляции (Compile-time error), наиболее легко устранимы. Их обнаруживает компилятор, а программисту остается только внести изменения в текст программы и выполнить повторную компиляцию. Ошибки времени выполнения, обычно проявляются уже при первых запусках программы и во время тестирования. С алгоритмическими ошибками дело обстоит иначе. Компиляция программы, в которой есть алгоритмическая ошибка, завершается успешно. При пробных запусках программа ведет себя нормально, однако при анализе результата выясняется, что он неверный. Для того чтобы устранить алгоритмическую ошибку," приходится анализировать алгоритм, вручную "прокручивать" его выполнение.
Ошибки ввода-вывода
Если один из операторов компилировался с директивой {$I+}, то ошибка ввода-вывода приводит к прекращению выполнения программы. В состоянии {$I-} программа продолжает выполняться, а ошибка возвращается функцией IORESULT.
100 Disk read error Ошибка чтения с диска
101 Disk write error Ошибка записи на диск
103 File not open Файл не открыт
Критические ошибки
150 Disk is write protected (Диск защищен от записи).
152 Drive not ready (Дисковод находится в состоянии «не готов»).
153 Unknown command (Неопознанная команда).
157 Unknown media type (Неизвестный тип носителя).
160 Device write fault (Ошибка при записи на устройство).
Сообщения об ошибках вовремя выполнения программы
Ошибки, ввода - вывода Эти ошибки контролировать с помощью директивы компилятора I и функции IOresult.
Ошибки ввода - вывода системные
2. File not found – Фaйл нe нaйдeн.
5. File access denied - Heвoзмoжeн дocтуп к фaйлу.
16. Cannot remove current directory - Нельзя удалить текущий каталог.
Ошибки ввода - вывода программные
100. Disk read error - Oшибкa чтeния диска: попытка чтения по концу файла.
104. File not Open for input - Файл не открыт для ввода.
Критические ошибки ввода - вывода
150. Disk is write - protected - Диск защищен от записи.
151. Bad drive request struct length - Неисправно устройство.
Фатальные ошибки Эти ошибки всегда приводят к немедленной остановке программы.
200. Division by zero - Деление на нуль.
202. Stack overflow error - переполнение стека.
4. Какой процесс называется тестированием программы
Успешное завершение процесса компиляции не означает, что в программе нет ошибок. Убедиться, что программа работает правильно можно только в процессе проверки ее работоспособности, который называется тестирование.
5. Какой процесс называется отладкой программы? В чем заключается отладка программы?
Осн задачей прогр-ния яв-ся созд-е правильн прог-м. Ошибки в прогр-х допускают все – как начинающие, так и опытн прог-ты. Причем следует иметь в виду, что в слож прогр-х некот ошибки могут обнаруживать себя после довольно длительн эксплуатации. При созд-и прогр-ы необх предусм-ть меры по обнаруж-ю и устранению возм-х ошибок. Процесс поиска ошибок в прогр-е наз тестированием, выявление причин ошибок и их устранение – отладкой. Обнаружив ошибку, необх ее исправить, для чего треб-ся выяснить причину этой ошибки. Сущ-ет неск-о различ методов отладки. Выбор того или иного метода завис от особен-ей ошибки и от ривычек прогр-та. Как правило, все же приход-ся польз-ся мовокуп-ю методов: 1. Проверка за столом. Он закл в том, что прог-т сам просматривает прогр-у, анализ-ет ее логич ветви и по рез-м контр примера, приведшего к ошибке, пытается обнаружить причину ошибки. Этот метод хорош тем, что помогает прогр-ту еще раз вникнуть в работу прогр-ы, детально разоб-ся в ее особен-х. К сожал, в слож прогр-х он бывает малоэф-ен из-за наличия больш кол-ва деталей, кот трудно охватить целиком. Поэтому бывает весьма полезно локализовать ошибку. 2. Трассировка. Она основана на использ-и отладочной печати, помещаемой в ключев точки прогр-ы. Отладочн печать позвол проследить ход выпол-я прогр-ы и сузить границы поиска причины ошибки. Трассировку м проводить в неск-о этапов, учащая отладочн печать во вновь получен обл-ти ошибки, тем самым поэтапно сужая границы поиска. Этот процесс м производить до тех пор, пока проверка за столом не окажется достаточно эффек-ой. В процессе исправл-я ошибки м.б. допущены новые. Поэтому после кажд исправл-я треб-ся вновь произ-ти тестир-е.
6. Какие инструментальные средства поддерживают процесс отладки программы?
Процесс поиска и устранение ошибок называется отладкой. Нарушение в работе программы называется исключением. Обработку исключений (ошибок) берет на себя автоматически добавляемый в выполняемую программу код, который обеспечивает, в том числе, вывод информационного сообщения. Вместе с тем Delphi дает возможность программе самой выполнить обработку исключения.
Инструкция обработки исключения в общем виде выглядит так:
try // здесь инструкции, выполнение которых может вызвать исключение
except // начало секции обработки исключений
on ТипИсключения1 do Обработка1;
on ТипИсключения2 do Обработка2;
on ТипИсключенияJ do ОбработкаJ;
else // здесь инструкции обработки остальных исключений
end;
где: try — ключевое слово, обозначающее, что далее следуют инструкции, при выполнении которых возможно возникновение исключений, и что обработку этих исключений берет на себя программа;
except — ключевое слово, обозначающее начало секции обработки исключений. Инструкции этой секции будут выполнены, если в программе возникнет ошибка;
on — ключевое слово, за которым следует тип исключения, обработку которого выполняет инструкция, следующая за do;
else — ключевое слово, за которым следуют инструкции, обеспечивающие обработку исключений, тип которых не указаны в секции except.
7. Что такое проект в терминах Delphi?
Проект в терминах Delphi – это совокупность программных модулей и ресурсов, представленных в виде текстовых и бинарных файлов, в результате компиляции и компоновки которых будет получен исполняемый модуль (.exe-файл) или библиотека (.dll, .bpl, .ocx-файл).
Работа над новым проектом, так в Delphi называется разрабатываемое приложение, начинается с создания стартовой формы. Так на этапе разработки программы называют диалоговые окна.
Стартовая форма создается путем изменения значений свойств формы Form1 и добавления к форме необходимых компонентов (полей ввода и вывода текста, командных кнопок).
Проект Delphi представляет собой набор программных единиц — модулей. Один из модулей — главный, содержит инструкции, с которых начинается выполнение программы. Главный модуль приложения полностью формируется Delphi. Главный модуль представляет собой файл с расширением dpr.
Проект — это набор файлов, используя которые компилятор создает исполняемый файл программы (ЕХЕ-файл). В простейшем случае проект состоит из файла описания проекта (DOF-файл), файла главного модуля (DPR-файл), файла ресурсов (RES-файл), файла описания формы (DFM-файл), файла модуля формы, в котором находятся основной код приложения, в том числе функции обработки событий на компонентах формы (PAS-файл), файл конфигурации (CFG-файл).
8. Какие существует базовые алгоритмические конструкции? Почему они называются базовыми?
Под алгоритмом понимают постоянное и точное предписание (указание) исполнителю совершить определенную последовательность действий, направленных на достижение указанной цели или решение поставленной задачи.
Блок – схемы. Условные обозначения
Начало - конец
Ввод-вывод
Процесс
Типовой процесс
Решение (условие)
Базовые алгоритмические структуры
Следование Ветвление Повторение (цикл)
Следование (линейный тип алгоритма) Все команды алгоритма следуют друг за другом.
Ветвление (условный тип алгоритма) Выбор действия зависит выполнения некоторого от условия. Условие - выражение, которое может принимать значение "истина" либо "ложь".
Повторение (циклический тип алгоритма) В алгоритме есть повторяющиеся действия.
Любой алгоритм основывается на этих структурах, поэтому они называются базовыми.
9. Какой алгоритм называется линейным? Приведите два примера
использования линейных алгоритмов.
Линейным называется алгоритм, в котором все этапы решения задачи выполняются строго последовательно один за другим. Такие алгоритмы применяются в случаях, когда необходимо выполнить обработку данных, возможно в несколько этапов, причем каждый этап выполняется строго один раз. В качестве примера применения линейного алгоритма рассмотрим задачу вычисления корней линейного уравнения ax + b = 0. Представим этот алгоритм в виде словесно-формульного описания (математической модели задачи).
Решение линейного уравнения.
Входные данные: a, b – коэффициенты уравнения
Выходные данные: x – корень уравнения
- Вычитаем из правой и левой частей уравнения значение –b:
ax + b – b = 0 – b;
ax = – b;
- Разделим обе части уравнения на значение a:
ax / a = – b / a;
x = – b / a.
Таким образом, для решения поставленной задачи необходим алгоритм из двух шагов (первый шаг – вычитание, второй шаг – деление), причем действия на каждом шаге выполняются ровно один раз.
На блок-схемах линейный алгоритм отображается в виде последовательно расположенных вертикально или горизонтально блоков «процесс» и «предопределенный процесс», соединенных линиями потока управления.
Представим алгоритм решения линейного уравнения в виде блок-схемы.
В нашем примере два шага алгоритма в словесно-формульном описании на блок схеме представлены одним блоком «процесс».
В программном коде линейный алгоритм представляется в виде последовательности операторов, записанных друг за другом. Никакие специальные ключевые слова и синтаксические конструкции языка программирования для представления линейного алгоритма не используются. Представим алгоритм решения линейного уравнения в виде программы на языке Object Pascal.
10. Какой алгоритм называется ветвящимся? Приведите два примера использования ветвящихся алгоритмов.
Выбор в точке разветвления алгоритма очередного шага программы может быть реализован при помощи инструкций if и case. Инструкция if позволяет выбрать один из двух возможных вариантов, инструкция case — один из нескольких.
Инструкция if
Инструкция if позволяет выбрать один из двух возможных вариантов развития программы. Выбор осуществляется в зависимости от выполнения условия.
В общем виде инструкция if записывается так:
if условие then
begin // здесь инструкции, которые надо выполнить, если условие истинно.
end
else
begin // здесь инструкции, которые надо выполнить, // если условие ложно. end;
Обратите внимание, что перед else (после end) точка с запятой не ставится.
Выполняется инструкция if следующим образом:
1. Вычисляется значение условия (условие — выражение логического типа, значение которого может быть равно True или False).
2. Если условие истинно (значение выражения условие равно True), то выполняются инструкции, следующие за словом then (между begin и end). На этом выполнение операции if заканчивается, то есть инструкции, следующие за else, не будут выполнены.
Если условие ложно (значение выражения условие равно False), то выполняются инструкции, следующие за словом else (между begin и end).
Инструкция case
В предыдущем примере, в программе контроля веса, множественный выбор был реализован при помощи вложенных одна в другую инструкций if. Такой подход не всегда удобен, особенно в том случае, если количество вариантов хода программы велико.
В языке Delphi есть инструкция case, которая позволяет эффективно реализовать множественный выбор. В общем виде она записывается следующим образом:
case Селектор of список1:
begin
{ инструкции 1 } end; список2:
begin
{ инструкции 2 } end; списокМ:
begin
{ инструкции N }
end;
else
begin
{ инструкции )
end;
end;
где: Селектор — выражение, значение которого определяет дальнейший ход выполнения программы (т. е. последовательность инструкций, которая будет выполнена);
Список N — список констант. Если константы представляют собой диапазон чисел, то вместо списка можно указать первую и последнюю константу диапазона, разделив их двумя точками. Например, список 1, 2, 3, 4, 5, 6 может быть заменен диапазоном 1..6.
Выполняется инструкция case следующим образом:
1. Сначала вычисляется значение выражения-селектора.
2. Значение выражения-селектора последовательно сравнивается с константами из списков констант.
3. Если значение выражения совпадает с константой из списка, то выполняется соответствующая этому списку группа инструкций. На этом выполнение инструкции саsе завершается.
4. Если значение выражения-селектора не совпадает ни с одной константой из всех списков, то выполняется последовательность инструкций, следующая за else.
Синтаксис инструкции case позволяет не писать else и соответствующую последовательность инструкций. В этом случае, если значение выражения не совпадает ни с одной константой из всех списков, то выполняется следующая за case инструкция программы.
11. Какой алгоритм называется циклическим? Какие существуют виды циклических алгоритмов? Приведите примеры использования каждого типа циклических алгоритмов.
Алгоритмы решения многих задач являются циклическими, т. е. для достижения результата определенная последовательность действий должна быть выполнена несколько раз. Например, программа контроля знаний выводит вопрос, принимает ответ, добавляет оценку за ответ к сумме баллов, затем повторяет это действие еще и еще раз, и так до тех пор, пока испытуемый не ответит на все вопросы.
Другой пример. Для того чтобы найти фамилию человека в списке, надо проверить первую фамилию списка, затем вторую, третью и т. д. до тех пор, пока не будет найдена нужная фамилия или не будет достигнут конец списка. Алгоритм, в котором есть последовательность операций (группа инструкций), которая должна быть выполнена несколько раз, называется циклическим, а сама последовательность операций именуется циклом.
В программе цикл может быть реализован при помощи инструкций for,while и repeat.
Инструкция for используется в том случае, если некоторую последовательность действий (инструкций программы) надо выполнить несколько раз, причем число повторений заранее известно.
Инструкция while Инструкция (цикл) while используется в том случае, если некоторую последовательность действий (инструкций программы) надо выполнить несколько раз, причем необходимое число повторений во время разработки программы неизвестно и может быть определено только во время работы программы. Типичными примерами использования цикла while являются вычисления с заданной точностью, поиск в массиве или в файле.
В общем виде инструкция while записывается следующим образом: while условие do begin
Инструкция repeat Инструкция repeat, как и инструкция while, используется в программе в том случае, если необходимо выполнить повторные вычисления (организовать цикл), но число повторений во время разработки программы неизвестно и может быть определено только во время работы программы, т. е. определяется ходом вычислений.
12. Что такое контейнер данных? Какие свойства контейнера Вы знаете?
Контейнер данных (абстрактный контейнер, далее просто "контейнер") - составной объект данных, т. е. объект данных, состоящий из нескольких вложенных в него объектов данных. Рассуждая от противного, можно также сказать, что объект данных является вырожденным случаем контейнера, содержащего только один объект.
Контейнеры во многом походят на блоки в универсальный языках программирования. При этом свойства контейнеров можно интерпретировать как переменные, которые принимают определенные значения в пределах каждого из контейнеров. Как и в языках программирования, например в Паскаль, описание свойств можно вынести в специальную секцию данных в начале документа. Такой секцией и является секция описания каскадных стилей. Обычно стиль описывается внутри контейнера STYLE.
13. Какие существуют операции над контейнерами? Приведите примеры использования для каждой операции.
Над контейнерами определены следующие операции:
INSERT. Вставка элемента в контейнер, операция добавляет элемент в контейнер в указанную позицию, увеличивая размер контейнера на единицу. Эта операция имеет смысл только для динамических контейнеров;
REMOVE. Удаление элемента из контейнера, операция удаляет указанный элемент из контейнера, уменьшая размер контейнера на единицу. Эта операция также имеет смысл только для динамических контейнеров;
AT. Получение доступа к элементу, хранящемуся в контейнере, то есть получение и изменение значение элемента. Операция определена для любых контейнеров;
EMPTY. Проверка контейнера на пустоту. Контейнер считается пустым, если он не содержит ни одного элемента, то есть его размер равен нулю.
SIZE. Получение текущего размера контейнера.
Считается, что контейнер является владельцем (owner) хранящихся в нем элементов. Это означает, что область памяти, занимаемая элементом контейнера, принадлежит контейнеру и будет выделена при добавлении элемента, а освобождена – при удалении элемента.
14. Что такое массив? Какие виды массивов Вы знаете? В каких случаях в программах используются массивы?
Массив — это структура данных, представляющая собой набор переменных одинакового типа, имеющих общее имя. Массивы удобно использовать для хранения однородной по своей природе информации, например, таблиц и списков. (одномерные и многомерные)
Различают массивы статические и динамические. Статический массив представляет собой массив, границы индексов и соответственно размеры которого задаются при объявлении — известны до компиляции программы. Формат описания типа статического массива:
Array [Тип индексов] of <Тип элементов>;
Пример. Объявление статических массивов.
Type tm = Arraytl .. 10, 1 .. 100] of real;
Var arrl, arr2: tm;
arr3: Array[20 .. 100] of char;
arr4: Array['a' .. 'z'] of integer;
Переменные arrl и arr2 являются двумерными массивами по юоо элементов — ю строк и юо столбцов. Каждый элемент этих массивов представляет собой число типа real. Для объявления массивов arrl и агг2 введен специальный тип tm. Переменные аггз и агг4 являются одномерными массивами соответственно на 81 символ и 26 целых чисел.
15. Какие операции над контейнерами поддерживаются языком Object Pascal непосредственно? Какие операции необходимо реализовывать отдельно?////////////
Контейнером данных (англ. data container) называют некоторую сущность (абстракцию), предназначенную для хранения однотипных данных, называемых элементами контейнера (element).
Над контейнерами определены следующие операции:
- INSERT. Вставка элемента в контейнер, операция добавляет элемент в контейнер в указанную позицию, увеличивая размер контейнера на единицу. Эта операция имеет смысл только для динамических контейнеров;
- REMOVE. Удаление элемента из контейнера, операция удаляет указанный элемент из контейнера, уменьшая размер контейнера на единицу. Эта операция также имеет смысл только для динамических контейнеров;
- AT. Получение доступа к элементу, хранящемуся в контейнере, то есть получение и изменение значение элемента. Операция определена для любых контейнеров;
- EMPTY. Проверка контейнера на пустоту. Контейнер считается пустым, если он не содержит ни одного элемента, то есть его размер равен нулю.
- SIZE. Получение текущего размера контейнера.
Считается, что контейнер является владельцем (owner) хранящихся в нем элементов. Это означает, что область памяти, занимаемая элементом контейнера, принадлежит контейнеру и будет выделена при добавлении элемента, а освобождена – при удалении элемента.
Простейшим контейнером данных является массив. Массивом (array) называется контейнер данных, для которого выполняются следующие условия:элементы хранятся последовательно, в порядке их добавления;размер используемой дополнительной памяти обычно равен нулю;каждый элемент массива имеет индекс, фактически порядковый номер;и т.д.
Язык программирования Object Pascal имеет встроенную поддержку массивов. Это означает, что язык непосредственно содержит набор синтаксических конструкций, позволяющих объявлять переменные типа массива и выполнять некоторые операции над такими переменными. Object Pascal поддерживает как статические массивы (фиксированные контейнеры), так и динамические массивы (динамические контейнеры).
---*-----16. Какую временную сложность имеют операции INSERT, REMOVE, AT для массивов?
Время, необходимое для вставки записи, можно грубо разделить на такие промежутки:
Подсоединение, Посылка запроса на сервер, синтаксический анализ запроса, Вставка записи, Вставка индексов, Закрытие. При этом не учитывается время в начале вставки, требующееся для открытия таблиц (таблицы открываются один раз для каждого конкурентно выполняющегося запроса).
Некоторые способы ускорения вставки:
Если с одного клиента одновременно вставляется большое количество строк, используйте операторы INSERT в форме, содержащей множество записей. При этом вставка будет происходить намного быстрее (в некоторых случаях в несколько раз), чем при использовании отдельных операторов INSERT. При добавлении данных в непустую таблицу можно настроить переменную myisam_bulk_insert_tree_size так, чтобы это делалось еще быстрее. См. раздел SHOW VARIABLES.
При вставке нескольких строк с различных клиентов можно повысить скорость, используя оператор INSERT DELAYED. См. раздел Синтаксис оператора INSERT.
Обратите внимание: при использовании таблиц MyISAM можно вставлять строки во время выполнения операторов SELECT, если в таблицах нет удаленных строк.
При загрузке таблицы из текстового файла используйте команду LOAD DATA INFILE. При этом обычно вставка будет происходить в 20 раз быстрее, чем при использовании соответствующего количества операторов INSERT. См. раздел Синтаксис оператора LOAD DATA INFILE.
Если таблица имеет много индексов, можно проделать некоторую дополнительную работу, чтобы команда LOAD DATA INFILE выполнялась еще быстрее. Можно ускорять операции вставки, выполняемые несколькими операторами, путем установки блокировки таблиц.
Главный фактор, влияющий на скорость, - то, что буфер индексов сбрасывается на диск только один раз, после завершения всех операторов INSERT. Обычно содержимое индексных буферов сбрасывалось бы на диск столько раз, сколько имеется различных операторов INSERT. Блокировка не нужна, если можно вставить все строки при помощи одного оператора. Для транзакционных таблиц, чтобы повысить скорость, следует использовать BEGIN/COMMIT вместо LOCK TABLES. Блокировка также понизит полное время проверки подсоединений (multi-connection tests), но максимальное время ожидания для некоторых потоков повысится (потому что они ожидают снятия блокировки).
- Какое пространство занимает массив TIntVector10, объявленный в примере? Проведите расчет
Язык программирования Object Pascal имеет встроенную поддержку массивов. Это означает, что язык непосредственно содержит набор синтаксических конструкций, позволяющих объявлять переменные типа массива и выполнять некоторые операции над такими переменными. Object Pascal поддерживает как статические массивы (фиксированные контейнеры), так и динамические массивы (динамические контейнеры).
Рассмотрим использование массивов в программе на языке Object Pascal. Для создания массива необходимо объявить тип массива в разделе объявления типов type при помощи конструкции array ... of, и затем использовать данный тип при объявлении переменных. При этом для создания статического массива указывается непосредственно размер массива в виде диапазона индексов, а для динамического массива – нет, например:
type
TIntVector10 = array [1..10] of Integer;
TIntVector = array of Integer;
Первое объявление создает тип статического массива, элементами которого являются целые числа, и имеющего размер 10 элементов. Второе объявление создает тип динамического массива, элементами которого являются целые числа, а размер может быть задан произвольно в любой момент выполнения программы. Для объявления переменных-массивов воспользуемся разделом var:
var
a: TIntVector10;
b: TIntVector;
Для динамического массива перед использованием необходимо установить размер, для этого в языке Object Pascal существует процедура SetLength:
SetLength (b, 20); // размер массива b – 20 элементов
18. Что такое сортировка данных? Какими свойствами обладают алгоритмы сортировки?
Сортировка массива
Под сортировкой массива подразумевается процесс перестановки элементов массива, целью которого является размещение элементов массива в определенном порядке. Например, если имеется массив целых чисел а, то после выполнения сортировки по возрастанию должно выполняться условие:
а[1] < а[2] < ...< a[SIZE]
где SIZE — верхняя граница индекса массива.
Примечание
Задача сортировки распространена в информационных системах и используется как предварительный этап задачи поиска, т. к. поиск в упорядоченном (отсортированном) массиве проводится намного быстрее, чем в неупорядоченном (см. рассмотренный ранее метод бинарного поиска).
Существует много методов (алгоритмов) сортировки массивов.
Рассмотрим два из них:
- метод прямого выбора;
- метод прямого обмена.
Сортировка методом прямого выбора
Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:
1. Просматривая массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый — на место минимального.
2. Просматривая массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй — на место минимального.
3. И так далее до предпоследнего элемента.
Сортировка методом обмена
В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением — к концу массива (тонут). Поэтому данный метод сортировки обменом иногда называют методом "пузырька". Этот процесс повторяется столько раз, сколько элементов в массиве, минус единица.
19. Что такое предикат сортировки? Как он реализуется на языке программирования Object Pascal?//////
Под термином «сортировка» (англ. sort) теория алгоритмов понимает процесс упорядочивания элементов данных на основе некоторого правила, известного также как предиката сортировки. В случае если элемент данных является составным, то поле, по которому осуществляется упорядочивание, называется ключевым полем или ключом. Алгоритмы сортировки оценивают по следующим критериям: 1)Время сортировки 2)Размер дополнительной памяти 3)Устойчивость (stability)
Простейшим алгоритмом сортировки является алгоритм пузырьковой сортировки (bubble sort). При выполнении этого алгоритма контейнер с данными просматривается поэлементно, на каждом проходе элементы контейнера сравниваются попарно при помощи предиката сортировки. Если оказывается, что порядок элементов неверен, то элементы меняются местами. Алгоритм продолжает работу до тех пор, пока существуют неверно упорядоченные элементы. Если на очередном проходе таких элементов найдено не будет, то алгоритм завершает работу, и контейнер оказывается упорядоченным. При работе алгоритм фактически находит элементы, стоящие не на «своем» месте, и затем перемещает их в нужную позицию, т.е. образно говоря элемент «всплывает» до нужной позиции, как пузырек в воде.
Алгоритм сортировки вставками (insertion sort). На каждом шаге выполнения алгоритм выбирает некоторый элемент сортируемого контейнера, определяет позицию, в которой элемент должен находиться после упорядочивания и выполняет вставку элемента в эту позицию. Алгоритм сортировки вставками обладает следующими свойствами: 1)алгоритм прост в реализации; 2)алгоритм эффективен на небольших наборах данных;3)алгоритм эффективен на наборах данных, которые уже частично отсортированы;4)это устойчивый алгоритм сортировки.
Алгоритм быстрой сортировки (quick sort), считающийся самым эффективным алгоритмом в общем случае. Быстрая сортировка использует стратегию «разделяй и властвуй». Идея алгоритма: 1)Выбираем в массиве некоторый элемент, который будем называть опорным элементом;2)Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного – справа от него;3)Рекурсивно сортируем подсписки, лежащие слева и справа от опорного элемента;4)Базой рекурсии являются списки, состоящие из одного или двух элементов, которые уже отсортированы. Алгоритм всегда завершается, поскольку за каждую итерацию он ставит по крайней мере один элемент на его окончательное место.
20. Приведите пример устойчивых и неустойчивых алгоритмов сортировки.
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Алгоритмы устойчивой сортировки
Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. Большинство простых методов сортировки устойчивы.
Сортировка пузырьком —для каждой пары индексов производится обмен, если элементы расположены не по порядку
Сортировка вставками —определяем где текущий элемент должен находится в упорядоченном списке и вставляем его туда
Сортировка слиянием —выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки
Блочная сортировка, Сортировка перемешиванием, Сортировка подсчётом,
In-place merge sort, Двоичное дерево сортировки, Цифровая сортировка
Лексикографичкская или поразрядная сортировка, Гномья сортировка
Алгоритмы неустойчивой сортировки
Сортировка выбором —поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка
Пирамидальная сортировка - превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
Быстрая сортировка — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Сортировка Шелла, Сортировка расчёской, Introsort, Плавная сортировка, Patience sorting
21. Какой алгоритм сортировки следует выбирать при отсутствии информации о природе входных данных? Почему?
22. Постройте доминанту для алгоритма быстрой сортировки N∙logN. По определению O-большое, найдите такое N0 для Вашей системы, после которого функция N∙logN будет доминирующей.
23. Что такое поиск? Какие требования накладывают алгоритмы поиска на контейнеры данных?
Процесс поиска может быть представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в которую можно попасть из текущей. Если очередная выбранная точка совпала с заданной конечной точкой, то маршрут найден. Если не совпала, то делаем из этой точки еще шаг. Так как текущая точка может быть соединена с несколькими другими, то нужен какой-то формальный критерий выбора. В простейшем случае можно выбрать точку с наименьшим номером. Таким образом, процесс поиска состоит из шагов вперед и возвратов назад. Поиск завершается, если из узла начала движения уже некуда идти. Алгоритм поиска имеет рекурсивный характер: чтобы сделать шаг, мы выбираем точку и опять делаем шаг, и так продолжаем до тех пор, пока не достигнем цели.Таким образом, задача поиска маршрута может рассматриваться как задача выбора очередной точки (города) и поиска оставшейся части маршрута, т. е. имеет место рекурсия.
Термин «поиск» (англ. search) в теории алгоритмов обозначает процесс определения в некотором контейнере элемента, удовлетворяющего заданным критериям. В роли критерия поиска обычно выступает некоторый предикат P(x), где x – элемент контейнера, в котором производится поиск. Считается, что элемент удовлетворяет критерию поиска, если значение предиката P(x) истинно. В случае если элемент данных является составным, то поле, по которому осуществляется поиск, называется ключевым полем или ключом. Основным свойством для оценки алгоритмов поиска является время поиска, обычно выраженное как оценка временной сложности O(N), где N – размер обрабатываемого контейнера данных. Аналогично алгоритмам сортировки, для алгоритмов поиска важны оценки для лучшего, среднего и худшего случаев, вытекающих из наличия искомого элемента в контейнере и месте его расположения.
Алгоритмы поиска можно разделить на две группы: 1)Алгоритмы, работающие на произвольных контейнерах, то есть контейнерах, в которых расположение элементов произвольно. Например, если элементы в массиве хранятся в неупорядоченном виде, то для осуществления поиска необходимо просмотреть все элементы контейнера, то есть временная сложность такого алгоритма будет линейной O(N), где N – размер контейнера. 2)Алгоритмы, требующие специально подготовленных контейнеров, то есть контейнеров, в котором расположение элементов подчиняется некоторым правилам. Например, если массив предварительно отсортировать, то можно воспользоваться более продвинутыми алгоритмами, пользующимися свойством упорядоченности элементов, что позволит уменьшить время поиска.
Основным алгоритмом первой группы, работающим на произвольном контейнере, является алгоритм последовательного поиска (sequential search). Алгоритм просматривает контейнер последовательно, элемент за элементом и проверяет критерий поиска, до тех пор, пока элемент не будет найден или пока не будет достигнут конец массива. После чего делается заключение о наличии искомого элемента в контейнере и о его позиции.
Для повышения эффективности поиска обычно применяют специально подготовленные контейнеры и алгоритмы из второй группы, умеющие такие контейнеры обрабатывать. Рассмотрим один из таких алгоритмов – алгоритм бинарного поиска (binary search). Перед его применением контейнер должен быть отсортирован. Алгоритм основан на стратегии «разделяй и властвуй»: начиная с большой задачи, разбиваем ее на набор более мелких задач, которые проще решить.
---*-----24. Что такое критерий поиска? Как он реализуется на языке программирования Object Pascal?
Необходимым компонентом содержания пользовательского запроса является описание тех свойств, которыми обладают документы, интересующие пользователя. Это описание естественно называть критерием поиска.
25. Какой алгоритм поиска следует выбирать при отсутствии информации о природе входных данных? Почему?
26. Что такое инвариант? Что такое утверждение?
Инвариант — это величина, которая остаётся неизменной при тех или иных преобразованиях. В некоторых задачах инвариант — это величина, которая изменяется монотонно, то есть только увеличивается или только уменьшается.