Computer Science

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

Главная загрузочная запись (MBR) Нулевой сектор физического жёсткого диска содержит так называемую главную загрузочную запись (MBR — Master Boot Record). При начальной загрузке компьютера с жёсткого диска BIOS считывает этот сектор в оперативную память и передаёт управление содержащемуся в нём коду начального загрузчика. MBR логически можно разделить на три области: код начального загрузчика, таблицу разделов и сигнатуру — слово со значением AA55h, занимающее последние два байта MBR. BIOS проверяет сигнатуру, чтобы убедиться в корректности MBR; если сигнатура не равна указанному значению, загрузка не выполнения и выдаётся сообщение об ошибке.  Начальный загрузчик, находящийся в MBR, в общем случае определяет, какой из разделов диска является активным, загружает в память первый сектор этого раздела и передаёт ему управление.

Таблица разделов Таблица разделов — часть главной загрузочной записи (MBR), состоящая из четырёх записей по 16 байт. Каждая запись описывает один из разделов жёсткого диска. Первая запись находится по смещению 1BEh от начала сектора, содержащего MBR, каждая последующая запись вплотную примыкает к предыдущей. Для создания на диске более 4 разделов используются расширенные разделы, позволяющие создать неограниченное количество логических дисков внутри себя. Адреса начала и конца раздела задаются в формате CHS, используемом традиционными функциями дискового сервиса BIOS, из-за чего номер цилиндра разорван на две части: старшие два бита хранятся в двух старших битах слова, отведённого под номера цилиндра и сектора; за ними следуют шесть бит номера сектора, а младшие восемь бит номера цилиндра занимают весь младший байт слова. Если задать корректный адрес с помощью формата CHS невозможно, все три байта полей начала и конца раздела должны содержать FFh

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

Сетевой концентратор или хаб Класс устройств для объединения компьютеров в сетях Ethernet с применением кабельной инфраструктуры типа витая пара. В настоящее время вытеснены сетевыми коммутаторами. Сетевые концентраторы также могли иметь разъёмы для подключения к существующим сегментам сети на базе толстого или тонкого коаксиального кабеля. Концентратор работает на физическом уровне сетевой модели OSI, ретранслируя входящий сигнал с одного из портов в сигнал на все остальные порты. Таким образом, несмотря на возможность реализации на многопортовых хабах физической топологии "звезда", логически сеть продолжает работать в режиме с общей средой, свойственном Ethernet: пропускная способность сети разделена между всеми устройствами, а передача ведется в режиме полудуплекса. Коллизии обрабатываются аналогично сети Ethernet на других носителях — устройства самостоятельно прекращают передачу и возобновляют попытку через случайный промежуток времени, говоря современным языком, концентратор объединяет устройства в одном домене коллизий.

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

Метод цепочек — метод разрешения коллизий Метод цепоцек — внешнее или открытое хеширование.  Технология сцепления элементов состоит в том, что элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список. В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш-значение ключа равно i; если таких элементов в множестве нет, в позиции i записан NULL.  Преимущества:  ⁃ Метод цепочек эффективен и имеет чёткую структуру.   ⁃ Его удобно использовать, когда неизвестно количество коллизий на  одно хеш-значение.   ⁃ Поиск нужного значения будет происходит за минимально возможное время.  Недостатки:  ⁃ Он использует много памяти: для хранения n хеш-значений выделяется ~n^2 ячеек памяти.   ⁃ Время работы метода O(n^2).

Профессия «Фронтенд-разработчик» на Хекслете включает в себя гораздо больше, чем кажется на первый взгляд. На курсе мы даем даем фундаментальные основы и развиваем алгоритмическое мышление. Несколько сотен практических заданий в онлайн-тренажере – лишь часть обучения. Вы будете участвовать в разработке открытых проектов Хекслета на GitHub, напишите 4 полноценных приложения для бизнеса и попрактикуетесь в решении реальных кейсов от компаний-партнеров. Цель любого обучения – это трудоустройство. Мы пройдем путь до первой работы в IT вместе с вами.  Начните прямо сейчас, переходите по ссылке выше. Вводные ознакомительные курсы профессии доступны бесплатно сразу после регистрации👆👆👆 Оцените формат и решите, стоит ли продолжать!

