Matematika_dlya_Sashi


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
325


Вопрос
ы

по дисциплине “Математическая
логика и теория алгоритмов “

5. Логика предикатов.

Предикаты, кванторы, предметные функции и термы

Логика предикатов



это раздел символической логики, изучающий
рассуждения и

другие языковые контексты с

учётом внутрен
ней
структуры входящих в

них простых высказываний, при этом выражения
языка трактуются функционально, то

есть как

знаки некоторых функций
или

же как

знаки аргументов этих

функций.

предикат



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


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


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

Пример предикатов.

Возьмём высказывания: ``
Сократ
-

человек
'', ``
Платон
-

человек
''. Оба эти высказывания выражают свойство ``быть человеком''. Таким
образо
м, мы можем рассматривать предикат ``
быть человеком
'' и говорить, что он
выполняется для

Сократа

и

Платона
.


Квантор



общее название для логических операций, ограничивающих область истинности
какого
-
либо предиката.


Терм



это объектная константа или объ
ектная переменная. Строка
называется

атомарной формулой
, если она является пропозициональной
константой или имеет вид

R
(
t
1
, ..., t
n
), где

R



предикатная константа
арности

n

(
n œ

0) и

t
1
, ... , t
n



термы. Например, если мы рассматриваем
сигнатуру (
4
), то

P
(
a
) и

Q
(
a, x
)


атомарные формулы.

6. Логика предикатов.

Формула,

ее свободные и связанные переменные. Примеры

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

326


В случае предикатных формул доказательство по

структурной
индукции

имеет следующий вид.
Для данного свойства формул мы проверяем,
что



каждая атомарная формула обладает этим свойством,



для любой формулы

F
, обладающей этим свойством,

¬F

также обладает
этим свойством,



для любых формул

F, G
, обладающих этим свойством, и любой бинарной
связки


, (
F



G
) также обладает этим свойством,



для любого квантора

K
, любой переменной

v

и любой формулы

F
,
обладающей этим свойством,

Kv F

также обладает этим свойством.

Тогда это свойство выполняется для всех формул.

Множество

свободных переменных
*

формулы

F

определяется рекурсивно,
следующим образом:

Определение 22 (Свободные переменные).



Все переменные, входящие в атомарную формулу, являются

свободными
переменными

этой формулы,



своб
одные переменные

формулы

F

являются

свободными
переменными

формулы

¬F
,



переменные, являющиеся

свободными

для хотя бы одной из
формул

F

или

G
, являются

свободными переменными

формулы (
F



G
),



все

свободные переменные

формулы

F

кроме

v

являются

свободными
пе
ременными

формулы

Kv F
.

Определение 23 (Замкнутая формула).

Формула без свободных переменных
называется

замкнутой формулой
, или

предложением
.

Определение 24 (Связаная переменная).

Переменная

v

связана

в формуле

F
,
если

F

содержит вхождение

Kv
, где

K



кван
тор.

3.4

Найдите свободные переменные и связанные переменные формулы



y P
(
x, y
)

& ¬


x P

(
x, x
)


7. Логика предикатов.

Интерпретация формул. Примеры

327




8. Логика предикатов.

Равносильность формул. Примеры

328






9. Основные типы задач на структурах д
анных.Их общая постановка. Абстрактный тип данных



329


1.1.1.Основные типы данных.

Данные, хранящиеся в памяти ЭВМ представляют собой совокупность нулей и
едениц (битов). Биты объединяются в последовательности: байты, слова и т.д.
Каждому участку оперативно
й памяти, который может вместить один байт или
слово, присваивается порядковый номер (адрес).

Какой смысл заключен в данных, какими символами они выражены
-

буквенными или цифровыми, что означает то или иное число
-

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

тип

связывается не только с представлением данных в адресном
пространстве, но и со

способом их обработки
.

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

Данные простого типа это
-

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

Некоторые структуры:



Массив
(функция с конечной областью определения)
-

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

кольцо, стек, очередь и двухсторонняя очередь
.



Запись
(декартово произведение)
-

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

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

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

ключом
.

Таки
е структуры данных как массив или запись занимают в памяти ЭВМ
постоянный объем, поэтому их называют статическими структурами. К
статическим структурам относится также

множество
.

Имеется ряд структур, которые могут изменять свою длину
-

так
называемые

