Методы сортировки и поиска

Введение
Типы и структуры данных
Понятие типа данных

Встроенные типы данных
Уточняемые типы данных
Перечисляемые типы данных
Конструируемые типы данных
Массивы
Записи

Записи с вариантами
Множества
Указатели
Динамическое распределение памяти и списки
Абстрактные (определяемые пользователями) типы данных

Представление типа
Реализация типа
Инкапсуляция
Наследование типов
Разновидности полиморфизма
Типы и структуры данных, применяемые в реляционных базах данных
Типы и структуры данных, применяемые в объектно-реляционных базах данных

Строчные типы данных
Наследование таблиц и семантика включения
Типы коллекций
Объектные типы данных
Методы внутренней сортировки
Сортировка включением
Обменная сортировка
Сортировка выбором

Сортировка разделением (Quicksort)
Сортировка с помощью дерева (Heapsort)
Сортировка со слиянием
Сравнение методов внутренней сортировки
Методы внешней сортировки
Прямое слияние
Естественное слияние

Сбалансированное многопутевое слияние
Многофазная сортировка
Улучшение эффективности внешней сортировки за счет использования основной памяти
Методы поиска в основной памяти
Методы поиска в основной памяти на основе деревьев
Двоичные деревья
Сбалансированные двоичные деревья

Деревья оптимального поиска
Деревья цифрового поиска
Методы хэширования для поиска в основной памяти
Совершенное хэширование
Коллизии при хэшировании и способы их разрешения
Линейное зондирование
Двойное хэширование

Использование цепочек переполнения
Методы поиска во внешней памяти
Методы поиска во внешней памяти на основе деревьев
Классические B-деревья
B+-деревья
Разновидности B+-деревьев для организации индексов в базах данных
R-деревья и их использование для организации индексов в пространственных базах данных
Методы хэширования для поиска во внешней памяти

Расширяемое хэширование
Линейное хэширование
Использование хэширования для организации индексов в базах данных
Дополнительные способы поддержки поиска в базах данных
Индексы соединения
Индексы на основе использования битовых шкал

Основы операционных систем

Все программное обеспечение принято делить на две части: прикладное и системное. К прикладному программному обеспечению, как правило, относятся разнообразные банковские и прочие бизнес-программы, игры, текстовые процессоры и т. п. Под системным программным обеспечением обычно понимают программы, способствующие функционированию и разработке прикладных программ. Надо сказать, что деление на прикладное и системное программное обеспечение является отчасти условным и зависит от того, кто осуществляет такое деление. Так, обычный пользователь, неискушенный в программировании, может считать Microsoft Word системной программой, а, с точки зрения программиста, это – приложение. Компилятор языка Си для обычного программиста – системная программа, а для системного – прикладная.

Структура вычислительной системы
Понятие процесса
Уровни планирования
Взаимодействующие процессы
Interleaving, race condition и взаимоисключения

Концепция семафоров
Условия возникновения тупиков
Физическая организация памяти компьютера
Понятие виртуальной памяти
Исключительные ситуации при работе с памятью

Имена файлов
Общая структура файловой системы
Физические принципы организации ввода-вывода
Для чего компьютеры объединяют в сети
Угрозы безопасности
Идентификация и аутентификация

---

---