Computer Science

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 позволяет создавать резервные копии выбранных данных в промежутки времени между запланированными сеансами резервного копирования на постоянной основе:  ⁃ Путем отслеживания изменений в указанных файлах/папках  ⁃ Путем отслеживания изменений файлов, внесенных конкретными приложениями Из данных, выбранных для резервного копирования, можно выбрать определенные файлы для непрерывной защиты данных. Система будет создавать копию каждого изменения, внесенного в эти файлы. Их можно будет восстановить в состояние на время последнего изменения.

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

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

Станьте уверенным разработчиком главного языка “энтерпрайза”, Java, вместе с Хекслетом! Кому подойдёт обучение: ✅ Новичкам, которые хотят освоить профессию с нуля. ✅ Тем, кто уже пробовал учиться самостоятельно, но чувствует потребность в наставнике. ✅ Тем, кто пробовал учиться на сторонних курсах, но до сих пор испытывает сложности в самостоятельном написании кода. Курс поможет освоить язык, алгоритмы и структуры данных, работу с микросервисами, фреймворком Spring Boot, базами данных и инфраструктурой. Начните прямо сейчас, переходите по ссылке выше. Вводные обзорные курсы профессии доступны бесплатно сразу после регистрации👆👆 Черная пятница!  Подарок на выбор при покупке профессии или вторая программа за полцены 🎁👻

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

ООП или объектно-ориентированное программирование ООП — это подход, при котором программа рассматривается как набор объектов, взаимодействующих друг с другом. ООП обычно определяют через четыре принципа. (иногда количество сокращают до трех — опускают понятие абстракции)  1. Абстракция — способ выделить набор наиболее важных атрибутов и методов и исключить незначимые.  2. Инкапсуляция — свойство системы, позволяющее объединить данные и методы, работающие с ними в классе и скрыть детали реализации от пользователя.   3. Наследование — описание нового класса на основе уже существующего с частично или полностью заимствующейся функциональностью.   4. Полиморфизм — когда методы разных объектов могут выполнять задачи разными способами. Например, у «человека» есть метод «работать». У «программиста» — это будет означать написание кода, а у «директора» — рассмотрение управленческих вопросов. Но глобально и то, и то есть работа.

Процедурное программирование  программирование, при котором последовательно выполняемые операторы можно собрать в подпрограммы, чтобы сообщить компьютеру, что он должен делать шаг за шагом, чтобы завершить задачу под рукой. Процедурное программирование является отражением архитектуры традиционных ЭВМ, которая была предложена Фон Нейманом в 1940-х годах. Теоретической моделью процедурного программирования служит машина Тьюринга. Эта парадигма использует линейный нисходящий подход и рассматривает данные и процедуры как два разных объекта. Основываясь на концепции вызова процедуры, процедурное программирование делит программу на процедуры, которые также известны как процедуры или функции, просто содержащие последовательность шагов, которые необходимо выполнить.

RAID-массив RAID (Redundant Array of Independent Disks) — технология виртуализации данных, которая объединяет несколько дисков в логический элемент для повышения производительности. Соответственно, минимальное количество требуемых дисков — 2. Есть несколько видов RAID-массива: RAID 0 — принцип работы - чередование. Массив при котором информация разбивается на одинаковые по длине блоки, а затем записывается поочерёдно на каждый диск в структуре (фактическое увеличение производительности в 2 раза) RAID 1 — принцип работы — «зеркалирование». Представляет собой параллельную запись информации с основного диска на другие — дублирующие.  RAID 10 (1+0) — совмещает в себе всё самое лучшее из RAID 1 и RAID 0 RAID 5 — схож по своему принципу работы с RAID 1. Только тут потребуется минимум 3 накопителя, на одном из которых будет храниться продублированная информация

Что такое избыточность данных? Избыточность данных относится к практике хранения данных в двух или более местах в базе данных или системе хранения данных. Потому что если каким то образом данные будут повреждены, их можно будет легко восстановить, не останавливая при этом рабочий процесс. Избыточность данных может возникать намеренно или случайно. Если это делается преднамеренно, то чаще всего эти данные используются для резервного копирования или аварийного восстановления. Если же это делается случайно, дублирование данных может привести к их несоответствию. Также существуют другие альтернативы для защиты и восстановления данных. Например, есть бэкапы непрерывная защита данных (CDP), shapShot и образы.