дина
мические структуры
. К ним относятся дерево, список, ссылка.

Важной структурой, для размещения элементов которой требуется нелинейное
адресное пространство является

дерево
. Существует большое количество
структур данных, которые могут быть представлены как д
еревья. Это,
например, классификационные, иерархические, рекурсивные и др. структуры.
Более подробно о деревьях рассказано в параграфе 1.2.1.


Язык С++ позволяет создавать типы данных, которые ведут себя
аналогично базовым типам языка Си. Такие типы обычно

330


называют

абстрактными типами данных

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


10. Основные свойства структур данных и операции с ними
. Уровни представления информации.
Изменчивость состава информации. Организация связей между элементами структур. Типовые
элементарные операции на структурах


11. Классификация структур данных


Корректные и некорректные, разрешимые задачи. Одиночные и груп
повые задачи



12. Интуитивное определение алгоритма. Основные требования к алгоритмам . Примеры

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


программа,
критерием алгоритмичн
ости процесса является возможность его
331


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

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

Определение 1.

Алгоритм

(алгорифм)


точное предписание, которое задает

вычислительный процесс, начинающийся с произвольного

исходного данного
и
направленный на получение полностью определенного этим исходным
данным

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

Другое определение понятия алгоритма может выглядеть следующим образо
м

Определение 2.

Алгоритм

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

Или

Определение 3.Алгоритм

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

Данные определения недостаточны для введения четкого и однозначного задания
исследуемого объекта. Необходимы уточнения.

1. Любой алгоритм применяется к

исходным данным

и выдает результат. Т.е.
всегда существует некий

конструктивный объект

к которому применяется
алгоритм. Ясно, что объекты должны быть четко определены и отличимы друг от
друга Чаще всего в качестве конструктивных объектов выступают данные или
структуры данных.

2. Данные для своего размещения требуют

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

3. Алгоритм состоит из отдельных

элементарных шагов

(действий). Множество
шагов алгоритма

конечно
.

4. Последовательность шагов алгоритма

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

5. Каждый алгоритм должен быть

результативным,

т.е. после конечного числа
шагов выдавать результат.

6. Следует различать:

· описание алгоритма (инструкцию или программу);

· механизм реал
изации алгоритма (устройство, например, ЭВМ), включающий
средства пуска, остановки, управления ходом вычислений и т.д.);

· процесс реализации алгоритма (алгоритмический процесс).

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


модели, например, машина Тьюринга, частично
-
рекурсивные функции, машина
Колмогорова, нормальные алгорифмы Маркова,
канонические системы Поста и т.д.




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

В работе рассматриваются несколько типов задач, удовлетворяющие постановке (0.1). Для
обозначения этих типов задач будем исполь
зовать такие названия:

-

линейная задача о назначениях;

-

задача о коммивояжере;

-

квадратичная задача о назначениях;

-

задача разбиения;

-

задача размещения;

-

один тип задач расписания.

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

задачами

комбинаторной
оптимизации
(combinatorial

optimization

problems).

Основные задачи на массивах:


http://marklv.narod.ru/book/mas02.html


14. Основные виды целевых функций.
Структуры множеств
M

и

Q
(
M
,
F
)

. Примеры


Принципиально возможны следующие критерии выбора режимов обработки при построении
оптимальной операции:

1. наименьшая технологическая себестоимость,

2. максимальная производительность,

3. максимальная стойкость инструмента
͵

4. показател
ь наименьших приведенных затрат.

4

-

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

применять

для

выбора

наилучшего

варианта

операции

при

возможной

обработке

деталей

на

разных

моделях

станков
.

3

-

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

соответствующего

этим

режимам
.

1, 2

-

В условиях

серийн
ого

производства особого внимания заслуживают две цел
œевые

функции
:

минимум технологической себестоимости

и

максимум производительности

при
выполнении операции. Эти цел
œевые

функции

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


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


15. Основные методы построения алгоритмов решений комбинаторных задач



16. Блок
-
схема алгоритма. Примеры

Сх
ма



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

т.

д.
[1]

Блок
-
схема



распространенный тип схем (
графических

моделей
),
описывающих

алгоритмы

или процессы, в которых отдельные шаги изображаются в виде
блоков различной формы, соединенных между собой линиями, указывающими направление
последовательности. Правила выполнения регламентируются ГОС
Т 19.701
-
90 «Схемы
алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения»
[1]
.
Стандарт в частности