Хеширование  Hashing – это преобразование входного массива данных определенного типа и произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свертки, а их результаты называют хешем, хеш-кодом, хеш-таблицей или дайджестом сообщения  Хеширование является распространенным методом обеспечения быстрого доступа к информации, хранящейся во внешней памяти. Оно полезно, когда широкий диапазон возможных значений должен быть сохранен в малом объеме памяти, и нужен способ быстрого, практически произвольного доступа.  Хэш-таблицы часто применяются в базах данных, и, особенно, в языковых процессорах типа компиляторов и ассемблеров, где они повышают скорость обработки таблицы идентификаторов. В качестве использования хеширования в повседневной жизни можно привести примеры распределение книг в библиотеке по тематическим каталогам, упорядочивание в словарях по первым буквам слов, шифрование специальностей в вузах и т.д.

Метод открытой адресации Метод открытой адресации или закрытое хеширование — один из методов разрешение коллизий. В случае открытой адресации, если ячейка с вычисленным индексом занята, то можно просто просматривать следующие записи таблицы по порядку до тех пор, пока не будет найден ключ K или пустая позиция в таблице. Для вычисления шага можно также применить формулу, которая и определит способ изменения шага.  Преимущества:  ⁃ Использует мало памяти: для хранения n значений резервируется только  n ячеек в памяти   ⁃ Удобно использовать при малом количестве коллизий на одно хеш- значение( не более 3-х)  Недостатки:  ⁃ Поиск определённого значения в хеш-таблице неоптимально.  ⁃ Время работы O(n^2)   ⁃ Нет чёткой структуры, хеш-значения могут храниться не в отсортированном виде

Breadth-First Search Поиск в ширину позволяет найти кратчайший (содержащий наименьшее число ребер) путь из одной вершины графа до всех остальных вершин. BFS следует концепции «расширяйся, поднимаясь на высоту птичьего полета» («go wide, bird’s eye-view»). Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. В нем сначала посещаются все вершины, смежные с текущей, а затем их потомки. Время выполнения BFS составляет O(V + E), где V — количество вершин. E — количество ребер.

Что такое хеш-таблицы? Хеш-таблица — это контейнер для хранения пар ключей и их значений. По сути это ассоциативный массив, в котором ключ представлен в виде хеш-функции. Главное свойство hash-таблиц — три операции: вставка, поиск и удаление — в среднем выполняются за время O(1), Принято считать, что хорошей, с точки зрения практического применения, является такая хеш-функция, которая удовлетворяет следующим условиям:   ⁃ функция должна быть простой с вычислительной точки зрения;   ⁃ функция должна распределять ключи в хеш-таблице наиболее равномерно;   ⁃ функция не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов;   ⁃ функция должна минимизировать число коллизий – то есть ситуаций, когда разным ключам соответствует одно значение хеш- функции(ключи в этом случае называются синонимами ). Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа.  Именно с ее помощью мы находим индекс, зная который, можно выполнить требующую операцию.

Depth-First Search Поиск в глубину является одним из основных алгоритмов обхода графа. Если говорить простыми словами, то обход графа — это переход от одной его вершины к другой в поисках свойств связей этих вершин.  DFS следует концепции «погружайся глубже, головой вперед» («go deep, head first»). Идея заключается в том, что мы двигаемся от начальной вершины по определенному пути до тех пор, пока не достигнем конца пути или искомой вершины. Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад и идем по другому маршруту. Поскольку мы обходим каждого «соседа» каждого узла, игнорируя тех, которых посещали ранее, мы имеем время выполнения, равное O(V + E), где V — количество вершин. E — количество ребер.

Алгоритм Дейкстры Алгоритм Дейкстры — это метод, который находит кратчайший путь от одной вершины графа к другой. Для этого алгоритма граф должен быть взвешенный, но не иметь ребер с отрицательным весом, т.е. таких, при прохождении через которые длина пути как бы уменьшается. Алгоритм Дейкстры пошаговый. Сначала выбирается точка, от которой будут отсчитываться пути. Затем алгоритм поочередно ищет самые короткие маршруты из исходной точки в другие. Вершины, где он уже побывал, отмечает посещенными. Алгоритм использует посещенные вершины, когда рассчитывает пути для непосещенных. Сложность алгоритма изменяется в зависимости от реализации. Например: Если вершины хранятся в простом массиве и для поиска минимума используется алгоритм линейного поиска, временная сложность алгоритма Дейкстры составляет O(V²). Если же используется очередь с приоритетами, реализованная на основе двоичной кучи, то мы получаем O(E log V). Если же очередь с приоритетами была реализована на основе кучи Фибоначчи, получается наилучшая оценка сложности O(V log V + E).

