Каким образом алгоритм завершает работу?

С помощью диаграммы

Диаграмма представляет собой геометрический объект (ориентированный граф), состоящий из вершин и дуг. Каждой вершине приписывается состояние машины Тьюринга: таким образом, вершин в диаграмме ровно столько, сколько имеется состояний. Дуге, соединяющей две вершины q_i и q_j, приписывается некоторый символ a алфавита A и двойка b D так, что запись a q_i b q_j D образует команду программы машины Тьюринга.

 

Композиция машин Тьюринга

1. Последовательное соединение машин.

Для организации такой работы достаточно построить объединенную таблицу машины Тьюринга, приписав к первой таблице вторую (справа) и заполнив пустые клетки первой таблицы командой перехода к начальному состоянию второй программы.

f(x)=(x+1)*2

	g1	g2	g3	g4	s1	s2	s3
1	1 g1 R	0 g2 L	1 g3 L	1 s1 S	1 s1 R	1 s2 L
0	0 g1 R	1 g3 L	0 g3 L	0 s1 S	0 s1 R	0 s2 L
e	e g2 L	1 g4 S	e g4 R		0 s2 L	e s3 R

 

Итерация (повторение) машин Тьюринга

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

f(X)=X+L                   eeeeX*Leeeee

	s1	s2	q1	q2	q3	q4	q5
1	1 s1 L	1 q1 S	1 q1 R	e q3 L	1 q3 L	1 q4 L
e	1 s2 S		e q2 L		e s1 R	e q5 R
*			* q1 R		* q3 L

 

3) Формализация понятия алгоритма: нормальные алгорифмы Маркова, определение и выполнение. Примеры.

Алгорифмы Маркова (нормальные алгорифмы) используются для представления алгоритмов, преобразующих одну цепочку символов (исходные данные) в другую (результат).

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

Если применив алгоритм  к строке , мы, за конечное число шагов, получили результат , то такой алгоритм будем называть применимым и обозначать  

Замены выполняются в соответствии с заданным правилом, которые и будут определять алгоритм. Такой алгоритм называется вербальным.

Расширим алфавит  тремя символами «», «». «|». Предполагается, что в алфавит  эти символы не входят. В расширенном алфавите можно записывать разные слова, но особенное внимание уделим сломам вида: , где  - один из двух символов: стрелка или стрелка с точкой,  - любая цепочка символов в алфавите .

Если такое правило срабатывает, то в исходной строке отыскивается подстрока  и она целиком заменяется на .

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

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

Если какая-то подстановка действует на исходную строку, причем левая часть встречается в строчке многократно, то формула подстановки применяется один раз. Причем применяется к самому левому вхождению.

При заменах могут использоваться пустые строки

Если в схеме используется несколько правил, в которых правые части совпадают, а левые части являются подстроками, которые можно объединить в какое-то множество, то пишут

, где  - все элементы от А до Я

Пустая строка может встречаться и в левой части. Если есть такие правила, то пустота замениться слева. В этом случае при составлении схемы, нужно думать о том, чтобы алгоритм был применим.

Суперпозиция

Будем предполагать, что все функции к которым применяется операция суперпозиции определены на одном и том же наборе входных данных. Обозначим функции, к которым применяется операция суперпозиции:

Если какой-то элемент из набора  не используется для вычисления какой-то из функций, то для этой функции мы объявляем этот элемент не значащим.

Входными данными для  будут результаты вычисления  для набора

, где  - количество переменных в объединенном наборе переменных функций с индексами от 1 до .

Все рассматриваемые функции являются частными, т.е не всюду определенными; могут существовать такие комбинации аргументов, для которых значение функции не существует.

Функция  не будет определена в двух случаях:

1. Значение  не определено

2. , но при этом  не определено

Примитивная рекурсия

Операция примитивной рекурсии имеет два операнда

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

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

Операция минимизации

Операция минимизации  имеет один операнд, . Значения функции  на заданном наборе аргументов  получаются следующим образом. Сначала с помощью функции  формируется уравнение , а затем отыскивается его решение . Если таких решений несколько, то берется минимальное из них; оно и считается значением функции  на данном наборе аргументов. Может случится, что уравнение не имеет ни одного решения. В этом случае считается, что функция  не определена на заданном наборе аргументов.

Оператор минимизации может превратить всюду определенную функцию в частичную.