регулирует способы построения схем и внешний вид их элементов.


17. Машина Тьюринга
. Устройство, принцип работы, основные понятия
.Табличный способ задания
машин Тьюринга

Маш
на Ть
ринга (МТ)



абстрактный исполнитель (абстрактная вычислительная машина)
.
Была предложена

Аланом Тьюрингом

в

1936 году

для формализации понятия

алгоритма
.

Машина Тьюринга является расширением

конечного автомата

и, согласно

тезису Чёрча



Тьюринга
,

способна имитировать всех исполнителей

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

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

Устройство машины Тьюринга
[
править

|

править код
]

В состав машины Тьюринга входит неограниченная в обе стороны

лента

(возможны машины
Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки
[2]
[3]
,
и

управляющее устройство

(также называется

головкой записи
-
чтения
(
ГЗЧ
)), способное
находиться в одном из

множества состояний
. Число возможных состояний управляющего
устройства конечно и точно задано.

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

пустой

символ,
заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны
входные данные.

Управляющее устройство работает согласно

правилам перехода
, которые представляют
алгоритм,

реализуемый

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


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

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

Машина Тьюринга называется

детерминированной
, ес
ли каждой комбинации состояния и
ленточного символа в таблице соответствует не более одного правила. Если существует пара
«ленточный символ



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

недетерминированной
.

принцип работы

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

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

Определить для любых заданных формул

R

и

S

в логическом исчислении,
сущ
ествует ли дедуктивная цепочка, ведущая от

R

к

S
, или нет.

Если формула

А

может быть преобразована в формулу

В

однократным
применением допустимой подстановки, и наоборот, то

А

и

В


смежные

формулы. Последовательность


формул, соседние из
которых смежные, называется

дедуктивной цепочкой,

ведущей от

к

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

R
и

S
).

Проблема является

алгоритмически неразрешимой,

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


335




18.
Задание машин Тьюринга в виде программ
. Конфигурация маш
и
ны Тьюринга. Примеры.
Тезис
Тьюринга. Существование неразрешимых корректных задач

336




Очевидно, что определённое отношение является функциональным: для каждой конфигураци
и


существует не более одной конфигурации

, для которой

.

Для машины Тьюринга, которая пишет символ


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


Тезис Тьюринга.

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

337




19. Размер задачи. Скорость роста. Примеры


20. Сложность алгоритма. Классификация алгоритмов по сложности

Вычисл
тельная сл
жность



понятие в

информатике

и

теории алгоритмов
,
обозначающее функцию зависимости

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

теорией сложности вычислений
.


Класс сложности



это множество

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


21. Класс
Р
. Полиномиальная сводимость. Примеры

Класс P
[
править

|

править код
]

Основная статья:

Класс P

Класс P

вмещает все те проблемы, решение которых считается «быстрым», то есть время
решения которых

полиномиально

зависит от размера входа. Сюда относится

сортировка
,
поиск в массиве, выяснение связности

графов

и многие другие.

Полиномиальная сводимо
сть

Определение
. Язык

L
1

за полиномиальное время к языку

L
2


(обозначение:

L
1

p
L
2

или

L
1


L
2
), если существует такая функция


f

: {0, 1}
*
, вы
числимая за полиномиальное время, что для любого слова

х
Î{0, 1}
*

:

x
Î
L
1

Û