Коллизии хеш-функции  Коллизия хеш-функции — это когда у двух разных входных элементов таблицы hash будет одинаковым. Коллизии встречаются в разнообразных алгоритмах хеширования, однако это не является нормой и в «правильных» алгоритмах их возникновение сведено к минимальному значению. Но в то же время, когда приходится работать с большими таблицами хеширования, то их возникновение неизбежно. При возникновении коллизий необходимо найти новое место для хранения ключей, претендующих на одну и ту же ячейку хеш-таблицы.  Причем, если коллизии допускаются, то их количество необходимо минимизировать. В некоторых специальных случаях удается избежать коллизий вообще. Например, если все ключи элементов известны заранее, то для них можно найти некоторую инъективную хеш-функцию, которая распределит их по ячейкам хеш-таблицы без коллизий. Хеш-таблицы, использующие подобные хеш-функции, не нуждаются в механизме разрешения коллизий, и называются хеш-таблицами с прямой адресацией.

Что лучше для представления графа — матрица или список? Лучше использовать матрицы, если:  ⁃ число вершин графа невелико;  ⁃ число рёбер графа относительно большое;  ⁃ в алгоритме часто требуется проверять, соединены ли между собой две вершины;  ⁃ в алгоритме используются фундаментальные понятия теории графов, например, связность графа. Списки инцидентности целесообразнее использовать когда:  ⁃ число вершин графа велико;  ⁃ число рёбер графа относительно невелико;  ⁃ граф формируется по какой-либо модели;  ⁃ во время действия алгоритма часто требуется модифицировать граф;  ⁃ в алгоритме часто используются локальные свойства вершин, например, например, окрестности вершин. Таким образом, матрицы чаще используют в теоретических исследованиях графа, а списки — в прикладных целях.

Способы представления графа матрица смежности  двумерная матрица, в которой и число строк, и число столбцов равно числу вершин графа. В ячейки матрицы смежности записываются числа 0 или 1 в зависимости от того, соединены соответствующие вершины рёбрами или нет. матрица инцидентности  матрица размера n x m, где n - число вершин графа, m - число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы - рёбрам графа. списки инцидентности Представляют собой граф в виде массива связанного списка. Индекс массива представляет вершину, и каждый элемент в его связанном списке представляет другие вершины, которые образуют ребро с вершиной.

Граф как структура данных Структура данных графа представляет собой набор узлов, которые имеют данные и связаны с другими узлами. Точнее, граф - это структура данных (V, E), которая состоит из:  ⁃ Коллекции вершин V.  ⁃ Набора ребер E, представленный в виде упорядоченных пар вершин (u, v). Терминология графа:  ⁃ смежность Вершина смежна с другой вершиной, если есть ребро, соединяющее их.   ⁃ путь Последовательность ребер, которая позволяет вам перейти от вершины A к вершине B  ⁃ ориентированный граф Граф, в котором есть ребро (u, v) не обязательно означает, что также имеется ребро (v, u). Ребра в таком графике представлены стрелками, чтобы показать направление ребра.

Непрерывная защита данных (CDP) Из соображений производительности резервные копии обычно создаются через регулярные, но достаточно долгие промежутки времени. Если система временно повреждена, изменения данных, внесенные в период между последним созданием резервной копии и сбоем системы, будут утрачены. Функциональность CDP позволяет создавать резервные копии выбранных данных в промежутки времени между запланированными сеансами резервного копирования на постоянной основе:  ⁃ Путем отслеживания изменений в указанных файлах/папках  ⁃ Путем отслеживания изменений файлов, внесенных конкретными приложениями Из данных, выбранных для резервного копирования, можно выбрать определенные файлы для непрерывной защиты данных. Система будет создавать копию каждого изменения, внесенного в эти файлы. Их можно будет восстановить в состояние на время последнего изменения.

Функциональное программирование Функциональное программирование сильно отличается как от процедурного программирования, так и от ООП, поскольку в нем используются математические функции. Благодаря этому операции выполняются только на основе введенных входных данных, и они не зависят от временных или скрытых переменных. Смысл функционального программирования в том, чтобы описать не сами чёткие шаги к цели, а правила, по которым компилятор сам должен дойти до нужного результата. Последовательность выполнения подпрограмм определяет сам код и компилятор, а не программист. Каждая команда — это какое-то правило, поэтому нет разницы, когда мы запишем это правило, в начале или в конце кода. Главное, чтобы у нас это правило было, а компилятор сам разберётся, в какой момент его применять.