Привет, это (коворкинг? если так можно сказать) по ТиСДам. Можешь просто почитать, можешь покомментировать, где-то исправить или быть крутым челиком и полностью написать вопрос.
_I cannot vanish, you will not scare me
Try to get through it, try to push through it
You were not thinking that I will not do it
They be lovin' someone and I'm another story
Take the next ticket, get the next train
Why would I do it? Anyone'd think that_
**Первоочередно искать в фотках с лекций(закреп чат
ыусемочки),вторая очередь - лекции прошлых годов(файл в чате ыусем),третья - вики,и только 4ое - дипсик.**
Ниже есть чекбоксы на неотвеченных вопросах (распишешь - отметь выполненным), также там можно оставлять пожелания. спасибо за внимание.
Ответы на вопросы:
- [ ] 1
- [ ] 2
- [ ] 3
- [ ] 4
- [ ] 5
- [ ] 6
- [ ] 7
- [ ] 8
- [ ] 9
- [ ] 10
- [ ] 11
- [x] 12
- [ ] 13
- [ ] 14
- [ ] 15
- [ ] 16
- [ ] 17
- [ ] 18
---
## 1. Понятие типа данных. Общая классификация структур.
### **1. Понятие типа данных**
**Тип данных** — это концепция, которая определяет:
1. **Множество допустимых значений** данных.
2. **Способ хранения** в памяти компьютера (различный для разных типов).
3. **Объём памяти**, занимаемый данными.
4. **Набор допустимых операций** над данными.
> *«Концепция типа данных появилась в языках программирования высокого уровня как естественное отражение того факта, что: обрабатываемые программой данные могут иметь различные множества допустимых значений, храниться в памяти компьютера различным образом, занимать различные объёмы памяти, обрабатываться с помощью различных команд процессора»* (стр. 4–5).
**Математически тип может быть определён двумя способами:**
- Множеством всех значений, принадлежащих типу.
- Предикатной функцией, определяющей принадлежность объекта к данному типу (стр. 5).
**Практическое применение типов данных:**
- Обеспечение **надёжности** (защита от некорректных присваиваний, операций, передачи параметров).
- **Стандартизация** (программисты могут быстро менять инструменты, программа не требует больших переделок) (стр. 5).
---
### **2. Классификация типов данных (по Вирту)**
Согласно классификации **Н. Вирта**, типы данных делятся на:
#### **А. Базовые (предопределённые в языке)**
- **Целые типы** (стр. 7).
- **Вещественные типы** (стр. 7–8).
- **Логический тип (BOOLEAN)** (стр. 6–7).
- **Символьный тип (CHARACTER/CHAR)** (стр. 6).
- **Указательные типы** (стр. 9–10).
#### **Б. Определяемые пользователем**
- **Перечисляемые типы** (стр. 8–9).
- **Уточняемые типы** (на основе встроенного порядкового типа) (стр. 8).
- **Конструируемые (составные) типы** — создаются на основе существующих в языке средств описания (стр. 6).
> *«„Полнотиповая система“ — это система типов, в которых пользовательские типы равноправны с предопределёнными»* (стр. 6).
---
### **3. Общая классификация структур данных**
**Структура данных (СД)** — это совокупность элементов данных, между которыми существуют какие-либо отношения.
> *«Т. е. логическая и математическая модель организации данных называется структурой данных»* (стр. 11).
**Формальное определение:**
\[ S = (D, R) \]
где \( D \) — множество элементов данных, \( R \) — множество отношений между ними (стр. 11).
---
#### **Классификация по организации взаимосвязей (стр. 12):**
1. **Линейные структуры**:
- Массив, список, стек, очередь, хеш.
2. **Передвижные (иерархические) структуры**:
- Дерево, иерархический список.
3. **Сетевые структуры**:
- Граф (ориентированный, взвешенный).
4. **Табличные структуры**:
- N-мерные массивы, таблицы базы данных.
5. **Другие**:
- Лес (список непересекающихся деревьев).
---
#### **Классификация по характеру изменения размера (стр. 14):**
**А. Статические структуры данных** — размер фиксирован на этапе компиляции.
- **Простые**: символы, логические, указатели, числа.
- **Определяемые программистом**: интервалы, перечисления.
- **Составные**:
- *Однородные*: строки, множества, массивы.
- *Неоднородные*: структуры, записи, объединения, объекты.
**Б. Динамические структуры данных** — размер может изменяться во время выполнения.
- Файлы (текстовые, бинарные…).
- **Связные динамические структуры**:
- *Линейной структуры*: односвязные/многосвязные списки, стеки, очереди, деки.
- *Кольцевой структуры*: кольцевые списки.
- *Нелинейной структуры*: графы, деревья (бинарные, разветвлённые).
- **Несвязные динамические структуры** (классифицируются как статические).
---
#### **Классификация по уровням представления (стр. 13):**
| Логическая (абстрактная) СД | Физическая (конкретная) СД |
|------------------------------|-----------------------------|
| Идеальная схема представления или модель. Пример: матрица как прямоугольный двумерный массив. | Схема размещения и хранения данных в памяти. Пример: матрица как последовательность ячеек памяти. |
> *«Т. Е., каждая СД определяется логическим и физическим представлением и совокупностью отношений на этих двух уровнях представления СД»* (стр. 13).
---
### **4. Фундаментальное уравнение (по Н. Вирту)**
> *«Таким образом, по формулировке Н. Вирта,*
> **АЛГОРИТМ + СД = ПРОГРАММА**
> *С наших позиций:*
> **СД + АЛГОРИТМ = ПРОГРАММА**» (стр. 13).
---
### **5. Выбор структуры данных**
При выборе СД учитываются:
1. **СД должна отражать фактические связи данных в реальном мире**.
2. **СД должна быть достаточно проста для простоты её обработки** (стр. 11).
----
## 2. Оценка эффективности алгоритмов, временная и емкостная сложность алгоритмов.
#### Оценка эффективности алгоритмов
Анализ любого алгоритма должен дать четкое представление:
1. Ёмкостной
2. Временной сложности процесса.
#### Временная сложность алгоритмов.
Временная сложность (time efficiency) — время работы программы. Реальное время выполнения каждого шага алгоритма зависит от конкретного вычислительного устройств.
#### Емкостная сложность алгоритмов.
Емкостная сложность (пространственная) (space efficiency) - это размер памяти, в которой предстоит размещать все данные, участвующие в вычислительном процессе (входные наборы данных, промежуточная и выходная информация).
Возможно, не все перечисленные наборы требуют одновременного хранения, - значит, удается сэкономить.
В ряде случаев, оценка емкостной сложности становится менее очевидной, например при использовании динамических структур.
-----
## 3. Выделение памяти под статические массивы. **Расчет** адресов памяти элементов массива с использованием дескриптора массива. Вектора Айлиффа. Принципы выделения памяти под динамические массивы.
#### Выделение памяти под статические массивы.
Не совсем выкупаю сложности.
```c
int main(void)
{
int *mas_by_ptr;
int mas_with_len[5];
int mas_init[] = {1, 2, 3, 4};
return 0;
}
```
#### **Расчет** адресов памяти элементов массива с использованием дескриптора массива.
Для $n$-мерного массива $M[I_1..K_1, I_2..K_2, \dots, I_n..K_n]$ длиной элемента $L$ при известном адресе первого элемента $Addr(M[I_1,\dots,I_n])$ адрес произвольного элемента $M[J_1,\dots,J_n]$ вычисляется так:[^1]
$$
Addr(M[J_1,\dots,J_n]) = Addr(M[I_1,\dots,I_n]) - L \cdot \sum_{m=1}^{n} I_m D_m + L \cdot \sum_{m=1}^{n} J_m D_m
$$
Константа
$$
C = Addr(M[I_1,\dots,I_n]) - L \cdot \sum_{m=1}^{n} I_m D_m
$$
вычисляется один раз и заносится в дескриптор как «постоянная часть» для данного массива, а $L \cdot D_m$ — как индексные множители.[^1]
Тогда формула упрощается до:[^1]
$$
Addr(M[J_1,\dots,J_n]) = C + \sum_{m=1}^{n} J_m \cdot (L \cdot D_m)
$$
Все умножения $L \cdot D_m$ заранее выполнены и хранятся в дескрипторе, при обращении к элементу остаются только сложения и умножение индекса на уже готовый множитель.[^1]
##### Содержимое дескриптора массива
Дескриптор многомерного массива содержит:[^1]
- Адрес первого элемента $Addr(M[I_1,\dots,I_n])$.
- Размерность $n$.
- Для каждой размерности: $I_m, K_m$.
- Длину элемента $L$.
- Индексные множители $L \cdot D_m$.
- Постоянную часть $C = Addr(M[I_1,\dots,I_n]) - L \cdot \sum I_m D_m$.[^1]
При обращении к элементу $M[J_1,\dots,J_n]$ используется только дескриптор и заданные индексы: адрес считается по линейной формуле без повторного вычисления $D_m$.[^1]
#### Векторы Айлиффа
***Вектор Айлиффа*** - вспомогательный дескриптор. Каждый элемент в-ра Айлиффа содержит указатель на дескриптор следующего, более низкого уровня, а дескр-р самого низкого уровня указывает на группы элементов массива. Основной дескриптор массива (нулевой деск-р) хранит указатель вектора Айлиффа первогоуровня. Каждый из указателей адресует обл-ть памяти, соответствующую нулевому значению индекса. После прибавления к указателю значения индекса получаем адрес соот-ющего компонента вектора Айлиффа или, в случае вектора нижнего уровня, - адрес требуемого элемента массива. Т. о., к элементу массива __M[J1 ,J2, ,Jn]__ можно обратиться, пройдя по цепи от основного дескр-ра через все компоненты вектора Айлиффа, после чего и будет получен адрес требуемого элемента:
#### Принципы выделения памяти под динамические массивы
1. **Постепенное увеличение памяти**: При необходимости расширения массива память увеличивается вдвое или крупными блоками (например, на 10, 20, 100 элементов), чтобы минимизировать частоту вызовов системных функций выделения памяти.
2. **Обязательное освобождение памяти**: После завершения работы с динамическим массивом память должна быть явно освобождена, чтобы избежать утечек.
3. **Контроль границ**: Необходимо следить за выходом индексов за границы выделенной памяти, чтобы избежать ошибок времени выполнения.
4. **Использование указателей**: Динамические массивы реализуются через указатели, что позволяет управлять памятью гибко, но требует аккуратного обращения с адресами.
5. **Фрагментация памяти**: При частом выделении и освобождении памяти может возникнуть фрагментация, когда свободные блоки разбросаны и не могут быть использованы эффективно. Для снижения этого эффекта применяются алгоритмы, такие как **алгоритм близнецов** или **алгоритм парных меток**.
6. **Алгоритмы выделения памяти**:
- **First fit** — выделяется первый подходящий блок.
- **Best fit** — выделяется блок минимального подходящего размера.
- **Buddy system (алгоритм близнецов)** — память делится на блоки размером 2^n, что упрощает объединение освобождённых блоков.
7. **Сборка мусора**: В некоторых случаях используется автоматическое управление памятью, включая маркировку и сборку мусора, особенно в языках высокого уровня.
Таким образом, выделение памяти под динамические массивы требует баланса между производительностью, гибкостью и надёжностью, с учётом возможных ошибок и ограничений системы.
-----
## 4. Методы управления динамической памятью. Способ учета свободной памяти, дисциплины выделения памяти по запросу: first fit, best fit ,алгоритм близнецов. Способы утилизации освобожденной памяти.
#### Методы управления динамической памятью.
Дисциплины выделения памяти
Две основные:
"самый подходящий (best fit) и "первый подходящий" (first fit)
По дисциплине "самый подходящий" выделяется тот свободный участок, размер которого равен запрошенному или превышает его на минимальную величину.
По дисциплине "первый подходящий" выделяется первый же найденный свободный участок, размер которого не меньше запрошенного (эффективнее)
#### Способ учета свободной памяти, дисциплины выделения памяти по запросу: first fit, best fit ,алгоритм близнецов.
__способ учета свободной памяти__
Методы учета свободной памяти основываются на
принципах:
• битовой карты
• списков свободных блоков
В методах битовой карты создается "карта" памяти - массив бит, в кот. каждый однобитовый элемент соответствует единице доступной памяти и отражает ее состояние: 0 - свободна, 1 - занята.
Если единица распределения это единица адресации (байт), то карта памяти занимает 1/8 часть всей памяти. При единице распределения 16 байт -1/128. Карта может рассматриваться как строка бит, тогда поиск участка памяти для выделения выполняется как поиск в этой строке подстроки нулей, требуемой длины.
• При использовании связных списков в системе есть переменная, в кот. хранится адрес первого свободного участка.
• В начале первого свободного участка записывается его размер и адрес следующего свободного участка.
__Best fit__ – увеличивает фрагментацию памяти
При использовании __first fit__
с линейным двунаправленным списком возникает специфическая проблема:
• при просмотре списка с одного и того же места большие блоки, расположенные ближе к началу, будут чаще удаляться, т.о., мелкие блоки будут иметь тенденцию скапливаться в начале списка - увеличивается среднее t-мя поиска.
• Для устранения - просматривать список то в одном направлении, то в другом. Еще проще – сделать список кольцевым, каждый поиск начинать с того места, где мы остановились в прошлый раз. В это же место добавляются освободившиеся блоки. В результате список очень эффективно перемешивается и никакой «антисортировки» не возникает.• В ситуациях, когда мы размещаем блоки нескольких фиксированных размеров, алгоритмы best fit оказываются лучше. Однако библиотеки распределения памяти рассчитывают на худший случай, и в них обычно используются алгоритмы first fit.
• В случае работы с блоками нескольких фиксированных размеров напрашивается такое решение: создать для каждого типоразмера свой список. Это избавляет программиста от необходимости выбирать между first и best fit, устраняет поиск в списках как явление... короче, решает сразу много проблем.
__Алгоритм близнецов__
Вариант подхода для случая, когда различные размеры блоков являются степенями 2-ки (512 байт, 1Кб, 2К и т.д.) Мы ищем блок требуемого размера в соответствующем списке. Если этот список пуст, то берем список блоков вдвое большего размера. Получив блок вдвое большего размера, мы делим его пополам. Ненужную половину помещаем в соответствующий список свободных блоков. Любопытно, что нам совершенно неважно, получили ли мы этот блок просто из соответствующего списка, или же делением пополам вчетверо большего блока, и далее по рекурсии. Одно из преимуществ этого метода состоит в простоте объединения блоков при их освобождении. Действительно, адрес блока-близнеца получается простым инвертированием соответствующего бита в адресе нашего блока. Нужно только проверить, свободен ли этот близнец. Если он свободен, то мы объединяем братьев в блок вдвое большего размера, и т.д.
• Алгоритм близнецов значительно снижает фрагментацию памяти и резко ускоряет поиск блоков. Наиболее важным преимуществом этого подхода является то, что даже в наихудшем случае время поиска не превышает __О(log(Smax)-log(Smin))__, где Smax Smin - соответственно максимальный и минимальный размеры используемых блоков. Это делает алгоритм близнецов труднозаменимым для ситуаций, когда необходимо гарантированное время реакции – напр., для задач реального времени. Часто этот алгоритм или его варианты используются для выделения памяти внутри ядра ОС. Например, функция kmalloc, используемая в ядре ОС Linux, основана именно на алгоритме близнецов.
• Если мы знаем о блоке его начальный адрес и размер (при выделении памяти «второго рода», т.е. когда размер освобождаемого блока передается как параметр процедуры FreeMem) или когда дескриптор блока содержит только его длину, то это очень плохая ситуация. Т.к. для объединения блока с соседями необходимо найти их в списке свободных блоков, или же убедиться, что там их нет – т.е. просмотр всего списка.
• Гораздо проще запоминать в дескрипторе блока указатели на дескрипторы соседних блоков. Такой метод называется алгоритмом парных меток и состоит в том, что мы добавляем к каждому блоку по два слова памяти.
• Именно слова, а не байта. Дело в том, что требуется добавить достаточно места, чтобы хранить там размер блока в байтах или словах. Обычно такое число занимает столько же места, сколько и адрес, а размер слова обычно равен размеру адреса.
#### Способы утилизации освобожденной памяти.
__утилизация освобожденной памяти__
• При явных запросах память должна быть освобождена явным образом.
• При представлении памяти на битовой карте: сбросить в 0 биты, соответствующие освобожденным кадрам.
• При исп-нии списков блоков: освобожденный участок д. б. включен в список + при образовании в памяти двух смежных свободных блоков необходимо слить их в один своб. блок суммарного размера. (Задача упрощается при упорядочении списка своб. блоков по адресам памяти).
• __В системах без явного освобождения памяти__:
• 1) система не приступает к освобождению, пока свободной памяти совсем не останется. ( «сборка мусора»). Алгоритм сборки мусора обычно бывает двухэтапным. На первом этапе осуществляется маркировка (пометка) всех блоков, на которые указывает хотя бы один указатель. На втором этапе все неотмеченные блоки возвращаются в свободный список, а метки стираются. (недостаток метода - расходы на него увеличиваются по мере уменьшения размеров свободной области памяти).
• 2) освобождается любой блок, как только он перестает использоваться. Реализуется посредством счетчиков ссылок: при 0 - блок не используется. Блок возвращается в свободный список.
• + предотвращает накопление мусора, не требует большого числа оперативных проверок во время обработки данных;
• - 1) когда все связи, идущие извне блоков в циклическую структуру, будут уничтожены, НО если зарезервированные блоки образуют циклическую структуру, то счетчик ссылок каждого из них не равен 0 ????; 2) требуются лишние затраты времен и памяти на ведение счетчиков ссылок.
• 3) __метод «Уплотнение»__:
осуществляется путем физического передвижения блоков данных с целью сбора всех свободных блоков в один большой блок.
• + после применения выделение памяти по запросам упрощается;
• - серьезная проблема - переопределение указателейметод «Уплотнение»:
• Механизма освобождения памяти в методе уплотнения (восстановления) совсем нет. Используется механизм маркировки, отмечающий блоки, используемые в данный момент, затем используется уплотнитель, кот. собирает неотмеченные блоки в один большой блок в одном конце области памяти.
• - 3 просмотра памяти >> затраты времени
• + повышенная скорость резервирования в опред. усл. м. компенсировать этот недостаток
__Практическая эффективность__ методов зависит от частоты запросов,
статистического распределения размеров запрашиваемых блоков, способа использования системы - групповая обработка или стратегия обслуживания при управлении вычислительным центром
-----
## 5. Стек. Доступ к элементу стека, адресация элемента. Алгоритмы исключения и включения элемента стека. Варианты конкретной реализации стека, оценка ее эффективности. **Функции** для реализации операций над стеком.
#### Стек.
***Стек*** - *АТД* (абстрактный тип данных), последовательность переменной длины, включение и исключение из которого происходят с одной стороны - его вершины.
Стек функционирует по принципу: последним пришел - первым вышел, то есть, Last In - First Out (*LIFO*).
Логически стек представляется:
▸ Верхняя граница стека
▸ Вершина стека
▸ Нижняя граница стека
#### Доступ к элементу стека, адресация элемента.
Согласно тексту лекций:
---
### **Доступ к элементу стека**
- Стек — структура с **доступом только к верхнему (последнему) элементу** (вершине).
- Доступ к другим элементам без извлечения верхних **невозможен** в классической реализации.
- Операции:
- **Push** — добавление на вершину,
- **Pop** — извлечение с вершины,
- **Peek** — чтение вершины без извлечения.
> *«Если стек реализован на основе вектора, то при работе доступен только верхний элемент»* (стр. 72).
---
### **Адресация элемента в стеке**
1. **При реализации вектором (массивом)**:
- Адрес вершины хранится в указателе **PS (Pointer Stack)**.
- Адрес элемента вычисляется как:
\[ \text{Addr} = \text{PS} \] (для вершины).
- При доступе к i-му элементу снизу требуется извлечение i-1 элементов.
2. **При реализации связным списком**:
- Элементы связаны указателями.
- Адрес элемента определяется переходом по цепочке ссылок от вершины.
3. **Дескриптор стека** содержит:
- **AUB** (Address Up Bond) — верхняя граница,
- **ALB** (Address Low Bond) — нижняя граница,
- **PS** — указатель вершины,
- **L** — длина элемента (стр. 72).
---
**Источник**: Лекции 5.2, 6 (стр. 70–75).
#### Алгоритмы исключения и включения элемента стека. **Функции** для реализации операций над стеком.
***Включение***
```
if PS = AUB // стек уже полон
сообщить «переполнение»;
отказ;
else
PS := PS + L; // сдвинуть указатель ВВЕРХ
память[PS] := элемент; // записать данные
end if;
```
***Исключение***
```
if PS < ALB // стек пуст
сообщить «опустошение»;
отказ;
else
элемент := память[PS]; // прочитать вершину
PS := PS – L; // сдвинуть указатель ВНИЗ
вернуть элемент;
end if;
```
#### Варианты конкретной реализации стека, оценка ее эффективности.
##### Реализация стека вектором
При включении элемента (Push - заталкивать): сначала перемещается «вверх» указатель на длину типа данных, затем по значению указателя в стек помещается информация. Если указатель выходит за верхнюю границу стека, то стек переполняется.
При исключении элемента (Pop - выскакивать): по указателю стека прочитывается информация об исключаемом элементе, затем указатель смещается «вниз» на один элемент. Если указатель выходит за нижнюю границу стека, то стек пуст. Для хранения стека отводится сплошная область памяти. Граничные адреса стека это параметры физической структуры.
Физическая структура обычно дополняется дескриптором стека
##### Реализация стека в виде односвязного линейного списка
Дескриптор
__Достаточно__:
* Указатель PS на вершину стека
* Описание данных
__Опционально__:
* Количество элементов стека
При этой реализации теоретически объем стека ограничен только объемом доступной
оперативной памяти
-----
## 6. Очереди. Алгоритмы включения, исключения элемента и очистки очереди. Конкретная реализация очереди, оценка эффективности различного представления очереди. **Функции** для реализации операций над очередью.
#### Очереди.
Очередь - последовательность переменной длины, включение в которую идёт с одной стороны, а исключение с другой - его вершины.
#### Алгоритмы включения, исключения элемента и очистки очереди.
При включении элемента он располагается по адресу Pin , а сам указатель Pin
перемещается на «пустое» место. Очистка очереди: Pin = Q1 , Pout = Q1 .
Для исключения переполнения производят сдвиг эл-тов к голове при каждом
исключении из очереди, тогда переполнение будет только, если все m мест заняты.
Но на эти последовательные сдвиги тратится время.
#### **Функции** для реализации операций над очередью.
***Включение***
Выделить память PtrN для нового элемента En
```
If К = 0 Then Pout <- N
Else F (Pin) <- N
Pin <- N
{теперь он последний}
D(Pin) <- Data
F(Pin) <- Nil {следующего - нет}
К + 1
```
***Исключение***
```
{ исключение головы очереди }
if K <> 0 then { очередь не пуста }
R <- F(Pout) { запоминаем адрес следующего элемента }
F(Pout) <- E { голова указывает на список свободных элементов }
E <- Pout { добавляем бывшую голову в free‑list }
Pout <- R { сдвигаем голову на следующий элемент }
K <- K - 1 { уменьшаем число элементов }
if K = 0 then
Pin <- Nil { если элементов не осталось – хвост тоже Nil }
else
{ отказ от исключения – очередь пуста }
```
***Очистка***
```
{ очистка очереди: все элементы в free‑list }
F(Pin) <- E { хвост очереди «цепляем» к списку свободных }
E <- Pout { начало free‑list – бывшая голова очереди }
Pin <- Nil
Pout <- Nil
K <- 0
```
Согласно тексту лекций, **конкретная реализация очереди** и **оценка эффективности различного представления очереди** изложены следующим образом:
---
### **1. Конкретная реализация очереди**
#### **А. Очередь на основе вектора (массива)**
> Для хвоста и головы очереди используют два указателя `PIN` и `POUT` (хвост и голова). То есть, исключается элемент с адресом Pout и включается элемент по адресу Pin. При моделировании простейшей линейной очереди на основе вектора выделяется последовательность m мест длиной L под каждый элемент очереди.
> *(стр. 78)*
**Схема:**
```
Q1 | Q2 | ... | X | X | X |
... | ... | ... | ... | X | X |
Рout ▼ Pin
```
> Количество элементов в очереди:
> \[ K = \frac{Pin - Pout}{L} \]
> *(стр. 78)*
**Алгоритмы:**
- **Очистка очереди**: `Pin = Q1, Pout = Q1`.
- **Переполнение**: наступает при `Pin = Qm + 1`, независимо от состояния Pout.
#### **Б. Кольцевая очередь на основе вектора**
> Если Pin = Qm + 1, то производят коррекцию: Pin = Q1, если Pout > Q1, T.e., здесь может быть Pin < Pout, Pin > Pout и Pin = Pout – пустая (но и заполненная).
> *(стр. 78)*
**Схема:**
```
Q1 | Q2 | ... | X | X | X |
X | X | ... | ... | X | X |
Pin ▼ Pout
```
#### **В. Очередь на основе односвязного линейного списка**
> Большинство перечисленных проблем устраняется при реализации очереди на основе односвязных линейных списков.
> *(стр. 79)*
**Дескриптор:**
```
| Pout | Pin | K | Описание элемента |
```
> Исходное состояние очереди:
> `Pout = Nil`, `Pin = Nil`, `K = 0`.
> *(стр. 79)*
**Алгоритмы (стр. 79–80):**
1. **Вставка элемента с адресом N**:
```
1 If K = 0 Then Pout ← N
2 Else F (Pin) ← N
3 Pin ← N {теперь он последний}
4 D(Pin) ← Data
5 F(Pin) ← Nil {следующего - нет}
6 K + 1
```
2. **Исключение элемента**:
```
1 If K <> 0 {если очередь не пуста}
2 Then
3 P ← F (Pout)
4 F (Pout) ← E {пополнение списка свободных элементов}
5 E ← Pout
6 Pout ← P
7 K = K-1
8 If K = 0 Then Pin ← Nil
9 Else {отказ от исключения - очередь пуста}
```
3. **Очистка очереди**:
```
1 F(Pin) ← E {пополнение списка свободных элементов}
2 E ← Pout
3 Pin ← Nil
4 Pout ← Nil
5 K ← 0
```
---
### **2. Оценка эффективности различного представления очереди**
#### **А. Сравнительная таблица эффективности**
(на основе анализа лекций, явной таблицы нет, но критерии приведены в тексте)
| Критерий | Очередь на векторе (линейная) | Очередь на векторе (кольцевая) | Очередь на связном списке |
|----------|-------------------------------|--------------------------------|----------------------------|
| **Память** | Фиксированный размер, возможна фрагментация | Фиксированный размер, лучше использование памяти | Динамическое выделение, накладные расходы на указатели |
| **Время добавления** | O(1), но при переполнении — сдвиг или отказ | O(1) | O(1) |
| **Время удаления** | O(1), но при сдвиге — O(n) | O(1) | O(1) |
| **Переполнение** | Частое, требует контроля границ | Контроль заполнения, возможно затирание головы | Ограничено только доступной памятью |
| **Гибкость** | Низкая (фиксированный размер) | Низкая (фиксированный размер) | Высокая (динамический размер) |
| **Реализация** | Простая | Сложнее из-за кольцевой логики | Средней сложности, требует работы с указателями |
#### **Б. Конкретные оценки из лекций**
1. **Для очереди на векторе (линейной)**:
> Переполнение очереди наступает при Pin = Qm + 1, независимо от состояния Pout. Для исключения переполнения производят сдвиг эл-тов к голове при каждом исключении из очереди, тогда переполнение будет только, если все m мест заняты. Но на эти последовательные сдвиги тратится время.
> *(стр. 78)*
2. **Для кольцевой очереди**:
> В кольцевой структуре нет необходимости сдвигать элементы, но сложнее алгоритмы включения и исключения элементов, а радикально проблема переполнения все равно не решается, т. к. при заполнении очереди следующий элемент будет затирать первый, то есть необходимо проверять заполнение очереди.
> *(стр. 79)*
3. **Для очереди на списке**:
> Большинство перечисленных проблем устраняется при реализации очереди на основе односвязных линейных списков.
> *(стр. 79)*
**Преимущества**:
- Динамическое изменение размера.
- Нет проблемы сдвига элементов.
- Переполнение происходит только при исчерпании всей памяти.
**Недостатки**:
- Дополнительные расходы памяти на хранение указателей.
- Время на выделение/освобождение памяти.
#### **В. Применение в вычислительных системах**
> Кольцевая очередь в BC – буфер клавиатуры в BIOS IBM PC. При нажатии на любую клавишу генерируется прерывание 9. Обработчик этого прерывания читает код нажатой клавиши и помещает его в буфер клавиатуры – в конец очереди. Коды нажатых клавиш могут накапливаться в буфере клавиатуры, прежде чем они будут прочитаны программой. Программа при вводе данные с клавиатуры обращается к прерыванию 16Н. Обработчик этого прерывания выбирает код клавиши из буфера – из начала очереди – и передает в программу.
> *(стр. 80–81)*
> Очередь – одно из ключевых понятий в многозадачных ОС (Windows NT, Unix, OS/2, EC и др.). Ресурсы ВС (процессор, ОП, ВУ и т.п.) используются всеми задачами, одновременно выполняемыми в среде такой ОС. Многие виды ресурсов не допускают одновременного использования разными задачами, такие ресурсы предоставляются задачам поочередно. Т. о., задачи, претендующие на использование того или иного ресурса, выстраиваются в очередь к этому ресурсу. Эти очереди обычно приоритетные, но, часто применяются и FIFO- очереди, т. к. это единственная логич. организация очереди, кот. гарантированно не допускает постоянного вытеснения задачи более приоритетными.
> *(стр. 81)*
---
### **3. Итоговые рекомендации по выбору реализации**
| Ситуация | Рекомендуемая реализация | Причина |
|----------|--------------------------|---------|
| Фиксированный размер, высокая скорость, простая логика | **Кольцевая очередь на векторе** | Минимизация накладных расходов, быстрота операций O(1) |
| Динамический размер, частая вставка/удаление, память не критична | **Очередь на односвязном списке** | Гибкость, отсутствие проблемы переполнения |
| Системное программирование, буферы устройств | **Кольцевая очередь на векторе** | Используется в BIOS, драйверах |
| Многозадачные ОС, планировщики | **Очередь на списке (часто с приоритетами)** | Удобство управления динамическими процессами |
---
**Источник**: Лекции 5.2, 6 (стр. 76–82, 90–93).
-----
## 7. Понятие дека, принципы обработки. Варианты реализаций.
#### Понятие дека, принципы обработки.
***Дек*** (от англ, deque double ended queen, т. e., очередь с двумя концами) - это последовательный список, в кот. включение и исключение элементов возможны с
любого конца.
Логическая и физическая структуры дека соответствуют структуре обычной очереди, но применительно к деку говорят вместо хвоста и головы о левом (I) и правом ( R) концах дека.
#### Варианты реализаций.
### **1. Дек на основе массива (вектора) с кольцевой организацией**
> Для хвоста и головы очереди используют два указателя `PIN` и `POUT` (хвост и голова). То есть, исключается элемент с адресом Pout и включается элемент по адресу Pin. При моделировании простейшей линейной очереди на основе вектора выделяется последовательность m мест длиной L под каждый элемент очереди.
> В кольцевой структуре нет необходимости сдвигать элементы, но сложнее алгоритмы включения и исключения элементов...
> *(стр. 78–79)*
**Схема кольцевой очереди/дека:**
```
Q1 | Q2 | ... | X | X | X | ... | X | X
↑Pin ↑Pout
```
> Здесь, если Pin = Qm + 1, то производят коррекцию: Pin = Q1... T.e., здесь может быть Pin < Pout, Pin > Pout и Pin = Pout — пустая (но и заполненная).
> *(стр. 78)*
---
### **2. Дек на основе односвязного линейного списка**
> Большинство перечисленных проблем устраняется при реализации очереди на основе односвязных линейных списков.
> *(стр. 79)*
**Дескриптор дека (очереди) на списке:**
```
| Pout | Pin | K | Описание элемента |
```
> Исходное состояние очереди:
> `Pout = Nil`, `Pin = Nil`, `K = 0`.
> *(стр. 79)*
**Операции:**
- **Вставка элемента с адресом N** (стр. 79–80).
- **Исключение элемента** (стр. 79–80).
- **Очистка очереди** (стр. 80).
---
### **3. Дек на основе двусвязного ациклического списка**
> **Дек (от англ, deque double ended queen, т. е., очередь с двумя концами)** — это последовательный список, в кот. включение и исключение элементов возможны с любого конца.
> Логическая и физическая структуры дека соответствуют структуре обычной очереди, но применительно к деку говорят вместо хвоста и головы о левом (L) и правом (R) концах дека.
> *(стр. 90)*
**Структура:**
- Используются два указателя: `PL` (левый конец) и `PR` (правый конец).
- Каждый элемент содержит данные (`Data`) и указатель на следующий элемент (`F`).
**Алгоритмы включения/исключения** приведены на стр. 91–92:
- **Включение справа**: `If K = 0 Then PL ← N Else F(PR) ← N; PR ← N; ...`
- **Включение слева**: `If K = 0 Then PR ← N Else F(N) ← PL; PL ← N; ...`
- **Исключение слева**: `If K <> 0 Then P ← F(PL); F(PL) ← E; E ← PL; PL ← P; ...`
- **Исключение справа**: требует последовательного прохода по деку слева (для односвязного списка) или упрощается для двусвязного.
---
### **4. Дек на основе двусвязного кольцевого списка**
> **Кольцевой двусвязный список**: объединить два пустых указателя, указатель конца не нужен, а указатель начала м. б. в любом месте.
> *(стр. 98)*
**Структура:**
Элементы связаны двунаправленно, список замкнут в кольцо. Указатель начала (`PB`) может находиться на любом элементе.
---
### **5. Дек с ограниченным выходом**
> **Организация дека с ограниченным выходом на основе двусвязного линейного списка**
> *(заголовок стр. 92)*
**Схема:**
```
удаление вход → [первый элемент] ↔ [элемент] ↔ ... ↔ [последний элемент] ← добавление вход
```
> Пример системной поддержки — организация буфера ввода в языке REXX… Дополнительная операция `PUSH` — запись строки в начало буфера — превращает буфер в дек с ограниченным выходом.
> *(стр. 93)*
---
### **6. Сравнение реализаций (сводка)**
| Реализация | Преимущества | Недостатки | Где используется |
|------------|--------------|------------|------------------|
| **Массив (кольцевой)** | Быстрый доступ, непрерывная память | Ограниченный размер, сложность управления переполнением | Статические очереди с фиксированным размером |
| **Односвязный список** | Динамический размер, простота удаления с начала | Сложность удаления с конца (требуется проход) | Динамические структуры с частыми операциями в начале |
| **Двусвязный список** | Удобное удаление и добавление с обоих концов | Дополнительная память на второй указатель | Универсальные деки с частыми операциями с двух сторон |
| **Двусвязный кольцевой** | Упрощённая логика, нет особых случаев для концов | Сложнее отладка из-за цикличности | Системные буферы, циклические обработчики |
| **Дек с ограниченным выходом** | Контроль над дисциплиной доступа | Ограниченная гибкость | Специализированные буферы (например, в языке REXX) |
---
### **7. Пример алгоритмов для дека на двусвязном списке**
#### **Включение элемента справа** (стр. 91):
```
1 If K = 0 Then PL ← N Else F(PR) ← N
2 PR ← N {теперь он справа}
3 D(PR) ← Data
4 F(PR) ← Nil {и он последний}
5 K ← K + 1
```
#### **Включение элемента слева** (стр. 91):
```
1 If K = 0 Then PR ← N Else F(N) ← PL
2 PL ← N {теперь он слева}
3 D(PL) ← Data
4 K ← K + 1
```
#### **Исключение элемента слева** (стр. 91–92):
```
1 If K <> 0
2 Then
3 P ← F(PL)
4 F(PL) ← E {пополнение списка свободных элементов}
5 E ← PL
6 PL ← P
7 K = K - 1
8 Else {отказ от исключения — дек пуст}
```
-----
## 8. Двусвязный список. Алгоритм включения, исключения элемента из двусвязного списка. (Реализация конкретной **функцией**). Многосвязные списки.
#### Двусвязный список.
***Двусвязный список***, в котором каждый элемент имеет два указателя: вперед __(F)__ и назад __(B)__. В структуру этого списка добавляется указатель конца __(PE)__. Начало и конец в этом списке логически эквивалентны, так как доступ к элементу списка имеется с любого конца .
#### Алгоритм включения, исключения элемента из двусвязного списка. (Реализация конкретной **функцией**)
##### Включение элемента в двусвязный список
Пусть `UK` — адрес узла, относительно которого вставляем, `N` — адрес нового узла.[^1]
###### Вставка перед узлом UK
```text
procedure InsertBefore(UK, N):
B(N) <- B(UK)
B(UK) <- N
F(N) <- UK
F(B(N)) <- N
```
###### Вставка после узла UK
```text
procedure InsertAfter(UK, N):
F(N) <- F(UK)
B(N) <- UK
B(F(UK)) <- N
F(UK) <- N
```
###### Исключение узла из двусвязного списка
Пусть `UK` — адрес удаляемого узла.[^1]
```text
procedure DeleteNode(UK):
B(F(UK)) <- B(UK)
F(B(UK)) <- F(UK)
{дальше UK можно включить в список свободных элементов}
```
#### Многосвязные списки.
В более общем случае каждый элемент связного списка может содержать произвольное конечное число связок, причем, различное в различных элементах. В этом случае получается __многосвязный список__, каждый элемент которого входит одновременно в несколько разных односвязных списков. Такие списки еще называют __прошитыми (мультисписками)__.
-----
## 9. Рекурсивные процедуры и функции. Критерии выбора для разработки рекурсивных или итеративных алгоритмов.
### **1. Определение рекурсии**
> **Рекурсивный** называют **объект, частично состоящий или определяемый с помощью самого себя**.
> *(стр. 148)*
---
### **2. Виды рекурсии**
> Рекурсия может быть **прямой (или явной)** и **косвенной (или неявной)**.
> **Прямая** рекурсия заключается в **прямом** вызове подпрограммой самой себя.
> **Косвенная** рекурсия может вызывать себя не прямо, а через **другую функцию**, то есть, одна функция вызывает вторую функцию, а вторая, в свою очередь, вызывает первую.
> *(стр. 149)*
---
### **3. Структура рекурсивной подпрограммы (фрейм активации)**
> Совокупность данных для одной активации подпрограммы — **фрейм активации**.
> **Фрейм активации** включает:
> - копию всех локальных переменных;
> - копии параметров, переданных по значению;
> - адреса параметров-переменных (по ссылке) и параметров-констант;
> - служебную информацию (около 12 байт...).
> *(стр. 150)*
---
### **4. Проблемы использования рекурсии**
> **Каждое** обращение к рекурсивной подпрограмме при **каждом** вызове порождает «поколение» локальных переменных и параметров, что при глубокой рекурсии может привести к переполнению стека.
> *(стр. 149)*
> рекурсивные подпрограммы м. приводить к не заканчивающимся вычислениям, поэтому необходимо следить тем, чтобы в них обязательно был нерекурсивный выход.
> *(стр. 151)*
---
### **5. Критерии выбора: рекурсия или итерация?**
#### **А. Когда рекурсия предпочтительна:**
1. **Для задач, где данные определяются рекурсивно**:
> Рекурсивные подпрограммы следует применять для задач, где данные определяются в терминах рекурсий.
> *(стр. 162)*
2. **Для алгоритмов «разделяй и властвуй» (декомпозиции)**:
> Алгоритмы, основанные на принципе «разделяй и властвуй» (еще называются алгоритмы, использующие **метод декомпозиции** или **разбиения**) являются по своей природе **рекурсивными** и их переводить в итеративную форму **не следует.**
> *(стр. 170)*
**Примеры**: быстрая сортировка Хоара, сортировка слиянием, задача о Ханойских башнях.
3. **Когда рекурсивная версия проще и эффективнее**:
> Если на практике сравнить коды программ и время их выполнения, то в данном случае вы увидите, что рекурсивный алгоритм будет лучше нерекурсивного и по простоте, и по времени выполнения. По времени выполнения рекурсивный алгоритм работает в 7-10 раз быстрее.
> *(стр. 174)*
#### **Б. Когда итерация предпочтительна:**
1. **При опасности переполнения стека**:
> При создании рекурсивных подпрограмм также важно убедиться, что максимальная глубина рекурсии не только конечна, но и достаточно мала.
> *(стр. 151)*
2. **Для простых линейных или хвостовых рекурсий**:
> Программы, в которых следует избегать алгоритмической рекурсии можно охарактеризовать некоторой схемой, отражающей их строение:
> \( P \equiv \text{If B Then S; P End} \)
> \( P \equiv \text{S; If B Then P End} \)
> Такие схемы естественны в ситуации, где вычисляемые значения определяются с помощью рекуррентных соотношений.
> *(стр. 162)*
**Пример**: вычисление факториала или чисел Фибоначчи лучше реализовать итеративно.
> В общем-то, программы, построенные по схеме переписывать, руководствуясь схемой:
> \( P = [X := X_0; \text{ While B Do S End}] \).
> *(стр. 166)*
3. **Когда рекурсия приводит к экспоненциальной сложности**:
> Вычисление чисел Фибоначчи… приводит к следующей рекурсивной подпрограмме… Вычисление по этой схеме приводит при каждом обращении к рекурсии еще к двум обращениям, то есть, число вызовов растет экспоненциально. Лучше сделать итеративно.
> *(стр. 167–168)*
---
### **6. Сравнение рекурсии и итерации на примерах**
#### **Пример 1: Факториал**
> Рекурсивно:
> ```
> long double fact(int N)
> { if(N < 0) return 0;
> if (N == 0) return 1;
> else return N * fact(N - 1);
> }
> ```
> Итеративное вычисление:
> ```
> long double fact(int N)
> { if (N < 0) return 0;
> if (N == 0) return 1;
> long double result = 1;
> for (int i = 1; i <= N; i++)
> { result *=i; }
> return result;
> }
> ```
> *(стр. 164–165)*
#### **Пример 2: Быстрая сортировка (Хоара)**
> Для сравнения можно взять алгоритмы рекурсивный и не рекурсивный… Сложность этого алгоритма равна \( O(n \log_2 n) \).
> *(стр. 169)*
> **Вывод**: для таких алгоритмов рекурсия естественна и эффективна.
---
### **7. Итоговые критерии выбора**
| Критерий | Рекурсия | Итерация |
|----------|----------|----------|
| **Структура данных** | Рекурсивная (деревья, графы, выражения) | Линейная (массивы, списки) |
| **Алгоритм** | «Разделяй и властвуй», декомпозиция | Последовательная обработка, циклы |
| **Сложность** | Логарифмическая, \( O(\log n) \) | Линейная, \( O(n) \) (если рекурсия приводит к экспоненциальному росту) |
| **Память** | Требует стека для фреймов, риск переполнения | Фиксированное использование памяти |
| **Читаемость** | Более краткая и ясная для рекурсивных задач | Более привычна для простых циклических задач |
| **Быстродействие** | Может быть выше за счёт учёта структуры (пример: Ханойские башни) | Часто выше за счёт отсутствия накладных расходов на вызовы |
---
-----
## 10. Рекурсивные типы данных. Примеры описаний и использования.
#### Рекурсивные типы данных.
***Рекурсивно определённым*** называют объект, частично состоящий или определяемый с помощью самого себя
Рекурсию можно представить как некоторую композицию __P__ из самой себя и множества операторов __S__, не содержащих __P__, то есть
$$ P => P[S, P]$$
#### Примеры описаний и использования.
• ***Прямая*** рекурсия заключается в прямом вызове подпрограммой самой себя.
• ***Косвенная*** рекурсия может вызывать себя не прямо, а через другую функцию, то есть, одна функция вызывает вторую функцию, а вторая, в свою очередь, вызывает первую.
• При использовании рекурсии:
• каждое обращение к рекурсивной подпрограмме при каждом вызове порождает «поколение» локальных переменных и параметров, что при глубокой рекурсии может привести к переполнению стека.
• Наиболее известные примеры рекурсии:
1. Натуральные числа:
а) число 0 – натуральное;
б) число, следующее за натуральным есть натуральное.
2. Деревья:
а) 0 есть нулевое (пустое) дерево;
б) если t1 и t2 – деревья, то построение, содержащее вершину с двумя ниже расположенными деревьями опять же дерево;
3. Функция факториала n! (для неотицат. целых чисел)
а) 0! = 1;
б) n > 0 n! = n * (n - 1)!
-----
## 11. Понятие абстрактных типов данных. Обработка абстрактных типов данных (АТД). Принципы создания программ с использованием АТД.
#### Понятие абстрактных типов данных.
**АТД** определяется как математическая модель с совокупностью операторов (подпрограмм), определенных в рамках этой модели, т. о.
**АТД** – это тип, для которого описание значений и операций, выполняемых над ними, отделено от представления значений и реализации операций
Согласно тексту лекций, **обработка абстрактных типов данных (АТД)** и **принципы создания программ с использованием АДТ** изложены следующим образом:
---
### **1. Определение АТД**
> **АТД** определяется как **математическая модель с совокупностью операторов (подпрограмм), определенных в рамках этой модели**, т. о. **АТД** – это тип, для которого описание значений и операций, выполняемых над ними, отделено от представления значений и реализации операций.
> *(стр. 183)*
---
### **2. Пример АТД в задаче раскраски графа**
Для задачи раскраски графа **АТД – это граф (GRAPH)**, для которого необходимы операторы, выполняющие следующие действия:
1. Выбрать первую незакрашенную вершину;
2. Проверить существование ребра между двумя вершинами;
3. Пометить вершину цветом;
4. Выбрать следующую незакрашенную вершину.
> *(стр. 184)*
---
### **3. Принципы создания программ с использованием АТД**
Процесс программирования с использованием АТД включает следующие этапы:
#### **Этап 1: Создание модели и неформального алгоритма**
> Создать модель исходной задачи, привлекая необходимые математические модели (например, теорию графов) и разработать неформальный алгоритм.
> *(стр. 185)*
#### **Этап 2: Запись на псевдоязыке и определение АТД**
> Записать алгоритм на псевдоязыке, создать АТД для каждого зафиксированного типа данных (кроме простых) и задать имена подпрограмм (процедур и функций) обработки этих данных.
> *(стр. 185)*
#### **Этап 3: Реализация АТД и написание программы**
> Реализовать АТД конкретной структурой данных, написать процедуры их обработки и преобразовать псевдокод в программу на языке программирования.
> *(стр. 185)*
---
### **4. Схема этапов разработки алгоритмов с использованием АТД**
> | Математическая модель | Абстрактные типы данных | Структуры данных |
> |-----------------------|-------------------------|------------------|
> | Неформальные алгоритмы | Программа на псевдозыке | Программа на языке программирования |
> *(стр. 186)*
---
### **5. Рекомендации по практике программирования с АТД**
> **Планировать этапы разработки программ**. Это организует и дисциплинирует процесс создания конечной программы, которая будет проще в отладке и в дальнейшей поддержке и сопровождении.
> **Применять инкапсуляцию**, то есть помещать все подпрограммы, реализующие АТД, в одно место программы.
> **Использовать и модифицировать уже существующие программы.** Не начинать «с нуля», пользоваться своими наработками и думать, где и как можно применить созданные вами программы (возможны непредвиденные варианты).
> **Стараться создавать программы-инструменты**, то есть, такие программы, которые будут универсальными, с широким спектром применения.
> *(стр. 187)*
---
### **6. Пример псевдокода с использованием АТД**
Для задачи раскраски графа («жадный» алгоритм) приводится псевдокод, использующий АТД **GRAPH** и **SET**:
```
Procedure Greedy (var G : GRAPH, var NEWCLR : SET);
{Greedy присваивает переменной NEWCLR (новый цвет) множество вершин графа G, кот. можно окрасить в один цвет}
Begin
NEWCLR := 0;
For каждой незакрашенной вершины V из G do
If V не соединена с вершинами из NEWCLR Then
Begin
пометить V цветом;
добавить V в NEWCLR;
End;
End;
```
> *(стр. 182)*
---
---
**Источник**: Лекции 7 (стр. 182–187).
-----
## 12. Разреженные матрицы, примеры их использования. Методы представления и обработки разреженных матриц. Критерии выбора алгоритмов для стандартного или разреженного представления и обработки матриц.
#### Разреженные матрицы, примеры их использования.
Разреженние матрицы используются в обработки графов низкой связности и решений систем уравнений
#### Методы представления и обработки разреженных матриц.
### **1. Ленточные и профильные схемы хранения**
- **Ленточные матрицы**: хранятся только элементы внутри ленты вокруг главной диагонали. Для симметричных матриц достаточно хранить верхнюю или нижнюю полуленту.
- **Профильная схема (схема Дженнингса)**: используется для симметричных матриц с переменной шириной ленты. Элементы оболочки хранятся в одномерном массиве `AN`, а массив указателей `IA` содержит позиции диагональных элементов.
Пример (стр. 55):
```
AN: 1 2 6 3 7 0 4 8 5
IA: 1 2 4 7 9
```
---
### **2. Связные схемы хранения (Кнута и КРМ)**
- **Схема Кнута (1968 г.)**: для каждого ненулевого элемента хранятся:
1. Значение элемента
2. Строковый индекс
3. Столбцовый индекс
4. Указатель на следующий ненулевой элемент в строке
5. Указатель на следующий ненулевой элемент в столбце
6. Указатели входа для строк и столбцов
- **КРМ-схема (кольцевая, Рейнболдта и Местеныча)**: списки строк и столбцов закольцовываются, что уменьшает объём накладной памяти. Указатели входа включаются в кольцевые списки, что упрощает обход (стр. 58–60).
---
### **3. Разреженный строчный формат (CSR/CSC)**
- **CSR (Compressed Sparse Row)**:
- `AN` — массив значений ненулевых элементов
- `JA` — массив столбцовых индексов элементов
- `IA` — массив указателей на начало каждой строки в `AN` и `JA`
Пример (стр. 63):
```
AN: 1 4 7 5 2 8
JA: 3 4 8
IA: 1 4 6
```
- **CSC (Compressed Sparse Column)**: аналогично, но для столбцов.
---
### **4. Алгоритмы обработки разреженных матриц**
- **Сложение разреженных векторов**: используется расширенный накопитель и массив-переключатель для эффективного слияния списков индексов (стр. 64–65).
- **Скалярное умножение векторов**: применяется массив указателей `IP` для быстрого поиска совпадающих позиций (стр. 66–67).
- **Транспонирование матриц**: необходимо для удобного доступа при работе с CSR/CSC форматами.
- **Умножение разреженной матрицы на вектор**: использует заранее заполненный массив указателей для ускорения операций.
---
### **Ключевые преимущества разреженных форматов:**
- Экономия памяти (хранятся только ненулевые элементы).
- Ускорение операций (вычисления только с ненулевыми элементами).
- Поддержка динамического изменения структуры (в связных схемах).
---
Источник: Лекции 4.1, 5.1, 5.2 (стр. 53–68, 103–106).
Алгоритмы обработки разреженных матриц предусматривают действия только с
ненулевыми элементами, т. о., число операций пропорционально числу ненулевых
элементов. Отсюда следует, что имеет смысл хранить в памяти только ненулевые
элементы.
#### Критерии выбора алгоритмов для стандартного или разреженного представления и обработки матриц.
---
### **1. Степень разреженности матрицы**
- **Разреженность** определяется как отношение числа ненулевых элементов к общему числу элементов.
Матрица считается разреженной, если число ненулевых элементов выражается как $n^{g + 1}$, где __( g < 1 )__ (стр. 53).
- **Если g <= 0.2 или g >= 0.5** — матрица считается разреженной, и использование разреженных форматов оправдано.
- **Если матрица плотная** — стандартное представление (двумерный массив) эффективнее по времени и проще в реализации.
---
### **2. Объём памяти и требования к хранению**
- **Разреженные форматы** (CSR, CSC, схемы Кнута, КРМ) требуют хранения только ненулевых элементов, но добавляют служебные массивы (индексы, указатели).
Например, в CSR хранятся:
1. `AN` — значения ненулевых элементов,
2. `JA` — столбцовые индексы,
3. `IA` — указатели на строки (стр. 63).
- **Стандартное представление** требует хранения всех элементов матрицы, включая нули.
- **Критерий**: если экономия памяти за счёт исключения нулей перевешивает накладные расходы на служебные данные — выбирается разреженный формат.
---
### **3. Характер операций с матрицей**
- **Операции, эффективные для разреженных форматов**:
- Умножение матрицы на вектор,
- Сложение/вычитание разреженных матриц,
- Решение систем линейных уравнений итерационными методами,
- Транспонирование.
- **Операции, где плотное представление может быть предпочтительнее**:
- Прямые методы решения СЛАУ (например, метод Гаусса),
- Операции, требующие частого случайного доступа к элементам,
- Когда матрица небольшого размера и плотная.
---
### **4. Динамичность структуры матрицы**
- **Если структура матрицы меняется** (добавление/удаление ненулевых элементов) — **связные схемы** (Кнута, КРМ) удобнее, так как позволяют вставлять и удалять элементы без перераспределения памяти (стр. 58–60).
- **Если структура статична** — **CSR/CSC** эффективнее по памяти и скорости доступа.
---
### **5. Особенности аппаратной реализации и языка программирования**
- **Векторизация и параллелизм**: плотные матрицы лучше поддаются оптимизации под SIMD-инструкции и GPU.
- **Языки программирования**:
- В Си/С++ указательная арифметика упрощает работу с разреженными форматами,
- В Паскале/Модуле-2 строгая типизация удобна для статических структур.
---
### **6. Критерии, связанные с вычислительной сложностью**
- **Временная сложность**:
- Для разреженных алгоритмов число операций пропорционально числу ненулевых элементов (стр. 53).
- Для плотных алгоритмов — пропорционально общему числу элементов.
- **Ёмкостная сложность**: разреженные форматы экономят память, но требуют дополнительных структур.
---
### **7. Практические рекомендации из лекций**
1. **Если матрица большая (\(>10^{10}\) элементов) и разреженная** — использовать **CSR/CSC** или **ленточные схемы** (стр. 53–55).
2. **Если разреженность нерегулярна и структура динамична** — применять **связные схемы** (Кнута или КРМ) (стр. 56–60).
3. **При умножении матрицы на вектор или решении СЛАУ итерационными методами** — использовать **CSR/CSC** (стр. 62–67).
4. **Если важен минимальный объём памяти и статическая структура** — **профильная схема** (Дженнингса) для симметричных матриц (стр. 54–55).
5. **Если матрица мала или плотна** — **стандартное представление в виде двумерного массива** (лекция 2, стр. 17–24).
---
### **Итоговое правило выбора**
| Критерий | Стандартное представление | Разреженное представление |
|----------|---------------------------|----------------------------|
| **Заполнение** | > 30–50% ненулевых | < 10–20% ненулевых |
| **Размер** | Небольшой (до \(10^4\) элементов) | Большой (от \(10^6\) элементов) |
| **Структура** | Статичная, регулярная | Динамичная, нерегулярная |
| **Операции** | Прямые методы, частый доступ | Умножение на вектор, итерационные методы |
| **Память** | Не критична | Критична, требуется экономия |
-----
## 13. Деревья. Виды деревьев и способы их представления.
#### Деревья.
Дерево - иерархическая структура данных, состоящая из вершин (узлов) и ребёр (дуг), которые их соединяют.
Деревья - связные графы без циклов.
#### Виды деревьев и способы их представления.
__Представление древовидной структуры__:
* скобочное (в выражениях): __(A(B(D(I), E(J,K,L)), C(F(O),G(M,N),H( P))))__
* в виде вложенных множеств
* отступами (в программах - структура)
* в виде графа
*
-----
## 14. Двоичные деревья. Обход двоичных деревьев. Двоичные деревья поиска (ДДП). Алгоритмы поиска в ДДП. Операции включения и исключения в ДДП. (Реализация конкретной **функцией**).
#### Двоичные деревья.
***Двоичное дерево Т*** - конечный набор элементов, являющихся узлами (вершинами) дерева, такой что:
1. __Т__ - пустое или нулевое дерево
2. __Т__ состоит из корня с двумя отдельными двоичными деревьями, называющимися соответственно левым и правым поддеревьями
***Деревья степени больше 2*** называют _сильно ветвящимися деревьями_.
#### Обход двоичных деревьев.
##### Рекурсивный обход бинарного дерева. Центрированный (инфиксный)
1. Проверить, является ли текущий узел пустым
2. Рекурсивно вызвать просмотр левого поддерева
3. Вывести содержимое текущего узла
4. Рекурсивно вызвать просмотр правого поддерева
```c
void infix_tree_print(t_tree* tree)
{
if (tree != NULL)
{
infix_tree_print(tree->left);
printf("%d \n", tree->data);
infix_tree_print(tree->right);
}
}
```
##### Рекурсивный обход бинарного дерева. Обратный (постфиксный)
1. Проверить, является ли текущий узел пустым
2. Рекурсивно вызвать просмотр левого поддерева
3. Рекурсивно вызвать просмотр правого поддерева
4. Вывести содержимое текущего узла
```c
void postfix_tree_print(t_tree* tree)
{
if (tree != NULL)
{
postfix_tree_print(tree->left);
postfix_tree_print(tree->right);
printf("%d \n", tree->data);
}
}
```
##### Обход дерева без применения рекурсии
###### а) Инфиксный обход дерева
```c
void iterInorder(node *root)
{
stack *ps = createStack();
while (ps->size != 0 || root != NULL)
{
if (root != NULL)
{
push(ps, root);
root = root->left;
}
else
{
root = pop(ps);
printf("visited %d\n", root->data);
root = root->right;
}
}
freeStack(&ps);
}
```
###### а) Постфиксный обход дерева
```c
void iterPostorder(node *root)
{
stack *ps = createStack();
node *lnp = NULL;
node *peekn = NULL;
while (!ps->size == 0 || root != NULL)
{
if (root)
{
push(ps, root);
root = root->left;
}
else
{
peekn = peek(ps);
if (peekn->right && lnp != peekn->right)
{
root = peekn->right;
}
else
{
pop(ps);
printf("visited %d\n", peekn->data);
lnp = peekn;
}
}
}
freeStack(&ps);
}
```
##### Рекурсивный обход бинарного дерева. Прямой (префиксный - сверху вниз)
1. Проверить, является ли текущий узел пустым
2. Вывести содержимое текущего узла
3. Рекурсивно вызвать просмотр левого поддерева
4. Рекурсивно вызвать просмотр правого поддерева
```c
void prefix_tree_print(t_tree* tree)
{
if (tree != NULL)
{
printf("%d \n", tree->data);
prefix_tree_print(tree->left);
prefix_tree_print(tree->right);
}
}
```
##### Обход в ширину
Сначала выводятся все вершины первого уровня, затем слева направо вершины второго и последующих уровней.
Так как сначала в контейнер помещаются все вершины, а затем их наследники, и извлекаются тоже сначала вершины, а затем наследники - используется очередь.
```c
void breadrhFirst(node* root)
{
queue *q = createQueue();
pushQueue(q, root);
while (q->size != 0)
{
node *tmp = (node*) popQueue;
printf("%d ", tmp->data);
if (tmp->left)
{
pushQueue(q, tmp->left);
}
else(tmp->right)
{
pushQueue(q, tmp->right);
}
}
deleteQueue(&q);
}
```
#### Двоичные деревья поиска (ДДП).
Двоичные деревья поиска - дерево, в котором все левые сыновья моложе предка, а правые - старше
Данное свойство наз-ся ***характеристическим свойством дерева двоичного поиска*** и выполняется для любого узла, включая корень.
#### Алгоритмы поиска в ДДП.
```c
typedef struct node
{
int key;
struct node *left;
struct node *right;
} node;
// Рекурсивный поиск узла
node *search(node *root, int key)
{
if ((root == NULL) || (root->key == key))
return root;
if (key < root->key)
return search(root->left, key);
else
return search(root->right, key);
}
//Итерационный поиск узла
node *search(node *root, int x)
{
node *curr = root;
while (curr == NULL)
{
if (curr->data == x)
return curr;
else if (curr->data < x)
curr = curr->right;
else
curr = curr->left;
}
return NULL;
}
```
***псевдокод***
```
Поиск узла со значением X с помощью рекурсии:
Function Poisk_R (X: Type_Inf; Q: P_Tr): P_Tr;
Begin
If (Q = Nil) Or (X = Q^.Inf)
Then Return Q;
If X < Q^.Inf
Then Return Poisk_R(X, Q^.Left)
Else Return Poisk_R(X, Q^.Right);
End;
Function Poisk_I (X: Type_Inf; Q: P_Tr): P_Tr;
Begin
Poisk_I := Nil;
While Q^.Inf <> X Do
If X < Q^.Inf Then Q := Q^.Left
Else Q := Q^.Right;
Poisk_I := Q;
End;
Если элемент с ключом не найден, то возвращается значение Nil.
```
#### Операции включения и исключения в ДДП.
__Включение__ в ДДП
```c
int t_insert(tree **root, int v)
{
while(*root)
{
if ((*root)->data == v)
return i;
if ((*root)->data > v)
root = &((*root)->left_p);
else
root = &((*root)->right_p)
}
if ((*root = (tree*)malloc(sizeof(tree))) == 0)
return 2;
(*root)->data = v;
(*root)->left_p = 0;
(*root)->right_p = 0;
return 0;
}
```
***Псевдокоды***
****включение****
```
3. Включение в дерево
Элемент с ключом X можно включить в дерево, реализовав
алгоритм поиска по дереву с включением.
Процедура поиска по дереву с включением выглядит так:
Procedure Search(X: Type_Inf; Var Q: P_Tr);
Begin
If Q = Nil Then
Begin
New(Q); // Создаем узел
Q^.Inf := X;
Q^.Left := Nil;
Q^.Right := Nil;
End
Else
Begin
If X < Q^.Inf Then Search(X, Q^.Left);
If X > Q^.Inf Then Search(X, Q^.Right);
End;
End;
Здесь Q — параметр-переменная (ссылка), а не параметр-значение.
Алгоритм поиска по дереву с включением
применяется для сортировки дерева.
При равных ключах можно
сделать: X ≥ Q^.Inf.
При большом количестве одинаковых ключей
можно добавить счетчик:
Type
P_Tr = ^Node;
Node = Record
Inf: Type_Inf;
Count: Word;
Left, Right: P_Tr;
End;
```
****исключение****
```
Type
P_Tr = ^Node;
Node = Record
Key: Type_Inf;
Left, Right: P_Tr;
End;
Procedure Delete_X (X: Type_Inf; Var P: P_Tr);
Var
Q: P_Tr;
// Процедура-заменитель
Procedure Changer (Var R: P_Tr);
Begin
if R^.Right <> Nil
Then Changer(R^.Right)
Else
Q^.Key := R^.Key;
Q := R;
R := R^.Left;
// Выход – левый потомок
End;
Begin
// Удаление элемента X из дерева
If P = Nil
Then Writeln('Элемента в дереве нет')
Else
If X < P^.Key
Then Delete_X(X, P^.Left)
Else
If X > P^.Key
Then Delete_X(X, P^.Right)
Else
Begin
// Удаление P
Q := P;
If Q^.Right = Nil
Then P := Q^.Left
Else
If Q^.Left = Nil
Then P := Q^.Right
Else Changer(Q^.Left);
Dispose(Q); // Освобождение вершины
End;
End;
```
-----
## 15. Сбалансированные деревья.
Дерево называется ***сбалансированным*** тогда и только тогда, когда высоты двух поддеревьев каждой из его вершин отличаются не более чем на единицу. Такие деревья также называют ***АВЛ-деревьями***.
эффективность: временная - __O(log n)__, емкостная - __O(n)__
-----
## 16. Операции включения и исключения в АВЛ деревьях.
__Включение в СБ__
Рассмотрим включение в левое поддерево. При включении в СБ возможны 3 случая:
• Левое и правое поддеревья становятся не равной высоты, но критерий сбалансированности не нарушается.
• Левое и правое поддерево приобретают равную высоту и т.о. сбалансированность даже улучшается.
• Критерий сбалансированности нарушается, и дерево надо перестраивать
__Исключение из СБ__
Удаление производится по алгоритму, аналогичному удалению из простого дерева поиска: удаляемый узел заменяется либо самым левым потомком из правого поддерева, либо самым правым потомком из левого поддерева (при условии, что у заменяющего узла не более одного потомка).
После фактического удаления узла на обратном пути рекурсии выполняется балансировка каждого пройденного узла теми же поворотами (RR, LL, LR, RL), что и при включении.
В результате дерово остаётся сбалансированным: высоты поддеревьев любого узла различаются не более чем на 1.
-----
## 17. Хеш-таблицы, методы создания хеш-таблиц. Критерии выбора хеш-функции. Коллизии, методы устранения коллизий. **Функции** для создания хеш-таблиц и поиска в них.
### Хеш-таблицы. Методы создания.
Хеш-таблица - структура данных вида "ассоциативный массив", к-ая ассоциирует ключи со значениями
__Методы создания:__
1. Метод деления (модульный)
2. Метод умножения (мультипликативный)
3. Метод сложения (аддитивный)
4. Полиномиальная функция
5. Метод "исключающее ИЛИ"
6. Метод середины квадрата
### Критерии выбора хеш-функций.
***Хорошей*** является хеш-функция, удовлетворяющая условиям:
1. простая с вычислительной точки зрения (быстрая)
2. распределяющая ключи в хеш-таблице наиболее равномерно
3. создающая минимальное кол-во коллизий
### Коллизии, методы устранения коллизий.
***Коллизия*** - ситуация, когда два ключа хешированы в одну и ту же ячейку
__Методы устранения коллизий:__
1. Метод цепочек - _открытое хеширование_
2. Закрытое хеширование - _внутреннее, открытая адресация_
### Функции для создания хеш-таблиц и поиска в них.
Согласно тексту лекций, **функции для создания хеш-таблиц и поиска в них** явно не приведены в виде конкретного кода, но на основе описанных методов и принципов можно выделить следующие:
---
### **1. Хеш-функции (основные методы)**
#### **А. Метод деления (модульный)**
```
hash(key) = key mod M
```
где `M` — размер таблицы (желательно простое число).
#### **Б. Метод умножения (мультипликативный)**
```
hash(key) = floor( M * ( (key * A) mod 1 ) )
```
где `A` — константа (0 < A < 1), `(key * A) mod 1` — дробная часть.
#### **В. Метод сложения (аддитивный)**
Для строки: сумма кодов символов.
```
hash(key) = (char1 + char2 + ... + charN) mod M
```
#### **Г. Полиномиальная функция**
Для строк (схема Горнера):
```
hash(key) = (char1 * p^(N-1) + char2 * p^(N-2) + ... + charN) mod M
```
где `p` — константа (часто 31 или 33).
#### **Д. Метод "исключающее ИЛИ" (XOR)**
```
hash(key) = char1 XOR char2 XOR ... XOR charN
```
#### **Е. Метод середины квадрата**
```
hash(key) = средние_цифры(key^2)
```
---
### **2. Функции поиска и разрешения коллизий**
#### **А. Метод цепочек (открытое хеширование)**
```
// Структура элемента цепочки
struct Node {
Key key;
Value value;
Node* next;
};
// Поиск в цепочке
Node* search(Node* table[], Key key) {
int index = hash(key) % M;
Node* current = table[index];
while (current != NULL) {
if (current->key == key) {
return current;
}
current = current->next;
}
return NULL;
}
```
#### **Б. Открытая адресация (закрытое хеширование)**
**Линейное пробирование:**
```
int probe_index(int index, int i) {
return (index + i) % M;
}
```
**Квадратичное пробирование:**
```
int probe_index(int index, int i) {
return (index + c1*i + c2*i*i) % M;
}
```
**Двойное хеширование:**
```
int hash1(key) = key mod M;
int hash2(key) = 1 + (key mod (M-1));
int probe_index(int index, int i) {
return (hash1(key) + i * hash2(key)) % M;
}
```
**Функция поиска при открытой адресации:**
```
Value search(Entry table[], Key key) {
int index = hash(key) % M;
int i = 0;
while (i < M) {
int current_index = probe_index(index, i);
if (table[current_index].key == key) {
return table[current_index].value;
}
if (table[current_index].status == EMPTY) {
return NOT_FOUND;
}
i++;
}
return NOT_FOUND;
}
```
---
### **3. Функции вставки**
#### **Для метода цепочек:**
```
void insert(Node* table[], Key key, Value value) {
int index = hash(key) % M;
Node* new_node = create_node(key, value);
new_node->next = table[index];
table[index] = new_node;
}
```
#### **Для открытой адресации (линейное пробирование):**
```
bool insert(Entry table[], Key key, Value value) {
int index = hash(key) % M;
int i = 0;
while (i < M) {
int current_index = (index + i) % M;
if (table[current_index].status != OCCUPIED) {
table[current_index].key = key;
table[current_index].value = value;
table[current_index].status = OCCUPIED;
return true;
}
i++;
}
return false; // таблица переполнена
}
```
---
### **4. Функция удаления**
#### **Для метода цепочек:**
```
bool remove(Node* table[], Key key) {
int index = hash(key) % M;
Node* current = table[index];
Node* prev = NULL;
while (current != NULL) {
if (current->key == key) {
if (prev == NULL) {
table[index] = current->next;
} else {
prev->next = current->next;
}
free(current);
return true;
}
prev = current;
current = current->next;
}
return false;
}
```
#### **Для открытой адресации (логическое удаление):**
```
bool remove(Entry table[], Key key) {
int index = hash(key) % M;
int i = 0;
while (i < M) {
int current_index = probe_index(index, i);
if (table[current_index].key == key &&
table[current_index].status == OCCUPIED) {
table[current_index].status = DELETED;
return true;
}
if (table[current_index].status == EMPTY) {
return false;
}
i++;
}
return false;
}
```
---
**Источник**: Лекции по хеш-таблицам (стр. 243–247), а также принципы обработки коллизий и общие алгоритмы поиска в структурах данных.
-----
## 18. Графы. Способы описания графов. Алгоритмы обработки графов: обход в ширину и глубину, поиск Эйлерова и Гамильтоновых путей, алгоритмы Дейкстры, Беллмана– Форда, Флойда - Уоршелла , Прима, Краскала.
### Графы. Способы описания графов
***Граф*** - это совокупность двух конечных множеств: множества точек и множества линий, попарно соединяющих некоторые из этих точек.
Множество точек называется __вершинами (узлами)__ графа.
Множество линий, соединяющих вершины графа, называются __ребрами (дугами)__ графа.
__Способы описания графов__
1. __матрица инцидентности__
• Для представления графа матрицейинцидентности надо n x m элементов
информации (ячеек памяти), из кот. большинство - нули. Неудобен и доступ к информации. Например, в пределе требуется перебор всех столбцов матрицы
• т.е. m шагов для ответа на вопросы типа "к
каким вершинам ведут ребра из x?" или
"существует ли ребро < x,y >?".
• Матрица инцидентности лучше всего подходит для операции «перечисление
ребер, инцидентных вершине x»
2. __матрица смежности__
Более эффективно представление графа МАТРИЦЕЙ СМЕЖНОСТИ B( N * N);
в ней элемент b[x,y] = 1 (или значение веса ребра), если есть ребро из вершины X в вершину Y и b[x,y] = 0 в противоположном случае. У неориентированных графов ребро {X,Y} является ребром {Y,X}, а потому матрица
смежности для них всегда симметрична.
+ "+" простота
- "-" разреженность, нельзя представить несколько ребер
между вершинами.
Этот способ очень хорош, когда нам надо часто
проверять смежность или находить вес ребра по двум
заданным вершинам.
• Для уменьшения времени доступа к эл-ту матрицы можно использовать векторы Айлиффа.
• В этом случае за один шаг просмотра можно ответить на вопрос, существует ли ребро из X в Y. Однако, независимо от количества ребер, объем требуемой памяти равен N*N, хотя для малых n можно хранить строку (столбец) матрицы машинном слове.
3. __список ребер__
• Можно представить неорграф списком ребер. Это
экономит память при неплотных графах ( m<<n*n ).
В третьей строке таблицы при необходимости можно указывать вес ребра
4. __список инцидентности__
Для каждой вершины v из V содержит список вершин U, таких, что v --> u ( для
неориентированного графа v -- u ). Каждый элемент списка инцидентности является записью (структурой)
```
R =Record
LINE : TypeV; //вершина
NEXT :^R; //указатель на следующую в списке
End; //(для последней записи в списке .NEXT = nil ).
```
Для неориентированных графов каждое ребро {u,v} представлено дважды: через вершину v в списке ZAP[u] и через вершину u в списке ZAP[v]. Требуемый объем памяти для представления графа списками инцидентности имеет порядок m+n.
### Обход в ширину и глубину.
Согласно тексту лекций, **обход в ширину и глубину** для **деревьев и графов** явно не описывается отдельным разделом, но следующие принципы и примеры обхода структур данных позволяют сделать выводы:
---
### **1. Обход в глубину (Depth-First Search, DFS)**
**Применительно к бинарным деревьям** обход в глубину реализуется тремя классическими способами (стр. 219–220):
1. **Прямой (префиксный) обход (NLR)**:
- Посещаем **узел (N)**, затем **левое поддерево (L)**, затем **правое поддерево (R)**.
- Пример: для дерева выражения `(a + b) * (c - d)` обход даст `* + a b - c d`.
2. **Симметричный (инфиксный) обход (LNR)**:
- Посещаем **левое поддерево (L)**, затем **узел (N)**, затем **правое поддерево (R)**.
- Для дерева поиска (BST) выдаёт элементы в отсортированном порядке.
3. **Обратный (постфиксный) обход (LRN)**:
- Посещаем **левое поддерево (L)**, затем **правое поддерево (R)**, затем **узел (N)**.
- Пример: `a b + c d - *` (обратная польская запись).
**Рекурсивная реализация** (на примере префиксного обхода, стр. 225):
```
Procedure Wr_TPref(Q : P_Tr);
Begin
If Q <> Nil Then
WriteLn(Q^.Inf); {N}
Wr_TPref(Q^.Left); {L}
Wr_TPref(Q^.Right); {R}
End;
```
**Для графов** обход в глубину подразумевает движение «вглубь» по одной ветви до конца, затем возврат (backtracking), что соответствует рекурсивному или стековому подходу.
---
### **2. Обход в ширину (Breadth-First Search, BFS)**
В лекциях **прямого описания BFS для деревьев/графов нет**, но принцип обхода в ширину соответствует работе **очереди (FIFO)**.
**Логика BFS** (выводится из принципов работы очереди):
1. Начинаем с корня (или начальной вершины), помещаем его в очередь.
2. Пока очередь не пуста:
- Извлекаем узел из начала очереди, обрабатываем его.
- Всех его непосещённых потомков (соседей) добавляем в конец очереди.
3. Повторяем для всех уровней дерева/графа.
**Связь с очередями** (стр. 78–81):
> Очередь функционирует по принципу FIFO (First In – First Out), что и используется в BFS: первыми обрабатываются узлы ближайшего уровня.
---
### **3. Сравнение обходов**
| Критерий | Обход в глубину (DFS) | Обход в ширину (BFS) |
|----------|-----------------------|-----------------------|
| **Структура данных** | Стек (явный или рекурсивный) | Очередь (FIFO) |
| **Порядок обработки** | «Углубление» по ветвям | По уровням (сначала ближние узлы) |
| **Применение** | Поиск в глубину, топологическая сортировка, решение задач с возвратом | Поиск кратчайшего пути, обход по уровням |
| **Пример в лекциях** | Обход бинарного дерева (префиксный, инфиксный, постфиксный) | Не описан явно, но логически соответствует работе очереди |
---
### **4. Пример использования обхода в глубину для выражений**
Для дерева выражения `(a + b * c) * (d - e / f)` (стр. 222–223):
- **Префиксный (DFS сверху вниз)**: `* + a * b c - d / e f`
- **Инфиксный (DFS слева направо)**: `a + b * c * d - e / f`
- **Постфиксный (DFS снизу вверх)**: `a b c * + d e f / - *`
---
**Источник**: Лекции 6, 7 (стр. 76–82, 219–226).
### Поиск Эйлерова пути.
***Эйлеров путь*** - путь в графе, проходящий через каждое ребро графа точно один раз
Эйлеров путь:
1. Выбрать произвольную вершину __v__. С нечетной степенью (если есть). _Вершины с нечетной степенью (не более 2) должны быть конечными._
2. В цикле по условию опустошения стека __ST__ строится путь с началом в вершине __v__.
3. Вершины строящегося пути размещаются в __ST__, ребра, входящие в путь, удаляются из графа (соответствующие элементы удаляются из списков __ZAP__)
4. Двунаправленность списко инцидентности __ZAP[v]__ позволяет устранить __{v, u}__ за время, ограниченное константой.
5. Общая сложность алгоритма: __O(m)__, где m - кол-во рёбер.
### Поиск Гамильтонова пути.
**алгоритм поиска всех гамильтоновых циклов в графе**
• в глобальном векторе X строится последовательность вершин:
• X[1],…X[k-1] строящегося пути;
• логический вектор DOP показывает, можно ли вставить вершины в проектируемый путь,
• n – кол-во вершин графа
```
Procedure Ham(k);
Begin
For u∈ZAP[X[k-1]] do
If (k=n+1) {если все вершины уже вставлены в путь}
And (u=v0) {и если последняя в-на в пути совпадает с 1-ой}
{т.е. это цикл}
Then Write(X[1],…X[k-1],v0) {печать пути и возможное окончание алгоритма}
Else
If DOP[u] {если вершину можно вставить в путь}
Then
Begin
X[k] <- u; DOP[u] <- False;
If k<= n Then
Ham(k+1); {очередное удлинение пути привело в тупик –}
Else
DOP[u] <- True; {необходимо вернуться для следующей попытки}
End;
End; {Ham}
Begin
For v∈V do DOP[v] <- True; //инициализация}
X[1] <- v0; //v0 – произвольная фиксированная вершина графа
DOP[v0] <- False;
Ham(2); //начало построения пути длиной 2
End.
```
• Этот рекурсивный алгоритм имеет сложность не более чем exp(n)
• Работу этого алгоритма можно проиллюстрировать процессом поиска в
некотором дереве, состоящем из всех возможных последовательностей
<x1,…,xk> для графа.
### Алгоритм Дейкстры.
• Поиск в орграфе кратчайших путей от одной вершины до всех остальных при неотрицательных ребрах.
• Каждой вершине из множества вершин V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм на каждом шаге «посещает» одну вершину и пытается уменьшать метки. Работа завершается, когда посетили все вершины.
• Инициализация. Метка вершины a полагается = 0, метки остальных — бесконечности (т.е. расстояния от a пока неизвестны, и они помечаются
как непосещённые)
• В цикле по всем вершинам идет поиск «минимальной » вершины и релаксация из нее всех достижимых из нее вершин с сохранением результата.
### Алгоритм Беллмана–Форда.
• Алгоритм поиска кратчайшего пути во взвешенном графе.
• За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алг-ма Дейкстры, алг-тм Беллмана–Форда допускает рёбра с отрицательным весом.
• Ричарда Беллмана (Richard Bellman) (1958 г.) - статья, посвящённую конкретно задаче нахождения кратчайшего пути. Лестер Форд (Lester Ford) (1956 г.) - фактически изобрёл этот алгоритм при изучении другой математ. задачи.
• Алгоритм маршрутизации RIP (алгоритм Беллмана–Форда) был впервые разработан в 1969 году, как основной для сети ARPANET.
### Алгоритм Флойда-Уоршелла.
• Алгоритм Флойда - Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного
графа. Разработан в 1962 году Робертом Флойдом (Robert W Floyd,) и Стивеном Уоршеллом (Stephen Warshall).
• Вершины графа последовательно пронумерованы от 1 до n. Алгоритм Флойда использует матрицу А размера п * n, в кот. вычисляются длины кратчайших путей.
• Вначале A[i, j] = D[i, j] для всех i != j. Если дуга i -» j отсутствует, то D[i, j] = ∞. Каждый диагональный элемент матрицы А равен 0.• Над матрицей А выполняется n итераций. После k-й итерации
• A[i, j] содержит значение наименьшей длины путей из вершины i в вершину у, которые не проходят через вершины с номером, большим k. Другими словами, между концевыми вершинами пути i и у могут находиться только вершины, номера которых меньше или равны k. На k-й итерации для вычисления матрицы А применяется следующая формула:
• Ak[i,j]=min(Ak-1[i,j], Ak-1[i,k]+Ak-1[k,j])
• Время выполнения этой программы, очевидно, имеет порядок 0(V3)
• Доказательство "правильности" работы этого алгоритма также очевидно и выполняется с помощью математической индукции по k, показывая, что на k-й итерации вершина k включается в путь только тогда, когда новый путь короче старого.
### Алгоритм Прима.
• А. Пр. — алгоритм построения минимального остового дерева
взвешенного связного неор. графа. Алгоритм впервые был открыт в 1930
году чешским математиком Войцехом Ярником, позже переоткрыт
Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959
году.
• Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В течение работы алгоритма дерево разрастается, пока не охватит все вершины исх. графа. На каждом шаге алгоритма к текущему дереву присоединяется самое лёгкое из рёбер, соединяющих вершину из построенного дерева, и вершину не из дерева.
• На входе - связный неориентированный граф G(V,E)
• На выходе - мн-во T рёбер минимального остового дерева
### Алгоритм Краскала.
• [Алгоритм](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%B0%D1%81%D0%BA%D0%B0%D0%BB%D0%B0) построения [минимального остового дерева](https://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE) взвешенного связного неор. графа. Алгоритм впервые описан Джозефом Крускалом (Kruskal).
• Вначале текущее множество рёбер устанавливается пустым.
Затем, пока это возможно, проводится след. операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовым деревом минимального веса
• До начала работы алгоритма необходимо отсортировать рёбра по весу, это требует O(E*log(E)) времени. После чего компоненты связности удобно хранить в виде системы непересекающихся множеств. Эффективность можно принять за O(E * log(E)).
• Идея алгоритма. Искомые ребра соединяют вершины. Поэтому возможны две стратегии построения. Можно идти от вершин и для каждой из них искать мин-ное ребро (как это сделано в а. Прима), а м. для каждого ребра выяснять можно ли его включить в строящееся дерево.
Google Drive
Gist
Clipboard
Sign in with Wallet