Множество функций, получаемых применением к базовому набору  конечного числа операций типа суперпозиции, примитивной рекурсии и минимизации называется множеством частично-рекурсивных функций и обозначается .

Примеры определения функций при помощи этих трех операций:

1)

2)

3)

 

                                

 

5) Проблема алгоритмической разрешимости. Примеры неразрешимых алгоритмических проблем.

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

 

Факт алгорифмической неразрешимости доказал в 1970 году российский математик Ю.В. Матиясевич.

 

Задачи, для которых не существует алгоритма, решающего ее, называют алгорифмически неразрешимыми. но аглорифмическая неразрешимость некоторой общей задачи не означает, что не могут быть созданы алгоритмы, решающие частные случаи задачи. 

 

 

В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов.

 

Проблема умирающей матрицы: для данного конечного множества квадратных матриц n × n определить, существует ли произведение всех или некоторых из этих матриц (возможно, с повторениями) в каком-либо порядке, дающее нулевую матрицу. Проблема неразрешима даже для n=3 (разрешимость для n=2 является открытым вопросом^[2])

 

6) Методы разработки алгоритмов. Суперпозиция, итерация, рекурсия.

Ключевым подходом в алгоритмизации является сведение задачи к подзадачам, а способ такого сведения определяет метод разработки алгоритмов.

 

1. Суперпозиция – самый простой метод. Состоит в том, что решение сложной задачи представляется как последовательное решение более простых задач, при этом результат решения предыдущей задачи используется в качестве входных данных для решения следующей задачи.

Разбивать задачу на подзадачи, можно:

1) разбивать исходные и выходные данные на части и упрощать их; под разбиением понимаем разделение структуры данных на части, например, разделение вектора из десяти компонент на два по пять компонент или разделение текста на предложения; под упрощением понимаем такие ситуации, когда, например X – число и его нельзя разбить на части, но его можно разложить в сумму X= X₁+ X₂, так, что результаты f(X₁) и f(X₂), отыскиваются проще, чем f(X).

2) производить декомпозицию функции f, т.е превращать ее в суперпозицию более простых, f(X)= g(h(s(X))) или f(X)= g(X, h(X), s(X))

На практике используется совмещение этих методов.

2. Итерация – частный случай предыдущего метода.

f(X)=g(g(g(g(X))) или f(X)=g(X,s(X),s(X),s(X))

Однородность подзадач позволяет значительно сократить длину текста алгоритма за счет применения операторов повторения (циклов).

3. Метод последовательного приближения

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

4. Метод обратной функции

Иногда обратная задача решается значительно более просто, чем исходная. Тогда имеющийся алгоритм решения обратной задачи, можно использовать для решения прямой задачи.

 

5. Рекурсия

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

 

6. Метод полного перебора

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

 

7) Технологии разработки программ. Технологии и методы тестирования программ.

 

1. Постановка задачи - составление точного и понятного словесного описания того, как должна работать будущая программа, что должен делать пользователь в процессе ее работы.
2. Разработка интерфейса (интерфейс - способ общения) - создание экранной формы (окна программы).
3. Составление алгоритма.
4. Программирование - создание программного кода на языке программирования.
5. Отладка программы - устранение ошибок.
6. Тестирование программы - проверка правильности ее работы.
7. Создание документации, помощи.

Качество (программных средств) можно определить как совокупную характеристику исследуемого ПО с учётом следующих составляющих:

· Надёжность

· Сопровождаемость - процесс улучшения, оптимизации и устранения дефектов программного обеспечения (ПО) после передачи в эксплуатацию

· Практичность

· Эффективность

· Мобильность

· Функциональность

 

           

8) Рекурсивные алгоритмы: определение и виды рекурсии. Реализация рекурсии и использование стека. Рекурсия и итерация. Примеры, сравнение.

Алгоритм  называется рекурсивным, если:

1. хотя бы один шаг этого алгоритма представляет собой обращение  к себе. Под обращением будем понимать передачу управления или вызов. В этом случае речь идет о прямой рекурсии.

2. хотя бы один шаг этого алгоритма представляет собой обращение  к , который в свою очередь вызывает . Такая рекурсия называется косвенной.

 

 

Реализация рекурсии

, причем  и

1)

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

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

При компиляции процедуры необходимо решить один важный вопрос: как быть с ее локальными переменными и параметрами, передаваемыми по значению? Есть два варианта:

1. Локальные данные, используемые в подпрограмме, размещаются в памяти статически, это означает, что и объем памяти, необходимый для их размещения, и адреса всех констант и переменных определяются еще на этапе трансляции. Преимущество такого способа в том, что не тратится время на выделение памяти. Однако, при таком распределении памяти, возникают проблемы с реализацией рекурсии, т.к при каждом вызове мы должны хранить свои копии локальных данных.

2. Динамическое распределение памяти, при таком распределении, память для локальных данных выделяется при вызове процедуры или функции. Такая процедура называется реинтерабельной. Код такой процедуры называют чистым кодом.

 

Модель стека

Стек представляет собой область памяти со смежными адресами. Размер стека фиксирован. Его размер определяется до начала выполнения программы. Базовый адрес – начало стека.

 

Для стека выполняются две операции:

1. Поместить данные в вершину стека (втолкнуть, push)

2. Вытолкнуть, pop

 

Стек в программировании используется для нескольких целей:

1. как вспомогательная рабочая память для организации вычислений

2. реализация вызовов процедур и функций

 

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

 

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

 

 

Begin

for i:= 1 to n do {Цикл 1}

for j:= 1 to n do {Цикл 2 и начало тела цикла 1}

begin

  c [ i, j ]:= 0; {Начало тела цикла 2}

  for k:= 1 to n do {Цикл 3}

   c[i, j]:= c[i, j] + a[i, k] * b[k, j]; {Тело цикла 3}

end {Конец тела цикла 2; конец тела цикла 1}

end;

Тип данных matrix определен вне процедуры как двумерный массив. Время доступа к элементам не учитываются при анализе алгоритмов. Прежде всего, выберем параметр V. Простой анализ текста показывает, что за параметр сложности данных можно взять размер n матриц, участвующих в вычислениях. Поскольку процедура представляет собой цикл по переменной i, то ее временная сложность

Т _α (n) = n· T ⁽¹⁾.

В свою очередь,

T ⁽¹⁾ = n· T ^{( 2 )}

и, следовательно,

Т _α (n) = n·(n· T ^{( 2 )}).

Тело цикла 2 состоит из одного оператора присваивания и цикла 3. Таким образом,

Т _α (n) = n·(n·(1 + n· T ^{( 3 )})).

Тело цикла 3 включает умножение, сложение и присваивание (3 операции). Окончательно получаем

Т _α (n) = n ·(n ·(1 + n ·3)) = 3 n ³ + n ²

End;

 

· Для вычисления сложности рекурсивных алгоритмов используется рекуррентное уравнение:

T _a (X)=T _a (f(X))+ T_f(X)+ T_h(X)+ T_с (X,S)

T _a (S)=T_c(S,S)+ T_s(S)

Здесь

T _a(X) – общая сложность рекурсивного алгоритма

T _a(f(X)) – сложность предыдущего уровня рекурсии

T_f(X) – сложность вычисления аргументов при рекурсивном вызове процедуры

T_h(X) – сложность нерекурсивных вычислений

T_с(X, S) – сложность операции сравнения

T_s(S) – сложность вычисления нерекурсивного начального значения

T_c(S, S) – сложность операции сравнения для нерекурсивного начального значения

Пример:

Function F(n);

begin

If (n=0) or (n=1) {проверка возможности прямого вычисления}

       Then

             F:= 1

       Else

             F:=n*F(n-1); {рекурсивный вызов функции}

End;

X = x, 

S = 1, x = 1

f(X)=X-1,  FACTORIAL (x-1)

Tf(X)=1,    FACTORIAL (x-1)

Th(X) = 2,  FACTORIAL:= x * FACTORIAL (x-1)

Tc(X,S)=l,  x = 1

Ts(S) = 1.   FACTORIAL:= 1

Таким образом, система уравнений превращается в

Тa(x) = Тa(х-1)+4, Тa(1) = 2.

Ее решение – Тa(x) = 4х-2.

 

В случае косвенной рекурсии рекуррентное уравнение имеет вид:

 

                                                    

12) Оптимизация алгоритмов. Примеры.

Поиск алгоритма min сложности – оптимизация алгоритма.

 

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

 

Существует несколько самостоятельных аспектов оптимизации программ, из которых выделим два:

· оптимизация, связанная с выбором метода построения алгоритма;

· оптимизация, связанная с выбором методов представления данных в программе.

 