Виды и типы связей между таблицами в реляционных базах данных В сего существует три вида связей между таблицами баз данных: • связь один к одному Самая редко встречаемая связь между таблицами. Таблицы будут связаны один к одному тогда, когда одному объекту таблицы А соответствует один объект таблицы Б, и наоборот. Если вы видите такую связь, то смело моно объединить две таблицы в одну. • связь один ко многим Реализуется тогда, когда объекту А может принадлежать или же соответствовать несколько объектов Б, но объекту Б может соответствовать только один объект А. • связь многие ко многим Реализуется в том случае, когда нескольким объектам из таблицы А может соответствовать несколько объектов из таблицы Б, и в тоже время нескольким объектам из таблицы Б соответствует несколько объектов из таблицы А.

Нормализация Нормализация — процесс разделения данных по отдельным связанным таблицам. Нормализация устраняет избыточность данных и тем самым избежать нарушения целостности данных при их изменении. Существуют 7 нормальных форм: 1NF (Первая нормальная форма) предполагает, что сохраняемые данные на пересечении строк и столбцов должны представлять скалярное значение, а таблицы не должны содержать повторяющихся строк. 2NF — каждый столбец, не являющийся ключом, должен зависеть от первичного ключа. 3NF — каждый столбец, не являющийся ключом, должен зависеть только от первичного ключа. Нормальная форма Бойса-Кодда (BCNF) является немного более строгой версией третьей нормальной формы. 4NF применяется для устранения многозначных зависимостей.  5NF разделяет таблицы на более малые таблицы для устранения избыточности данных. 6NF — каждое ограничение в связях между таблицами должно зависеть только от ограничений ключа и ограничений домена, где домен представляет набор допустимых значений для столбца

Остался в РФ и думаешь о своем будущем? Посмотри на IT! Это отличный шанс для всех, ведь в 2022 году на рынке освободилось место для новых специалистов после оттока айтишников из страны. Поступай в  Kata Academy на Java-разработчика и плати за обучение только после гарантированного трудоустройства с зарплатой от 100 000₽.  Тебя ждут 7 месяцев интенсивного обучения: ты изучишь только нужный стек технологий и будешь полностью подготовлен к выходу на работу в Москве или Санкт-Петербурге, куда тебе предстоит переехать после выпуска по условиям договора со школой.  По окончании обучения школа продолжит поддерживать тебя и участвовать в развитии твоей карьеры в течение 2-х лет после выпуска. Поступай в Kata Academy, чтобы стать Java-разработчиком уже в мае: https://clck.ru/32cMcP

3 уровня детализации в ER-моделях и моделях данных Концептуальная модель данных — схема наивысшего уровня с минимальным количеством подробностей. Достоинство: возможность отобразить общую структуру модели и всю архитектуру системы. Менее масштабные системы могут обойтись и без этой модели. В этом случае можно сразу переходить к логической модели. Логическая модель данных содержит более подробную информацию, нежели концептуальная модель. На этом уровне определяются более подробные операционные и транзакционные сущности. Логическая модель не зависит от технологии, в которой она будет применяться. Физическая модель данных: на основе каждой логической модели данных можно составить одну или две физических модели. В последних должно присутствовать достаточно технических подробностей для составления и внедрения самой базы данных.

ER модель базы данных Схема «сущность-связь», ERD или ER-диаграмма — это разновидность блок-схемы, где показано, как разные «сущности» связаны между собой внутри системы. Основные концепции модели:  ⁃ сущность — множество объектов реального мира с одинаковыми свой­ствами. Представляет собой основное содержание того явления или процесса, о котором необходимо собрать информа­цию  ⁃ атрибут — средство, с помощью которого определяются свойства сущности или связи. Наименование атрибута должно быть уникальным для кон­кретной сущности, но может быть одинаковым для разных сущностей.   ⁃ связи — отношение между экземплярами двух (и более) разных сущностей. Механизм связей используется для того, чтобы опре­делить взаимоотноше­ния между сущностями. ER-диаграммы чаще всего применяются для проектирования и отладки реляционных баз данных