Способы представления графа
матрица смежности
двумерная матрица, в которой и число строк, и число столбцов равно числу вершин графа. В ячейки матрицы смежности записываются числа 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.
New Technology File System
NTFS – это файловая система (система организации файлов), обычно используемая на жестких дисках компьютеров под управлением Microsoft Windows.
NTFS предлагает более эффективные методы защиты данных и восстановления файлов, чем предыдущая файловая система FAT, используемая в ОС MS-DOS и Windows.
NTFS отслеживает содержимое тома с помощью файла MFT (Master File Table), являющегося сердцем файловой системы NTFS. MFT состоит из индекса всех файлов в томе, который содержит имена файлов, список атрибутов файлов и указателей на их фрагменты.
Особенности системы:
⁃ NTFS поддерживает длинные имена файлов.
⁃ Поддержка сжатия файлов и каталогов для оптимизации пространства на жестком диске.
⁃ Поддержка больших размеров жестких дисков
⁃ Максимальный размер одного файла может достигать ~
⁃ Максимальное количество файлов:
NTFS – это файловая система (система организации файлов), обычно используемая на жестких дисках компьютеров под управлением Microsoft Windows.
NTFS предлагает более эффективные методы защиты данных и восстановления файлов, чем предыдущая файловая система FAT, используемая в ОС MS-DOS и Windows.
NTFS отслеживает содержимое тома с помощью файла MFT (Master File Table), являющегося сердцем файловой системы NTFS. MFT состоит из индекса всех файлов в томе, который содержит имена файлов, список атрибутов файлов и указателей на их фрагменты.
Особенности системы:
⁃ NTFS поддерживает длинные имена файлов.
⁃ Поддержка сжатия файлов и каталогов для оптимизации пространства на жестком диске.
⁃ Поддержка больших размеров жестких дисков
⁃ Максимальный размер одного файла может достигать ~
16 Тб⁃ Максимальное количество файлов:
4 294 967 295Журналируемые файловые системы
Основная цель, которая преследуется при создании журналируемых файловых систем, состоит в том, чтобы обеспечить быстрое восстановление системы после сбоев. Если произойдет такой сбой, то часть информации о расположении файлов теряется, поскольку не все изменения сразу записываются на диск. После этого программа fsck вынуждена просматривать весь диск блок за блоком с целью восстановления потерянных связей. При увеличении размера дисков вдвое, вдвое увеличивается и время, необходимое для просмотра всего диска. А при тех объемах, которых достигают современные диски, время стало достигать часов и даже суток. А сервер в это время не отзывается! Кроме того, нет гарантии, что все связи удастся восстановить.
В журналируемых файловых системах для решения этой проблемы применяют технику транзакций, развитую в теории баз данных. Суть этой техники в том, что действие не считается завершенным, пока все изменения не сохранены на диске. А чтобы сбои, происходящие в течение времени, необходимого для завершения всех операций, не приводили к необратимым последствиям, все действия и все изменяемые данные протоколируются. Если сбой все-таки произойдет, то по этому протоколу можно вернуть систему в безошибочное состояние.
Основная цель, которая преследуется при создании журналируемых файловых систем, состоит в том, чтобы обеспечить быстрое восстановление системы после сбоев. Если произойдет такой сбой, то часть информации о расположении файлов теряется, поскольку не все изменения сразу записываются на диск. После этого программа fsck вынуждена просматривать весь диск блок за блоком с целью восстановления потерянных связей. При увеличении размера дисков вдвое, вдвое увеличивается и время, необходимое для просмотра всего диска. А при тех объемах, которых достигают современные диски, время стало достигать часов и даже суток. А сервер в это время не отзывается! Кроме того, нет гарантии, что все связи удастся восстановить.
В журналируемых файловых системах для решения этой проблемы применяют технику транзакций, развитую в теории баз данных. Суть этой техники в том, что действие не считается завершенным, пока все изменения не сохранены на диске. А чтобы сбои, происходящие в течение времени, необходимого для завершения всех операций, не приводили к необратимым последствиям, все действия и все изменяемые данные протоколируются. Если сбой все-таки произойдет, то по этому протоколу можно вернуть систему в безошибочное состояние.
Материнская плата
Материнская плата — печатная плата, являющаяся основой построения модульного электронного устройства.
Системная плата содержит основную часть устройства. В случае компьютера — процессор, системную шину или шины, оперативную память, «встроенные» контроллеры периферийных устройств, сервисную логику — и разъёмы для подключения дополнительных взаимозаменяемых плат, называемых платами расширений, как правило подключённые к общей шине или шинам.
В отличие от объединительной панели/платы, просто соединяющей между собой разъёмы карт расширения, материнская плата всегда несёт на себе активные компоненты или разъёмы для их установки. В англоязычной литературе также принято разделять системные платы на собственно материнские («motherboards»), обладающие возможностями расширения и модификации, и «основные платы» («mainboards»), таких возможностей не имеющие и представляющие собой законченную неизменяемую систему.
Материнская плата — печатная плата, являющаяся основой построения модульного электронного устройства.
Системная плата содержит основную часть устройства. В случае компьютера — процессор, системную шину или шины, оперативную память, «встроенные» контроллеры периферийных устройств, сервисную логику — и разъёмы для подключения дополнительных взаимозаменяемых плат, называемых платами расширений, как правило подключённые к общей шине или шинам.
В отличие от объединительной панели/платы, просто соединяющей между собой разъёмы карт расширения, материнская плата всегда несёт на себе активные компоненты или разъёмы для их установки. В англоязычной литературе также принято разделять системные платы на собственно материнские («motherboards»), обладающие возможностями расширения и модификации, и «основные платы» («mainboards»), таких возможностей не имеющие и представляющие собой законченную неизменяемую систему.
Соглашения о вызовах
Соглашение о вызовах определяют как функция вызывается, как функция управляет стеком и стековым кадром, как аргументы передаются в функцию, как функция возвращает значения.
⁃ stdcall
стандартное соглашение для Win32 API. В данном соглашение, аргументы передаются справа налево и очистка стека ложится на вызываемую функцию. Для передачи аргументов используется стек, т.е. перед вызовом нужно положить аргументы на стек. Возвращаемое значение записывается в регистр eax.
⁃ cdecl
Стандартное соглашение о вызовах для программ на C/C++. В данном соглашение аргументы передаются справа налево и кладутся на стек, как и в stdcall, но вот стек уже очищается функцией, которая вызывает.
⁃ fastcall
Главным отличием от двух соглашениях выше является то, что аргументы кладутся в регистры, если это возможно, что позволяет увеличить скорость вызова функции, потому что обратиться к регистру быстрее, чем к стеку.
⁃ thiscall
Это соглашение о вызовах используется для вызова нестатических функций-членов C++. Так как используется только для нестатических функций-членов, то у нас есть указатель this, который передается в ECX, стек очищается вызываемой функцией, аргументы передаются справа налево на стек, возвращаемое значение помещается в регистр EAX.
Соглашение о вызовах определяют как функция вызывается, как функция управляет стеком и стековым кадром, как аргументы передаются в функцию, как функция возвращает значения.
⁃ stdcall
стандартное соглашение для Win32 API. В данном соглашение, аргументы передаются справа налево и очистка стека ложится на вызываемую функцию. Для передачи аргументов используется стек, т.е. перед вызовом нужно положить аргументы на стек. Возвращаемое значение записывается в регистр eax.
⁃ cdecl
Стандартное соглашение о вызовах для программ на C/C++. В данном соглашение аргументы передаются справа налево и кладутся на стек, как и в stdcall, но вот стек уже очищается функцией, которая вызывает.
⁃ fastcall
Главным отличием от двух соглашениях выше является то, что аргументы кладутся в регистры, если это возможно, что позволяет увеличить скорость вызова функции, потому что обратиться к регистру быстрее, чем к стеку.
⁃ thiscall
Это соглашение о вызовах используется для вызова нестатических функций-членов C++. Так как используется только для нестатических функций-членов, то у нас есть указатель this, который передается в ECX, стек очищается вызываемой функцией, аргументы передаются справа налево на стек, возвращаемое значение помещается в регистр EAX.
Форма Бэкуса — Наура
БНФ (Бэкуса — Наура форма) — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории.
БНФ используется для описания контекстно-свободных формальных грамматик. Если точнее, то для описания синтаксиса языков программирования, данных, протоколов.
БНФ-конструкция определяет конечное число символов. Также она определяет правила замены символа на какую-то последовательность букв и символов.
Процесс получения цепочки букв, можно определить поэтапно:
⁃ изначально имеется один символ (символы обычно заключаются в угловые скобки, а их название не несёт никакой информации).
⁃ этот символ заменяется на некоторую последовательность букв и символов, согласно одному из правил.
⁃ процесс повторяется (на каждом шаге один из символов заменяется на последовательность, согласно правилу).
⁃ в конце концов, получается цепочка, состоящая из букв (и не содержащая символов). Это означает, что полученная цепочка может быть выведена из начального символа.
БНФ (Бэкуса — Наура форма) — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории.
БНФ используется для описания контекстно-свободных формальных грамматик. Если точнее, то для описания синтаксиса языков программирования, данных, протоколов.
БНФ-конструкция определяет конечное число символов. Также она определяет правила замены символа на какую-то последовательность букв и символов.
Процесс получения цепочки букв, можно определить поэтапно:
⁃ изначально имеется один символ (символы обычно заключаются в угловые скобки, а их название не несёт никакой информации).
⁃ этот символ заменяется на некоторую последовательность букв и символов, согласно одному из правил.
⁃ процесс повторяется (на каждом шаге один из символов заменяется на последовательность, согласно правилу).
⁃ в конце концов, получается цепочка, состоящая из букв (и не содержащая символов). Это означает, что полученная цепочка может быть выведена из начального символа.
Fully qualified domain name (FQDN)
Полностью определённое имя домена — это полный адрес веб-сайта, компьютера, сервера или аналогичного объекта, существующего в Интернете.
Полное доменное имя состоит из трех меток: имя хоста, доменное имя второго уровня и доменное имя верхнего уровня (TLD). Пример того, как выглядит полное доменное имя:
В этом примере «www» — это имя хоста, «networksolutions» — это домен второго уровня, а «com» — это TLD.
Единственный элемент, который может выглядеть неуместно — это конечная точка. Завершающие точки требуются протоколом системы доменных имен (DNS), поскольку они указывают на конец адреса.
Полностью определённое имя домена — это полный адрес веб-сайта, компьютера, сервера или аналогичного объекта, существующего в Интернете.
Полное доменное имя состоит из трех меток: имя хоста, доменное имя второго уровня и доменное имя верхнего уровня (TLD). Пример того, как выглядит полное доменное имя:
www.google.com.В этом примере «www» — это имя хоста, «networksolutions» — это домен второго уровня, а «com» — это TLD.
Единственный элемент, который может выглядеть неуместно — это конечная точка. Завершающие точки требуются протоколом системы доменных имен (DNS), поскольку они указывают на конец адреса.
Partially Qualified Domain Name (PQDN)
Частично определенное доменное имя (PQDN) очень похоже на полное доменное имя в том смысле, что оно используется для указания адреса веб-сайта. Разница в том, что PQDN относятся к одной или двум меткам из FQDN, включая либо имя хоста, либо имя домена. Пример того, как выглядит частичное доменное имя:
Можно заметить, что и полное доменное имя, и частичное доменное имя ведут на одну и ту же целевую страницу. Это связано с тем, что разработчики сайта настроили DNS для перенаправления посетителей с любого адреса на унифицированный указатель ресурса (URL) для домашней страницы веб-сайта
Создание таких перенаправлений является обычной практикой среди разработчиков веб-сайтов и автоматически настраивается в большинстве современных конструкторов веб-сайтов.
Частично определенное доменное имя (PQDN) очень похоже на полное доменное имя в том смысле, что оно используется для указания адреса веб-сайта. Разница в том, что PQDN относятся к одной или двум меткам из FQDN, включая либо имя хоста, либо имя домена. Пример того, как выглядит частичное доменное имя:
google.com.Можно заметить, что и полное доменное имя, и частичное доменное имя ведут на одну и ту же целевую страницу. Это связано с тем, что разработчики сайта настроили DNS для перенаправления посетителей с любого адреса на унифицированный указатель ресурса (URL) для домашней страницы веб-сайта
Создание таких перенаправлений является обычной практикой среди разработчиков веб-сайтов и автоматически настраивается в большинстве современных конструкторов веб-сайтов.
Зачем нужно полное доменное имя?
Полные доменные имена указывают уникальные адреса в Интернете, что делает их важными для работы в Интернете. Говоря простым языком: если у вас нет полного доменного имени, у вас нет веб-сайта, к которому люди могут получить доступ.
Они также необходимы для установки сертификатов SSL, что является еще одной функцией, ожидаемой от большинства веб-сайтов.
Помимо веб-сайтов, полные доменные имена полезны, когда вы хотите получить удаленный доступ к компьютеру. Это распространено в офисной среде, поскольку упрощает отслеживание активности на компьютере.
Также они помогают получить доступ к службам домена, таким как протокол передачи файлов (FTP) и электронная почта.
Полные доменные имена указывают уникальные адреса в Интернете, что делает их важными для работы в Интернете. Говоря простым языком: если у вас нет полного доменного имени, у вас нет веб-сайта, к которому люди могут получить доступ.
Они также необходимы для установки сертификатов SSL, что является еще одной функцией, ожидаемой от большинства веб-сайтов.
Помимо веб-сайтов, полные доменные имена полезны, когда вы хотите получить удаленный доступ к компьютеру. Это распространено в офисной среде, поскольку упрощает отслеживание активности на компьютере.
Также они помогают получить доступ к службам домена, таким как протокол передачи файлов (FTP) и электронная почта.
Асимметричное шифрование
Используется для защиты информации при ее передаче и предполагает использование двух ключей — открытого и закрытого.
Схема передачи данных между двумя субъектами (А и Б) с использованием открытого ключа выглядит следующим образом:
1. Субъект А генерирует открытый и закрытый ключи.
2. Субъект А передает открытый ключ субъекту Б.
3. Субъект Б шифрует пакет данных при помощи полученного открытого ключа и передает его А.
4. Субъект А расшифровывает полученную от Б информацию при помощи секретного, закрытого ключа.
В такой схеме перехват любых данных не имеет смысла, поскольку восстановить исходную информацию возможно только при помощи закрытого ключа, известного лишь получателю и не требующего передачи.
Используется для защиты информации при ее передаче и предполагает использование двух ключей — открытого и закрытого.
Схема передачи данных между двумя субъектами (А и Б) с использованием открытого ключа выглядит следующим образом:
1. Субъект А генерирует открытый и закрытый ключи.
2. Субъект А передает открытый ключ субъекту Б.
3. Субъект Б шифрует пакет данных при помощи полученного открытого ключа и передает его А.
4. Субъект А расшифровывает полученную от Б информацию при помощи секретного, закрытого ключа.
В такой схеме перехват любых данных не имеет смысла, поскольку восстановить исходную информацию возможно только при помощи закрытого ключа, известного лишь получателю и не требующего передачи.
Применение асимметричных алгоритмов
Асимметричное шифрование решает главную проблему симметричного метода, при котором для кодирования и восстановления данных используется один и тот же ключ.
С другой стороны, асимметричные алгоритмы гораздо медленнее симметричных, поэтому во многих криптосистемах применяются и те и другие.
Например, стандарты SSL и TLS используют асимметричный алгоритм на стадии установки соединения: с его помощью кодируют и передают ключ от симметричного шифра, которым и пользуются в ходе дальнейшей передачи данных.
Также они применяются для создания электронных подписей, которые генерируется с помощью закрытого ключа, а проверяются с помощью открытого.
Асимметричное шифрование решает главную проблему симметричного метода, при котором для кодирования и восстановления данных используется один и тот же ключ.
С другой стороны, асимметричные алгоритмы гораздо медленнее симметричных, поэтому во многих криптосистемах применяются и те и другие.
Например, стандарты SSL и TLS используют асимметричный алгоритм на стадии установки соединения: с его помощью кодируют и передают ключ от симметричного шифра, которым и пользуются в ходе дальнейшей передачи данных.
Также они применяются для создания электронных подписей, которые генерируется с помощью закрытого ключа, а проверяются с помощью открытого.
Виды алгоритмов симметричного шифрования
В зависимости от принципа работы алгоритмы симметричного шифрования делятся на два типа: блочные и потоковые.
Блочные алгоритмы шифруют данные блоками фиксированной длины. Если все сообщение или его финальная часть меньше размера блока, система дополняет его предусмотренными алгоритмом символами, которые так и называются дополнением.
Блочные алгоритмы: AES, RC5, Blowfish, Twofish
Потоковое шифрование данных предполагает обработку каждого бита информации с использованием гаммирования (изменение этого бита с помощью соответствующего ему бита псевдослучайной секретной последовательности чисел, которая формируется на основе ключа и имеет ту же длину, что и шифруемое сообщение). Как правило, биты исходных данных сравниваются с битами секретной последовательности с помощью логической операции XOR.
Потоковые алгоритмы: RC4, Salsa20, HC-256, WAKE
В зависимости от принципа работы алгоритмы симметричного шифрования делятся на два типа: блочные и потоковые.
Блочные алгоритмы шифруют данные блоками фиксированной длины. Если все сообщение или его финальная часть меньше размера блока, система дополняет его предусмотренными алгоритмом символами, которые так и называются дополнением.
Блочные алгоритмы: AES, RC5, Blowfish, Twofish
Потоковое шифрование данных предполагает обработку каждого бита информации с использованием гаммирования (изменение этого бита с помощью соответствующего ему бита псевдослучайной секретной последовательности чисел, которая формируется на основе ключа и имеет ту же длину, что и шифруемое сообщение). Как правило, биты исходных данных сравниваются с битами секретной последовательности с помощью логической операции XOR.
Потоковые алгоритмы: RC4, Salsa20, HC-256, WAKE
Достоинства и недостатки симметричного шифрования
Симметричные алгоритмы требуют меньше ресурсов и демонстрируют большую скорость шифрования, чем асимметричные алгоритмы.
Большинство симметричных шифров предположительно устойчиво к атакам с помощью квантовых компьютеров, которые в теории представляют угрозу для асимметричных алгоритмов.
Слабое место симметричного шифрования — обмен ключом. Поскольку для работы алгоритма ключ должен быть и у отправителя, и у получателя сообщения, его необходимо передать; однако при передаче по незащищенным каналам его могут перехватить и использовать посторонние (на практике во многих системах эта проблема решается шифрованием ключа с помощью асимметричного алгоритма).
Симметричные алгоритмы требуют меньше ресурсов и демонстрируют большую скорость шифрования, чем асимметричные алгоритмы.
Большинство симметричных шифров предположительно устойчиво к атакам с помощью квантовых компьютеров, которые в теории представляют угрозу для асимметричных алгоритмов.
Слабое место симметричного шифрования — обмен ключом. Поскольку для работы алгоритма ключ должен быть и у отправителя, и у получателя сообщения, его необходимо передать; однако при передаче по незащищенным каналам его могут перехватить и использовать посторонние (на практике во многих системах эта проблема решается шифрованием ключа с помощью асимметричного алгоритма).