f
(
x

L
2

(
х

является индивидуальной задачей

L
1

тогда и
только тогда, когда

f
(
x
) является индивидуальной задачей

L
2
).

22. Класс
N
Р
. Предикат задачи.
NP



полнота. Проблема
Р=NP
. Приме
ры


Класс NP
[
править

|

править код
]

Основная статья:

класс NP

Класс NP

содержит задачи, которые

недетерминированная машина Тьюринга

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

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

детерминированной машине Тьюринга

с ограниченной памятью.
338


Поскольку

детерминированная машина Тьюринга

может рассматриваться как специальный
случай

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

задача коммивояжёра
,

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

факторизация
и др.

Проблема равенства классов P и NP
[
править

|

править код
]

Основная статья:

Равенство классов P и NP

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

Математический институт Клэя

включил эту проблему
в список

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

долларов
США

за её решение.


23. Основные виды сложности комбинаторных алгоритмов. Примеры

https://habrahabr.ru/post/247807/

Вообще, комбинаторные алгоритмы я бы разбил на такие классы:




Генерац
ия комбинаторных объектов в едином цикле (тут все просто,
примеры я привел);



Переход к следующему (или предыдущему) комбинаторному объекту, зная
предыдущий (своего рода forward/backward iterator, выражаясь в терминах
C++)


тут можно отметить учебное пособ
ие Т. И. Федоряевой, где
приводится алгоритм константной временной сложности для перестановок, да
и другие примеры в рунете можно найти, но только для перестановок


а
было бы интересно увидеть аналогичные алгоритмы и для других
комбинаторных объектов;



Нах
ождение индекса объекта. Тут примеров совсем нет, исключая пособие
Федоряевой, причем линейной сложности и только для перестановки;



Нахождение объекта по индексу.


24. Приближенные алгоритмы решения комбинаторных задач. Примеры


25. Числа. Основные виды за
дач на них. Проверка свойств чисел

26. Числа. Расчет явно заданных последовательностей
. Рекурсия и рекурсивные вычисления


27 .Массивы. Выполнение элементарных операций на них


Массив

(в некоторых языках программирования также таблица, ряд, матрица)


стр
уктура
данных в виде набора компонентов (элементов

массива
), расположенных в памяти
непосредственно друг за другом.

339




28. Динамические массивы и массивы с переменной длиной. Амортизированное время
добавления элемента


Динамическим

называется

массив
, размер которого, при необходимости, может
менять
ся во время исполнения программы. Для изменения размера динамического
массива

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





340



29. Выполнение общих операций на массивах. Типы алгоритмов сортировки


Вычисление

суммы элементов массива


Дан массив

X
, состоящий из n элементов. Найти сумму элементов этого
массива. Процесс накапливания суммы элементов массива достаточно прост

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

S

присваивается значение равное
нулю, затем последовательно суммируются элементы массива

X
. Блок
-
схема
алгоритма расчета суммы перед вами:


Поиск максимального элемента в массиве

Дан массив

X
, состоящий из

n

элементов. Найти максимальный
элемент массива и
номер, под которым он хранится в массиве.

Алгоритм решения задачи следующий. Пусть в переменной с именем

Max
хранится
значение максимального элемента, а в переменной

Nmax



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

Max
, а в

Nmax


его номер (ноль). Затем все элементы начиная с
первого сравниваем в цикле с максимальным. Если текущий элемент массива
оказывается больше максимального, то записываем его в переменную

Max
, а в
переменную

N
max



текущее значение индекса

i
.


Сортировка элементов в массиве

Сортировка

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



сортировка обменом
;



сортировка выбором
;



сортировка вставкой
.

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

обменом

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

Для сортировки

выбором

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

наименьшая

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

Для сортировки

вставкой

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




30. Алгоритмы внутренней сортировки.
Сортировка простыми обменами (пузырьковая

сортировка
)

341



Внутренняя сортировка

(
англ.

internal

sort
)



разновидность

алгоритмов
сортировки

или их реализаций, при которой объема

оперативной памяти

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

периферийным устройствам

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

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

внешней сортировки



отдельные части
массива данных сортируются в оперативной памяти и с помощью специального
алгоритма

сцепляются

в один массив, упорядоченный по ключу.

В современных

архитектурах компьютеров

и

системных
архитектурах

широко применяется
подкачка и

кэширование

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

операционной
системой

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

внешней сортировки
.


Алгоритмом сортировки

называется

алгоритм

для упорядочения некоторого

множества

элементов.
Обычно под алгоритмо
м сортировки подразумевают

алгоритм

упорядочивания

множества

элементов по
возрастанию или убыванию.


Сортировка простыми обменами
,

сортир
вка пузырьк
м

(
англ.

bubble

sort
)



простой

алгоритм сортировки
. Для понимания и реализации этот алгоритм



простейший, но
эффективен он лишь для небольших массивов. Сложность алгоритма:

.

Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо
него на практике применяются более эффективные алгоритмы сортировки. В то же время
метод сортировки обменами

лежит в основе некоторых более совершенных алгоритмов, таких
как

шей
керная сортировка
,

пирамидальная сортиро
вка

и

быстрая сортировка
.


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


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



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

31. Алгоритмы внутренней сортировки.

Сортировка вставками


Сортировка вставками

(
англ.

Insertion

sort
)



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

32. Алгоритмы внутренней сортировки.

Гномья сортировка


Гномья сортировка

(
англ.

Gnome

sort
)


алгоритм сортировки
, похожий
на

сортировку вставками
, но в отличие от последней перед вставкой на нужное место
происходит серия обменов, как в

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

33. Алгоритмы внешней сортировки. Сортировка слиянием


Сортировка слиянием

(
англ.

merge

sort
)



алгоритм сортировки
, который
упорядочивает

списки

(или другие

структуры данных
, дос
туп к

элементам

которых можно
получат
ь только

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



потоки
) в определённом порядке. Эта
сортировка



хороший пример использования принципа «
разделяй
и властвуй
». Сначала
задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с
помощью

рекурсивного вызова

или непоср
едственно, если их размер достаточно мал.
Наконец, их

решения

комбинируются, и получается решение исходной задачи.

34
. Алгоритмы внешней сортировки. Быстрая сортировка

342



Общая идея алгоритма состоит в следующем:



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



Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы
разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие
опорного», «равные» и «большие»
.
[1]



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


35. Алгоритмы внешней сортировки. Пирамидальная сортировка


Массив можно отсортировать, если на его основе строить и перестраивать

сортирующее
дерево
, известное как

двоичная куча

или просто

пирамида
.


36.

Алгоритмы внешней сортировки. Метод Шелла


При сортировке Шелла сначала сравниваются и сортируются между собой значения,
стоящие один от другого на некотором расстоянии


(о выборе значения


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

, а завершается
сорт
ировка Шелла упорядочиванием элементов при


(то есть обычной

сортировкой
вставками
). Эффективность сортировки Шелла в определённых случаях обеспечивается тем,
что элементы «б
ыстрее» встают на свои места (в простых методах сортировки,
например,

пузырьковой
, каждая перестановка двух элементов уменьшает
количество

инверсий

в списке максимум на 1, а при сортировке Шелла это число может быть
больше).

37. Сортировки за линейное время. Блочная сортировка


Блочная сортировка

(Карманная сортировка, корзинная сортир
овка,

англ.

Bucket

sort
)


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

массив
. Этот тип сортировки может обладать линейным временем
исполнения.

38. Сортировки за ли
нейное время. Поразрядная сортировка

Исходно предназначен для сортировки целых чисел, записанных цифрами. Но так как в
памяти компьютеров любая информация записывается целыми числами, алгоритм пригоден
для сортировки любых объектов, запись которых можно по
делить на «разряды», содержащие
сравнимые значения. Например, так сортировать можно не только числа, записанные в виде
набора цифр, но и строки, являющиеся набором символов, и вообще произвольные значения
в памяти, представленные в виде набора байт.

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


40
. Однон
аправленный список


Линейный

однонаправленный список



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

41
. Двунаправленный и кольцевой списки




В программировании двунаправленные сп
иски часто преобразовывают следующим
образом: "обычный" линейный двунаправленный список замыкают в своеобразное "кольцо":
при движении по списку

в прямом направлении

можно от последнего звена переходить к
343


звену, следующему прямо за заглавным звеном, а при
движении

в обратную сторону

-

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

кольцевыми двунаправленными списками

4
2
. Стек. Его назначение. Реализация на базе массива


Стек

-

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

первым
уйдешь (First In First Out
). Дисциплина работы стека обозначается LIFO,
последним пришел
-

первым уйдешь (Last In First Out).


Стек можно представить в виде трубки с подпружиненым дном, расположеной
вертикально. Верхний конец трубки открыт, в него можно добавлять, или, как
говорят,

заталкивать элементы. Общепринятые английские термины в этом
плане очень красочны, операция добавления элемента в стек обозначается push,
в переводе "затолкнуть, запихнуть". Новый добавляемый элемент проталкивает
элементы, помещеные в стек ранее, на одну
позицию вниз. При извлечении
элементов из стека они как бы выталкиваются вверх, по
-
английски pop
("выстреливают").

Реализация стека на базе массива является классикой программирования.
Иногда даже само понятие стека не вполне корректно отождествляется с эт
ой
реализацией.

Базой реализации является массив размера N, таким образом, реализуется стек
ограниченного размера, максимальная глубина которого не может превышать N.
Индексы ячеек массива изменяются от 0 до N
-

1. Элементы стека хранятся в
массиве следующ
им образом: элемент на дне стека располагается в начале
массива, т.е. в ячейке с индексом 0. Элемент, расположенный над самым
нижним элементом стека, хранится в ячейке с индексом 1, и так далее. Вершина
стека хранится где
-
то в середине массива. Индекс элем
ента на вершине стека
хранится в специальной переменной, которую обычно называют указателем
стека (по
-
английски Stack Pointer или просто SP).


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

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


индексом N
-

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

43
.
Реализац
ия стека на базе связанного списка


44
. Очереди. Их реализация на базе кольцевого массива


Очередь

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

Очере
дь можно представить в виде трубки. В один конец трубки можно
добавлять шарики
-

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

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




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

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

соседний
стул. Просто начало очереди
-

какой
-
то тяжело объяснимый атрибут (ага, такое впечатление,
что в Америке нет очередей к стоматологу...)
-

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

45
.
Реализация очереди на
базе связанного списка

46
. Дек. Назначение. Реализация на базе кольцевого буфера


Дек

(от англ.

deque



double ended queue)


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

Кольцевой буфер создается пустым, с некоторой заранее определенной длиной. Например,
это семиэлементный буфер:


Предположим, что в середину буфера записывается 1 (в кольцевом буфере точная
начальная ячейка не имеет значения):


Затем предположим, что после единицы были добавлены ещё два элемента



2 и 3:


345


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


Если в буфере находится 7 элементов, то он заполнен:


Если продолжить запись в буфер, не принимая во внимание его
заполненность, то новые данные начнут перезаписывать старые данные.
В нашем случае, добавляя элементы A и B, мы

перезапишем

3 и 4:


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

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

Наконец, если тепер
ь удалить из буфера два элемента, то удалены
будут

не

3 и 4, а 5 и 6, потому что A и B перезаписали элементы 3 и 4;
буфер придет в состояние:



47
.
Реализация дека на базе двусвязного списка


48
. Упорядочение линейных структур. Сортировка списков


Подавляющее большинство

алгоритмов сортировки

требует для своей работы во
зможности
обращения к элементам сортируемого списка по их порядковым номерам (индексам).
В

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


довольно ресурсоёмкая операция, требующая в среднем n/2 сравнений и
обращений к памяти. В результате применение типичных алгоритмов сортировки становится
крайне неэффективным. Однако
у связных списков есть преимущество: возможность
объединить два отсортированных списка в один за время O(n+m) без использования
дополнительной памяти.

49
. Хеширование.

Хэш
-
таблица


Хеширование
, реже

хэширование

(
англ.

hashing
)



преобразование

массива

входных данных произвольной длины в (выходную)

битовую

строку
фиксированной
длины, выполняемое

определё
нным алгоритмом
. Функция, реализующая
алгоритм и выполняющая преобразование, называется «
хеш
-
функцией
» или «
функцией
свёртки
». Исходные данные называются входным массивом, «
ключом
» или
«
сообщением
». Результат преобразования (выходные данные) называется «
хешем
», «
хеш
-
кодом
», «
хеш
-
суммой
», «сводкой

сообщения
».

Хэш
-
табл
ца

или

хеш
-
табл
ца



это

структура данных
, реализующая
инте
рфейс

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


50
. Идеальное хеширование

346


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

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

информацией.

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


5
1
. Универсальное хеширование


Универс
льное хеш
рование

(
англ.

Universal

hashing
)


это вид

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

алгоритму
[1]
[2]
. Такой подход обеспечивает равномерное
хеширование: для очередного ключа вероятности помещения его в любую я
чейку совпадают.
Известно несколько семейств универсальных хеш
-
функций, которые имеют многочисленные
применения в

информатике
,

в частности в

хеш
-
таблицах
,

вероятностных
алгоритмах

и

криптографии
.

5
2.Хэш
-
таблицы

М
етод
ы

борьбы с коллизиями в хеш
-
таблицах

Разрешение

коллизий

(англ. collision re
solution) в

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





Приложенные файлы

  • pdf 17402890
    Размер файла: 2 MB Загрузок: 0

Добавить комментарий