Первый вид оптимизации имеет глобальный характер и (при удачной оптимизации) ведет к уменьшению порядка функции сложности - например, замена алгоритма с Т a (V) = O(F^S) на алгоритм с T a (V) = O(V⁴). Он зависит от того, как задача разбивается на подзадачи, насколько это разбиение свойственно самой задаче или является только искусственным приемом.

 

Второй вид оптимизации, не меняя структуры программы в целом, ведет к экономии памяти и/или упрощению работы со структурами данных, повышению эффективности вспомогательных процедур, обеспечивающих "интерфейс" между прикладным уровнем (на котором мыслим в терминах высокоуровневых объектов - графов, матриц, текстов и т. д.) и машинным уровнем, поддерживающим простейшие типы данных (числа, символы, указатели). Результатом этого обычно является уменьшение коэффициентов при некоторых слагаемых в функции сложности (при удачной оптимизации - при наиболее значимом слагаемом), но порядок функции сложности остается тем же.

 

Пример: вычисления числа Фибоначчи через формулу:

 

 

13) Понятие сложности задачи и классы сложности задач. Понятия сводимости, полиномиальная сводимость.

Задачи:

1. массовые (список параметров и формулировка условий)
2. частные (формальные параметры заменяются фактическими)

сложность задачи – сложность самого простого алгоритма. Поиск алгоритма min сложности – оптимизация алгоритма.

Детерминированные вычисления – обычный, классический способ.

Недетерминированные вычисления – существует в нескольких параллельно работающих экземплярах. Недетерминированный вычислитель исполняет недетерминированные алгоритмы. Разрешаем шаги с неоднозначным результатом – шаги, вырабатывающие сразу несколько значений для одной переменной. Эти значения могут использоваться:

1. параллельно выполняющиеся процессы.
2. угадать, какое из значений, полученных на данном шаге, является правильным и использовать только его.

Классы сложности задач:

1. полиномиальные-их временная сложность ограничивается сверху некоторым полиномом.
2. экспоненциальные – в общем случае требуется кол-во операций, увеличивающееся с ростом n по крайней мере експоненциально.
3. NP – задачи, которые можно решить за полиномиальное время на недетерминированном вычислителе

Задача Q сводится к задаче Р за полином.время, если сущ-ет детерминированный полиномиальный алгоритм, преобразовывающий произвольный частный случай задачи Р так, что ответом для данного случая задачи Q является «да» тогда и только тогда,када ответом на соответсвующий случай задачи Р также является «да».

вход для Q                Вход для Р               ответ Р                              Ответ Q

 

 

Полиномиальная сводимость – детерминированный полиномиальный алгоритм сводит одну задачу к другой

NPC – подкласс NP, любая задача NP сводится к ним

 

 

                        

14) Методы сортировок: сортировка массивов простыми включениями, сортировка массивов простым выбором, сортировка обменами. Анализ сложности алгоритмов сортировки.

Сортировка – процесс перегруппировки заданного множества объектов в некотором определенном порядке. Цель сортировки – облегчить последующий поиск элементов в таком упорядоченном (отсортированном) множестве. Сортировку массивов называют внутренней сортировкой, т.к. поскольку массивы хранятся в быстрой, оперативной, внутренней памяти ЭВМ, допускающей случайный (прямой) доступ к элементам.

При анализе сложности алгоритмов сортировки будем учитывать только операции сравнения и пересылки записей.

 

Сортировка обменами:

Производится последовательное упорядочение смежных пар элементов массива: x [1] и x [2], x [2] и x [3], … x [ N -1] и x [ N ]. Если первый элемент больше второго, то элементы переставляются. В итоге, после N –1 сравнения максимальное значение переместится на место элемента X [ N ], т.е. "вверху" оказывается самый "легкий" элемент – отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента (X [ N –1]), таким образом второй по величине элемент поднимается на правильную позицию и т.д. Таким образом, нужно выполнить данную процедуру N –1 раз.

При первом прохождении нужно сравнить N –1 пар элементов, при втором – N –2 пары, при k -м прохождении – N ‑ k пар.

 

Program Sort1;

Const N=10;

Type mas=array[1..N] of real;

Var x:mas;

i,k:integer;

a:real;

Begin

For i:=1 to N do {Ввод элементов массива}

read(x[i]);

For i:=1 to N-1 do {Сортировка}

For j:=1 to N-i do

If x[j]>x[j+1] then Begin

   a:=x[j];

   x[j]:=x[j+1];

   x[j+1]:=a;

  End;

For i:=1 to N do {Вывод элементов массива}

