Содержимое системного блока
⁃ Центральный процессор. Физически представлен довольно крупной микросхемой, включающей в себя множество транзисторов. Выполняет все математические расчеты.
⁃ Главная (материнская) плата. Является основой, объединяющей все компоненты в единую систему. На ней размещаются разъемы для подключения комплектующих, внутренние шины, преобразователи напряжения и пр.
⁃ Импульсный блок электропитания. Ответственен за преобразование сетевого переменного напряжения
⁃ Модули оперативной памяти. Представляют собой ряд микросхем, подключающейся к соответствующему разъему материнской платы.
Отметим, что вышеуказанные компоненты являются необходимыми для функционирования компьютера. Так, если без монитора включить системный блок можно, то без процессора это невозможно.
⁃ Центральный процессор. Физически представлен довольно крупной микросхемой, включающей в себя множество транзисторов. Выполняет все математические расчеты.
⁃ Главная (материнская) плата. Является основой, объединяющей все компоненты в единую систему. На ней размещаются разъемы для подключения комплектующих, внутренние шины, преобразователи напряжения и пр.
⁃ Импульсный блок электропитания. Ответственен за преобразование сетевого переменного напряжения
⁃ Модули оперативной памяти. Представляют собой ряд микросхем, подключающейся к соответствующему разъему материнской платы.
Отметим, что вышеуказанные компоненты являются необходимыми для функционирования компьютера. Так, если без монитора включить системный блок можно, то без процессора это невозможно.
Что такое SSD?
SSD, Solid State Drive – современный твердотельный накопитель. Для хранения информации используется флеш-память.
Есть 4 типа флеши-памяти:
⁃ SLC (Single Level Cell), где в каждой ячейке хранится по одному биту;
⁃ MLC (Multi Level Cells) – несмотря на нелогичное название, здесь всего два бита;
⁃ TLC (Triple Level Cells) с тремя битами на ячейку;
⁃ QLC (Quadruple Level Cells) – четыре бита на ячейку.
Кроме типа флеш-памяти есть еще один важный момент — контроллер. Он управляет операциями чтения/записи данных в ячейки памяти, следит за их состоянием, выполняет коррекцию ошибок, выравнивание износа ячеек, а также другие вспомогательные функции.
SSD, Solid State Drive – современный твердотельный накопитель. Для хранения информации используется флеш-память.
Есть 4 типа флеши-памяти:
⁃ SLC (Single Level Cell), где в каждой ячейке хранится по одному биту;
⁃ MLC (Multi Level Cells) – несмотря на нелогичное название, здесь всего два бита;
⁃ TLC (Triple Level Cells) с тремя битами на ячейку;
⁃ QLC (Quadruple Level Cells) – четыре бита на ячейку.
Кроме типа флеш-памяти есть еще один важный момент — контроллер. Он управляет операциями чтения/записи данных в ячейки памяти, следит за их состоянием, выполняет коррекцию ошибок, выравнивание износа ячеек, а также другие вспомогательные функции.
Жесткий диск (HDD)
HDD — устройство хранения данных, принцип записи информации в котором заключается в намагничивании областей на поверхности магнитных дисков(пластин).
Для организации хранения данных магнитный диск разбивается на дорожки и сектора, а совокупность дорожек, расположенных одна над другой
В зависимости от объема памяти, внутри корпуса HDD могут находиться до восьми пластин. Запись и чтение информации с пластины осуществляется при помощи магнитной головки.
За управление работой HDD отвечает электронная плата управления. На ней размещены центральный процессор с интегрированной ПЗУ, сервоконтроллер, кэш-память. Объем кэш-буфера в современных HDD достигает 512 МБ.
В зависимости от типоразмера жесткие диски можно разделить на две группы: 2.5-дюймовые HDD (нашли массовое применение в ноутбуках) и 3.5-дюймовые (применяются в персональных компьютерах, сетевых хранилищах и системах видеонаблюдения).
HDD — устройство хранения данных, принцип записи информации в котором заключается в намагничивании областей на поверхности магнитных дисков(пластин).
Для организации хранения данных магнитный диск разбивается на дорожки и сектора, а совокупность дорожек, расположенных одна над другой
В зависимости от объема памяти, внутри корпуса HDD могут находиться до восьми пластин. Запись и чтение информации с пластины осуществляется при помощи магнитной головки.
За управление работой HDD отвечает электронная плата управления. На ней размещены центральный процессор с интегрированной ПЗУ, сервоконтроллер, кэш-память. Объем кэш-буфера в современных HDD достигает 512 МБ.
В зависимости от типоразмера жесткие диски можно разделить на две группы: 2.5-дюймовые HDD (нашли массовое применение в ноутбуках) и 3.5-дюймовые (применяются в персональных компьютерах, сетевых хранилищах и системах видеонаблюдения).
3 уровня детализации в ER-моделях и моделях данных
Концептуальная модель данных — схема наивысшего уровня с минимальным количеством подробностей. Достоинство: возможность отобразить общую структуру модели и всю архитектуру системы. Менее масштабные системы могут обойтись и без этой модели. В этом случае можно сразу переходить к логической модели.
Логическая модель данных содержит более подробную информацию, нежели концептуальная модель. На этом уровне определяются более подробные операционные и транзакционные сущности. Логическая модель не зависит от технологии, в которой она будет применяться.
Физическая модель данных: на основе каждой логической модели данных можно составить одну или две физических модели. В последних должно присутствовать достаточно технических подробностей для составления и внедрения самой базы данных.
Концептуальная модель данных — схема наивысшего уровня с минимальным количеством подробностей. Достоинство: возможность отобразить общую структуру модели и всю архитектуру системы. Менее масштабные системы могут обойтись и без этой модели. В этом случае можно сразу переходить к логической модели.
Логическая модель данных содержит более подробную информацию, нежели концептуальная модель. На этом уровне определяются более подробные операционные и транзакционные сущности. Логическая модель не зависит от технологии, в которой она будет применяться.
Физическая модель данных: на основе каждой логической модели данных можно составить одну или две физических модели. В последних должно присутствовать достаточно технических подробностей для составления и внедрения самой базы данных.
Что такое избыточность данных?
Избыточность данных относится к практике хранения данных в двух или более местах в базе данных или системе хранения данных. Потому что если каким то образом данные будут повреждены, их можно будет легко восстановить, не останавливая при этом рабочий процесс.
Избыточность данных может возникать намеренно или случайно. Если это делается преднамеренно, то чаще всего эти данные используются для резервного копирования или аварийного восстановления. Если же это делается случайно, дублирование данных может привести к их несоответствию.
Также существуют другие альтернативы для защиты и восстановления данных. Например, есть бэкапы непрерывная защита данных (CDP), shapShot и образы.
Избыточность данных относится к практике хранения данных в двух или более местах в базе данных или системе хранения данных. Потому что если каким то образом данные будут повреждены, их можно будет легко восстановить, не останавливая при этом рабочий процесс.
Избыточность данных может возникать намеренно или случайно. Если это делается преднамеренно, то чаще всего эти данные используются для резервного копирования или аварийного восстановления. Если же это делается случайно, дублирование данных может привести к их несоответствию.
Также существуют другие альтернативы для защиты и восстановления данных. Например, есть бэкапы непрерывная защита данных (CDP), shapShot и образы.
Процедурное программирование
программирование, при котором последовательно выполняемые операторы можно собрать в подпрограммы, чтобы сообщить компьютеру, что он должен делать шаг за шагом, чтобы завершить задачу под рукой.
Процедурное программирование является отражением архитектуры традиционных ЭВМ, которая была предложена Фон Нейманом в 1940-х годах. Теоретической моделью процедурного программирования служит машина Тьюринга.
Эта парадигма использует линейный нисходящий подход и рассматривает данные и процедуры как два разных объекта. Основываясь на концепции вызова процедуры, процедурное программирование делит программу на процедуры, которые также известны как процедуры или функции, просто содержащие последовательность шагов, которые необходимо выполнить.
программирование, при котором последовательно выполняемые операторы можно собрать в подпрограммы, чтобы сообщить компьютеру, что он должен делать шаг за шагом, чтобы завершить задачу под рукой.
Процедурное программирование является отражением архитектуры традиционных ЭВМ, которая была предложена Фон Нейманом в 1940-х годах. Теоретической моделью процедурного программирования служит машина Тьюринга.
Эта парадигма использует линейный нисходящий подход и рассматривает данные и процедуры как два разных объекта. Основываясь на концепции вызова процедуры, процедурное программирование делит программу на процедуры, которые также известны как процедуры или функции, просто содержащие последовательность шагов, которые необходимо выполнить.
ООП или объектно-ориентированное программирование
ООП — это подход, при котором программа рассматривается как набор объектов, взаимодействующих друг с другом.
ООП обычно определяют через четыре принципа. (иногда количество сокращают до трех — опускают понятие абстракции)
1. Абстракция — способ выделить набор наиболее важных атрибутов и методов и исключить незначимые.
2. Инкапсуляция — свойство системы, позволяющее объединить данные и методы, работающие с ними в классе и скрыть детали реализации от пользователя.
3. Наследование — описание нового класса на основе уже существующего с частично или полностью заимствующейся функциональностью.
4. Полиморфизм — когда методы разных объектов могут выполнять задачи разными способами. Например, у «человека» есть метод «работать». У «программиста» — это будет означать написание кода, а у «директора» — рассмотрение управленческих вопросов. Но глобально и то, и то есть работа.
ООП — это подход, при котором программа рассматривается как набор объектов, взаимодействующих друг с другом.
ООП обычно определяют через четыре принципа. (иногда количество сокращают до трех — опускают понятие абстракции)
1. Абстракция — способ выделить набор наиболее важных атрибутов и методов и исключить незначимые.
2. Инкапсуляция — свойство системы, позволяющее объединить данные и методы, работающие с ними в классе и скрыть детали реализации от пользователя.
3. Наследование — описание нового класса на основе уже существующего с частично или полностью заимствующейся функциональностью.
4. Полиморфизм — когда методы разных объектов могут выполнять задачи разными способами. Например, у «человека» есть метод «работать». У «программиста» — это будет означать написание кода, а у «директора» — рассмотрение управленческих вопросов. Но глобально и то, и то есть работа.
Структура ООП
Объекты и классы
Чтобы сделать код проще, программу разбивают на независимые блоки — объекты. В реальной жизни это может быть стол, чашка, человек и многое другое. В программировании объекты — это структуры данных, у них, как и у реальных предметов, могут быть свойства: цвет, содержание или имя пользователя. А чтобы объединить между собой объекты с похожими свойствами, существуют классы.
Класс — это «шаблон» для объекта, который описывает его свойства. Объект — это экземпляр какого-нибудь класса.
Атрибуты и методы
Атрибуты — это переменные, конкретные характеристики объекта, такие как цвет поля или имя пользователя.
Методы — это функции, которые описаны внутри объекта или класса. Они относятся к определенному объекту и позволяют взаимодействовать с ними или другими частями кода.
Объекты и классы
Чтобы сделать код проще, программу разбивают на независимые блоки — объекты. В реальной жизни это может быть стол, чашка, человек и многое другое. В программировании объекты — это структуры данных, у них, как и у реальных предметов, могут быть свойства: цвет, содержание или имя пользователя. А чтобы объединить между собой объекты с похожими свойствами, существуют классы.
Класс — это «шаблон» для объекта, который описывает его свойства. Объект — это экземпляр какого-нибудь класса.
Атрибуты и методы
Атрибуты — это переменные, конкретные характеристики объекта, такие как цвет поля или имя пользователя.
Методы — это функции, которые описаны внутри объекта или класса. Они относятся к определенному объекту и позволяют взаимодействовать с ними или другими частями кода.
Плюсы и минусы объектно-ориентированного программирования
Начнем с преимуществ:
⁃ модульность — подход позволяет сделать код более структурированным, в нем легко разобраться стороннему человеку.
⁃ гибкость — ООП-код легко развивать, дополнять и изменять.
⁃ экономия времени — благодаря абстракции, полиморфизму и наследованию можно не писать один и тот же код много раз. Это ускоряет разработку нового ПО.
⁃ безопасность — программу сложно сломать, так как инкапсулированный код недоступен извне.
Недостатки:
⁃ снижение производительности — ООП подход снижает производительность кода в целом. Программы работают медленнее из-за особенностей доступа к данным и большого количества сущностей.
⁃ большой размер программы — занимает больше места на диске, чем «процедурный», тк в программе хранится больше конструкций.
Начнем с преимуществ:
⁃ модульность — подход позволяет сделать код более структурированным, в нем легко разобраться стороннему человеку.
⁃ гибкость — ООП-код легко развивать, дополнять и изменять.
⁃ экономия времени — благодаря абстракции, полиморфизму и наследованию можно не писать один и тот же код много раз. Это ускоряет разработку нового ПО.
⁃ безопасность — программу сложно сломать, так как инкапсулированный код недоступен извне.
Недостатки:
⁃ снижение производительности — ООП подход снижает производительность кода в целом. Программы работают медленнее из-за особенностей доступа к данным и большого количества сущностей.
⁃ большой размер программы — занимает больше места на диске, чем «процедурный», тк в программе хранится больше конструкций.
Функциональное программирование
Функциональное программирование сильно отличается как от процедурного программирования, так и от ООП, поскольку в нем используются математические функции. Благодаря этому операции выполняются только на основе введенных входных данных, и они не зависят от временных или скрытых переменных.
Смысл функционального программирования в том, чтобы описать не сами чёткие шаги к цели, а правила, по которым компилятор сам должен дойти до нужного результата.
Последовательность выполнения подпрограмм определяет сам код и компилятор, а не программист. Каждая команда — это какое-то правило, поэтому нет разницы, когда мы запишем это правило, в начале или в конце кода. Главное, чтобы у нас это правило было, а компилятор сам разберётся, в какой момент его применять.
Функциональное программирование сильно отличается как от процедурного программирования, так и от ООП, поскольку в нем используются математические функции. Благодаря этому операции выполняются только на основе введенных входных данных, и они не зависят от временных или скрытых переменных.
Смысл функционального программирования в том, чтобы описать не сами чёткие шаги к цели, а правила, по которым компилятор сам должен дойти до нужного результата.
Последовательность выполнения подпрограмм определяет сам код и компилятор, а не программист. Каждая команда — это какое-то правило, поэтому нет разницы, когда мы запишем это правило, в начале или в конце кода. Главное, чтобы у нас это правило было, а компилятор сам разберётся, в какой момент его применять.
Непрерывная защита данных (CDP)
Из соображений производительности резервные копии обычно создаются через регулярные, но достаточно долгие промежутки времени. Если система временно повреждена, изменения данных, внесенные в период между последним созданием резервной копии и сбоем системы, будут утрачены.
Функциональность CDP позволяет создавать резервные копии выбранных данных в промежутки времени между запланированными сеансами резервного копирования на постоянной основе:
⁃ Путем отслеживания изменений в указанных файлах/папках
⁃ Путем отслеживания изменений файлов, внесенных конкретными приложениями
Из данных, выбранных для резервного копирования, можно выбрать определенные файлы для непрерывной защиты данных. Система будет создавать копию каждого изменения, внесенного в эти файлы. Их можно будет восстановить в состояние на время последнего изменения.
Из соображений производительности резервные копии обычно создаются через регулярные, но достаточно долгие промежутки времени. Если система временно повреждена, изменения данных, внесенные в период между последним созданием резервной копии и сбоем системы, будут утрачены.
Функциональность CDP позволяет создавать резервные копии выбранных данных в промежутки времени между запланированными сеансами резервного копирования на постоянной основе:
⁃ Путем отслеживания изменений в указанных файлах/папках
⁃ Путем отслеживания изменений файлов, внесенных конкретными приложениями
Из данных, выбранных для резервного копирования, можно выбрать определенные файлы для непрерывной защиты данных. Система будет создавать копию каждого изменения, внесенного в эти файлы. Их можно будет восстановить в состояние на время последнего изменения.
Граф как структура данных
Структура данных графа представляет собой набор узлов, которые имеют данные и связаны с другими узлами.
Точнее, граф - это структура данных (V, E), которая состоит из:
⁃ Коллекции вершин V.
⁃ Набора ребер E, представленный в виде упорядоченных пар вершин (u, v).
Терминология графа:
⁃ смежность
Вершина смежна с другой вершиной, если есть ребро, соединяющее их.
⁃ путь
Последовательность ребер, которая позволяет вам перейти от вершины A к вершине B
⁃ ориентированный граф
Граф, в котором есть ребро (u, v) не обязательно означает, что также имеется ребро (v, u). Ребра в таком графике представлены стрелками, чтобы показать направление ребра.
Структура данных графа представляет собой набор узлов, которые имеют данные и связаны с другими узлами.
Точнее, граф - это структура данных (V, E), которая состоит из:
⁃ Коллекции вершин V.
⁃ Набора ребер E, представленный в виде упорядоченных пар вершин (u, v).
Терминология графа:
⁃ смежность
Вершина смежна с другой вершиной, если есть ребро, соединяющее их.
⁃ путь
Последовательность ребер, которая позволяет вам перейти от вершины A к вершине B
⁃ ориентированный граф
Граф, в котором есть ребро (u, v) не обязательно означает, что также имеется ребро (v, u). Ребра в таком графике представлены стрелками, чтобы показать направление ребра.
Способы представления графа
матрица смежности
двумерная матрица, в которой и число строк, и число столбцов равно числу вершин графа. В ячейки матрицы смежности записываются числа 0 или 1 в зависимости от того, соединены соответствующие вершины рёбрами или нет.
матрица инцидентности
матрица размера n x m, где n - число вершин графа, m - число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы - рёбрам графа.
списки инцидентности
Представляют собой граф в виде массива связанного списка. Индекс массива представляет вершину, и каждый элемент в его связанном списке представляет другие вершины, которые образуют ребро с вершиной.
матрица смежности
двумерная матрица, в которой и число строк, и число столбцов равно числу вершин графа. В ячейки матрицы смежности записываются числа 0 или 1 в зависимости от того, соединены соответствующие вершины рёбрами или нет.
матрица инцидентности
матрица размера n x m, где n - число вершин графа, m - число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы - рёбрам графа.
списки инцидентности
Представляют собой граф в виде массива связанного списка. Индекс массива представляет вершину, и каждый элемент в его связанном списке представляет другие вершины, которые образуют ребро с вершиной.
Коллизии хеш-функции
Коллизия хеш-функции — это когда у двух разных входных элементов таблицы hash будет одинаковым. Коллизии встречаются в разнообразных алгоритмах хеширования, однако это не является нормой и в «правильных» алгоритмах их возникновение сведено к минимальному значению. Но в то же время, когда приходится работать с большими таблицами хеширования, то их возникновение неизбежно.
При возникновении коллизий необходимо найти новое место для хранения ключей, претендующих на одну и ту же ячейку хеш-таблицы.
Причем, если коллизии допускаются, то их количество необходимо минимизировать. В некоторых специальных случаях удается избежать коллизий вообще. Например, если все ключи элементов известны заранее, то для них можно найти некоторую инъективную хеш-функцию, которая распределит их по ячейкам хеш-таблицы без коллизий. Хеш-таблицы, использующие подобные хеш-функции, не нуждаются в механизме разрешения коллизий, и называются хеш-таблицами с прямой адресацией.
Коллизия хеш-функции — это когда у двух разных входных элементов таблицы hash будет одинаковым. Коллизии встречаются в разнообразных алгоритмах хеширования, однако это не является нормой и в «правильных» алгоритмах их возникновение сведено к минимальному значению. Но в то же время, когда приходится работать с большими таблицами хеширования, то их возникновение неизбежно.
При возникновении коллизий необходимо найти новое место для хранения ключей, претендующих на одну и ту же ячейку хеш-таблицы.
Причем, если коллизии допускаются, то их количество необходимо минимизировать. В некоторых специальных случаях удается избежать коллизий вообще. Например, если все ключи элементов известны заранее, то для них можно найти некоторую инъективную хеш-функцию, которая распределит их по ячейкам хеш-таблицы без коллизий. Хеш-таблицы, использующие подобные хеш-функции, не нуждаются в механизме разрешения коллизий, и называются хеш-таблицами с прямой адресацией.
Алгоритм Дейкстры
Алгоритм Дейкстры — это метод, который находит кратчайший путь от одной вершины графа к другой.
Для этого алгоритма граф должен быть взвешенный, но не иметь ребер с отрицательным весом, т.е. таких, при прохождении через которые длина пути как бы уменьшается.
Алгоритм Дейкстры пошаговый. Сначала выбирается точка, от которой будут отсчитываться пути. Затем алгоритм поочередно ищет самые короткие маршруты из исходной точки в другие. Вершины, где он уже побывал, отмечает посещенными. Алгоритм использует посещенные вершины, когда рассчитывает пути для непосещенных.
Сложность алгоритма изменяется в зависимости от реализации. Например:
Если вершины хранятся в простом массиве и для поиска минимума используется алгоритм линейного поиска, временная сложность алгоритма Дейкстры составляет
Если же используется очередь с приоритетами, реализованная на основе двоичной кучи, то мы получаем O(E log V).
Если же очередь с приоритетами была реализована на основе кучи Фибоначчи, получается наилучшая оценка сложности
Алгоритм Дейкстры — это метод, который находит кратчайший путь от одной вершины графа к другой.
Для этого алгоритма граф должен быть взвешенный, но не иметь ребер с отрицательным весом, т.е. таких, при прохождении через которые длина пути как бы уменьшается.
Алгоритм Дейкстры пошаговый. Сначала выбирается точка, от которой будут отсчитываться пути. Затем алгоритм поочередно ищет самые короткие маршруты из исходной точки в другие. Вершины, где он уже побывал, отмечает посещенными. Алгоритм использует посещенные вершины, когда рассчитывает пути для непосещенных.
Сложность алгоритма изменяется в зависимости от реализации. Например:
Если вершины хранятся в простом массиве и для поиска минимума используется алгоритм линейного поиска, временная сложность алгоритма Дейкстры составляет
O(V²).Если же используется очередь с приоритетами, реализованная на основе двоичной кучи, то мы получаем O(E log V).
Если же очередь с приоритетами была реализована на основе кучи Фибоначчи, получается наилучшая оценка сложности
O(V log V + E).Depth-First Search
Поиск в глубину является одним из основных алгоритмов обхода графа. Если говорить простыми словами, то обход графа — это переход от одной его вершины к другой в поисках свойств связей этих вершин.
DFS следует концепции «погружайся глубже, головой вперед» («go deep, head first»). Идея заключается в том, что мы двигаемся от начальной вершины по определенному пути до тех пор, пока не достигнем конца пути или искомой вершины. Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад и идем по другому маршруту.
Поскольку мы обходим каждого «соседа» каждого узла, игнорируя тех, которых посещали ранее, мы имеем время выполнения, равное
Поиск в глубину является одним из основных алгоритмов обхода графа. Если говорить простыми словами, то обход графа — это переход от одной его вершины к другой в поисках свойств связей этих вершин.
DFS следует концепции «погружайся глубже, головой вперед» («go deep, head first»). Идея заключается в том, что мы двигаемся от начальной вершины по определенному пути до тех пор, пока не достигнем конца пути или искомой вершины. Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад и идем по другому маршруту.
Поскольку мы обходим каждого «соседа» каждого узла, игнорируя тех, которых посещали ранее, мы имеем время выполнения, равное
O(V + E), где V — количество вершин. E — количество ребер.Breadth-First Search
Поиск в ширину позволяет найти кратчайший (содержащий наименьшее число ребер) путь из одной вершины графа до всех остальных вершин.
BFS следует концепции «расширяйся, поднимаясь на высоту птичьего полета» («go wide, bird’s eye-view»). Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. В нем сначала посещаются все вершины, смежные с текущей, а затем их потомки.
Время выполнения BFS составляет
Поиск в ширину позволяет найти кратчайший (содержащий наименьшее число ребер) путь из одной вершины графа до всех остальных вершин.
BFS следует концепции «расширяйся, поднимаясь на высоту птичьего полета» («go wide, bird’s eye-view»). Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. В нем сначала посещаются все вершины, смежные с текущей, а затем их потомки.
Время выполнения BFS составляет
O(V + E), где V — количество вершин. E — количество ребер.Метод открытой адресации
Метод открытой адресации или закрытое хеширование — один из методов разрешение коллизий.
В случае открытой адресации, если ячейка с вычисленным индексом занята, то можно просто просматривать следующие записи таблицы по порядку до тех пор, пока не будет найден ключ K или пустая позиция в таблице. Для вычисления шага можно также применить формулу, которая и определит способ изменения шага.
Преимущества:
⁃ Использует мало памяти: для хранения n значений резервируется только
n ячеек в памяти
⁃ Удобно использовать при малом количестве коллизий на одно хеш- значение( не более 3-х)
Недостатки:
⁃ Поиск определённого значения в хеш-таблице неоптимально.
⁃ Время работы
⁃ Нет чёткой структуры, хеш-значения могут храниться не в отсортированном виде
Метод открытой адресации или закрытое хеширование — один из методов разрешение коллизий.
В случае открытой адресации, если ячейка с вычисленным индексом занята, то можно просто просматривать следующие записи таблицы по порядку до тех пор, пока не будет найден ключ K или пустая позиция в таблице. Для вычисления шага можно также применить формулу, которая и определит способ изменения шага.
Преимущества:
⁃ Использует мало памяти: для хранения n значений резервируется только
n ячеек в памяти
⁃ Удобно использовать при малом количестве коллизий на одно хеш- значение( не более 3-х)
Недостатки:
⁃ Поиск определённого значения в хеш-таблице неоптимально.
⁃ Время работы
O(n^2) ⁃ Нет чёткой структуры, хеш-значения могут храниться не в отсортированном виде
Метод цепочек — метод разрешения коллизий
Метод цепоцек — внешнее или открытое хеширование.
Технология сцепления элементов состоит в том, что элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список. В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш-значение ключа равно i; если таких элементов в множестве нет, в позиции i записан NULL.
Преимущества:
⁃ Метод цепочек эффективен и имеет чёткую структуру.
⁃ Его удобно использовать, когда неизвестно количество коллизий на
одно хеш-значение.
⁃ Поиск нужного значения будет происходит за минимально возможное время.
Недостатки:
⁃ Он использует много памяти: для хранения n хеш-значений выделяется ~n^2 ячеек памяти.
⁃ Время работы метода O(n^2).
Метод цепоцек — внешнее или открытое хеширование.
Технология сцепления элементов состоит в том, что элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список. В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш-значение ключа равно i; если таких элементов в множестве нет, в позиции i записан NULL.
Преимущества:
⁃ Метод цепочек эффективен и имеет чёткую структуру.
⁃ Его удобно использовать, когда неизвестно количество коллизий на
одно хеш-значение.
⁃ Поиск нужного значения будет происходит за минимально возможное время.
Недостатки:
⁃ Он использует много памяти: для хранения n хеш-значений выделяется ~n^2 ячеек памяти.
⁃ Время работы метода O(n^2).
Extensible Firmware Interface
Многие низкоуровневые системные настройки компьютера доступны только в BIOS. Современные же компьютеры в основном уже идут с UEFI, которая является приемником традиционного BIOS. Но данные прошивки имеют много общего. Иногда даже интерфейс UEFI сложно отличить от BIOS.
Основное назначение EFI - замена устаревающей технологии BIOS и связанных с ней ограничений.
Основная цель разработки UEFI заключается в стандартизации взаимодействия операционной системы с микропрограммами платформы в ходе процесса загрузки. В классическом BIOS основным механизмом взаимодействия с аппаратурой в процессе загрузки были программные прерывания и порты ввода-вывода, однако современные системы в состоянии обеспечить более эффективное выполнение операций ввода-вывода между оборудованием и программным обеспечением.
Многие низкоуровневые системные настройки компьютера доступны только в BIOS. Современные же компьютеры в основном уже идут с UEFI, которая является приемником традиционного BIOS. Но данные прошивки имеют много общего. Иногда даже интерфейс UEFI сложно отличить от BIOS.
Основное назначение EFI - замена устаревающей технологии BIOS и связанных с ней ограничений.
Основная цель разработки UEFI заключается в стандартизации взаимодействия операционной системы с микропрограммами платформы в ходе процесса загрузки. В классическом BIOS основным механизмом взаимодействия с аппаратурой в процессе загрузки были программные прерывания и порты ввода-вывода, однако современные системы в состоянии обеспечить более эффективное выполнение операций ввода-вывода между оборудованием и программным обеспечением.
File Allocation Table
FAT (сокр. от File Allocation Table, таблица размещения файлов) – это вид файловой системы, созданный компанией Microsoft и используемый её ранними операционными системами.
Есть несколько версий системы:
FAT8 — Самая старая версия FAT, FAT8 использовалась на 8 дюймовых дискетах с процессором 8086.
FAT12 — Это таблица размещения файлов испытующая 12-битную двоичную систему, которая была получена от FAT8. FAT12 уже давно не используется. Ранее она применялась на 3,5 дюймовых дискетах емкостью 1,44 Мб.
FAT16 — Файловая система FAT с использованием 16-битной двоичной системы. Использовалась с Windows 3.x до Windows 95.
FAT32 — Улучшенная «таблица размещения файлов» с использованием 28-битной двоичной системы. Она применялась в первую очередь в Windows 95 OSR2 и Windows 98.
FAT (сокр. от File Allocation Table, таблица размещения файлов) – это вид файловой системы, созданный компанией Microsoft и используемый её ранними операционными системами.
Есть несколько версий системы:
FAT8 — Самая старая версия FAT, FAT8 использовалась на 8 дюймовых дискетах с процессором 8086.
FAT12 — Это таблица размещения файлов испытующая 12-битную двоичную систему, которая была получена от FAT8. FAT12 уже давно не используется. Ранее она применялась на 3,5 дюймовых дискетах емкостью 1,44 Мб.
FAT16 — Файловая система FAT с использованием 16-битной двоичной системы. Использовалась с Windows 3.x до Windows 95.
FAT32 — Улучшенная «таблица размещения файлов» с использованием 28-битной двоичной системы. Она применялась в первую очередь в Windows 95 OSR2 и Windows 98.