Write(x[i],’ ‘)

End.

Среднее число сравнений и обменов имеют квадратичный порядок роста: О (n ²), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.

 

Begin

for i:=1 to N do        { Ввод элементов массива }

read(a[i]);

for i:=n downto 2 dobegin

k:=i;               {Запоминаем номер и }

m:=a[i];            {значение текущего элемента}

for j:=1 to i-1 do   {Поиск максимального элемента}

if a[j]>m thenbegin

    k:=j;

    m:=a[k]

end;

if k<>i thenbegin { Меняем местами с последним }

    a[k]:=a[i];

    a[i]:=m

    end

end;

for i:=1 to N do     { Вывод элементов массива }

write(a[i]:3)

end.

 

 

Бинарный поиск –

Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.

Переменные Lb и Ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Случайный поиск

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

 

Метод крайне не эффективен.

 

 

18) Алгоритмы внешней сортировки: метод естественного слияния, метод сбалансированного слияния. Двухпутевая и многопутевая реализация. Фибоначчиева сортировка.

 

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

 

Очевидно, что любой алгоритм сортировки файла требует изъятия каких-то

элементов из файла и включения их в файл на новые места. Таким образом, часть файла

должна быть переписана на новое место (в новый файл или несколько новых файлов), а

затем эти новые файлы должны быть объединены (слиты). Основным понятием будем

считать понятие отрезка файла. Отрезком длины k является последовательность записей

A i, A i+1,…A i+k-1 такая, что в ней все записи упорядочены по заданному ключу key.

 

Естественное слияние

При использовании метода прямого слияния не принимается во внимание то, что

исходный файл может быть частично отсортированным.

 

Первая серия упорядоченных записей и переписывается в файл B, вторая - в файл C

и т.д. При слиянии первая серия записей файла B сливается с первой серией файла C,

вторая серия B со второй серией C и т.д. Если просмотр одного файла заканчивается

раньше, чем просмотр другого (по причине разного числа серий), то остаток файла

целиком копируется в конец файла A. Процесс завершается, когда в файле A остается

только одна серия

 

 

Многофазная сортировка

При использовании рассмотренного выше метода сбалансированной многопутевой

внешней сортировки на каждом шаге примерно половина вспомогательных файлов

используется для ввода данных и примерно столько же для вывода сливаемых серий. Идея

многофазной сортировки состоит в том, что из имеющихся m вспомогательных файлов

(m-1) файл служит для ввода сливаемых последовательностей, а один - для вывода

образуемых серий. Как только один из файлов ввода становится пустым, его начинают

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

файлов. Таким образом, имеется первый шаг, при котором серии исходного файла

распределяются по m-1 вспомогательному файлу, а затем выполняется многопутевое

слияние серий из (m-1) файла с записью в файл m, пока один из них не станет пустым..

 

Метод трехфазной внешней сортировки дает желаемый результат и работает

максимально эффективно (на каждом этапе сливается максимальное число серий), если

начальное распределение серий между вспомогательными файлами описывается суммами

соседних числел Фибоначчи.

 

 

19) Понятие хеширования. Построение хеш функции. Разрешение коллизий, линейное рехеширование, случайное рехеширование, квадратичное рехеширование, метод цепочек (списковое и матричное представление)

 

Для сокращения времени доступа к данным в таблицах используется так называемое случайное упорядочивание или хеширование.

 

Хеш-таблица – это обычный массив с необычной адресацией, задаваемой хеш-

функцией.

Хеширование (глагол «hash» в английском языке означает «рубить, крошить») применяется, когда реальное количество записей значительно меньше, чем количество возможных ключей.

 

Если входной поток информации абсолютно случаен, то в качестве хеш-функции можно использовать, например, функцию:

h (a)= code (a) mod N

При заполнении таблицы возникают ситуации, когда для двух неодинаковых ключей

функция вычисляет один и тот же адрес: ki ≠ kj; h(ki) = h(kj). Данный случай носит

название коллизия, а такие ключи называются ключи-синонимы.

 

Разрешение коллизий достигается путём рехеширования – специального алгоритма,

который используется при размещении новой записи или при поиске существующей.

 

h(a)=(B code(a) +C) mod N, где B и C – константы

При большом количестве элементов с одинаковым значением адреса будет получены

кластеры (блоки) - последовательности подряд идущих записей, соответствующих

одному и тому же адресу.

Методы разрешения коллизий:

Освобождение памяти