Что лучше для представления графа — матрица или список?

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

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

Таким образом, матрицы чаще используют в теоретических исследованиях графа, а списки — в прикладных целях.

Числовое программное управление

Числовое программное управление - область техники, связанная с применением цифровых вычислительных устройств для управления производственными процессами.

Структурно в состав ЧПУ входят:
- пульт оператора, позволяющий вводить управляющую программу, задавать режимы работы; выполнить операцию вручную.

- дисплей — для визуального контроля режимов работы и редактируемой управляющей программы/данных.

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

ПЗУ — память, предназначенная для долговременного хранения системных программ и констант; информация из ПЗУ может только считываться.

ОЗУ — память, предназначенная для временного хранения управляющих программ и системных программ, используемых в данный момент.

Виртуализация — технология, которая позволяет создавать и использовать виртуальные версии ресурсов, таких как серверы, сети и рабочие станции. Это достигается с помощью ПО, известного как гипервизор.

Гипервизор — это слой ПО, который позволяет запускать несколько операционных систем на одном физическом сервере как отдельные виртуальные машины (ВМ). Гипервизоры бывают двух типов:

Гипервизор типа 1 (или "bare-metal"): Эти гипервизоры устанавливаются непосредственно на аппаратное обеспечение. Примеры включают VMware ESXi, Microsoft Hyper-V и Xen.

Гипервизор типа 2 (или "hosted"): Эти гипервизоры работают на операционной системе хоста, как обычное приложение. Примеры включают VMware Workstation и Oracle VirtualBox.

Что такое хвостовая рекурсия?

Хвостовая рекурсия - это способ рекурсивной функции, в котором вызов функции является последней операцией в теле функции.

Имеет одно важное преимущество - она может быть оптимизирована компилятором или интерпретатором, чтобы избежать проблемы переполнения стека при вызове рекурсивной функции многократно. Вместо того чтобы сохранять каждое состояние рекурсивного вызова на стеке, компилятор может использовать только один кадр стека для всех вызовов хвостовой рекурсии.

Пример хвостовой рекурсии в языках программирования, поддерживающих оптимизацию хвостовой рекурсии, таких как Scheme или Clojure, может быть таким:
(define (factorial-iter n acc)
(if (<= n 1)
acc
(factorial-iter (- n 1) (* acc n))))

(define (factorial n)
(factorial-iter n 1))

Сегментная адресация памяти

Сегментация - это деление памяти на сегменты.

Это механизм адресации, обеспечивающий существование нескольких независимых адресных пространств как в пределах одной задачи, так и в системе в целом для защиты задач от взаимного влияния.

С точки зрения разработчиков ПО, сегментация дает удобный способ совместного использования информации несколькими процессами. Конкретный сегмент может использоваться совместно с другими без нарушения требований его защиты.

Сегментация также предполагает естественное разделение программных строк и данных и отделение модуля от модуля.

Номера портов 

Как рассматривалось ранее, каждый протокол связан с определенным номером порта TCP или UDP. 

IANA — это организация, которая решает, какой номер порта является стандартным для каждого из протоколов. 

Когда создается новый протокол, его разработчики отправляют в IANA запрос на резервирование номера порта. Вместо того чтобы разрабатывать новый протокол и подавать заявку на номер порта, многие разработчики интернет-приложений используют для связи через интернет общие протоколы. 

Например, многие приложения становятся доступными через интернет благодаря интеграции с веб-сервером. В таких случаях HTTP используется для передачи необработанных данных в приложения и из них.

Звукообработка — это процесс изменения звуковых сигналов для достижения определенных звуковых эффектов или улучшения качества звука.

Несколько основных принципов звукообработки:

Эквализация: Это настройка уровней частот в звуковом сигнале. Эквализация позволяет подчеркнуть определенные частоты или уменьшить другие, что может сделать звук более ясным или добавить эффектов.

Компрессия: Этот процесс уменьшает разницу между самыми тихими и самыми громкими частями аудиосигнала. Он используется для контроля уровней громкости и создания более уравновешенного звучания.

Реверберация: Эффект, имитирующий эхо, которое звук вызывает при отражении от поверхностей. Реверберация добавляет пространственность и глубину звуку.

Дилэй: Эффект, задерживающий звуковой сигнал, создавая эхо или отклик. Может использоваться для создания эффектов пространства или для усиления звучания.

Фильтрация: Применение фильтров для усиления или ослабления определенных частот сигнала.

Стереообработка: Работа со стерео-изображением, включающая панорамирование (размещение звука между левым и правым каналами), создание пространственных эффектов и другие техники для улучшения пространственного восприятия звука.

Человеко-машинный интерфейс

Человеко-машинный интерфейс(ЧМИ) — широкое понятие, охватывающее инженерные решения, обеспечивающие взаимодействие человека-оператора с управляемыми им машинами.

Создание систем человеко-машинного интерфейса тесно увязано с понятиями эргономика и юзабилити.

Проектирование ЧМИ включает в себя:

- создание рабочего места: кресла, стола, или пульта управления, размещение приборов и органов управления и освещение рабочего места.

- далее рассматриваются взаимодействие оператора со всеми органами управления: их доступность и необходимые усилия, эффективность и скорость доступа, согласованность управляющих воздействий, расположение дисплеев и размеры надписей на них (всё это входит в сферу юзабилити).

Одной из наиболее сложных задач является создание эффективного ЧМИ рабочих мест сложных машин с множеством органов управления, например пилотов самолёта и космических кораблей.

В промышленных условиях ЧМИ чаще всего реализуется с использованием типовых средств: операторских панелей, компьютеров и типового программного обеспечения.

Автоматизированная система управления

Сокращённо АСУ — комплекс аппаратных и программных средств, а также персонала, предназначенный для управления различными процессами в рамках технологического процесса, производства, предприятия.

Важнейшая задача АСУ — повышение эффективности управления объектом на основе роста производительности труда и совершенствования методов планирования процесса управления.

Таким образом, можно выделить ряд целей:
- Предоставление лицу, принимающему решение (ЛПР), релевантных данных для принятия решений.- Ускорение выполнения отдельных операций по сбору и обработке данных.
- Снижение количества решений, которые должно принимать ЛПР.- Повышение уровня контроля и исполнительской дисциплины.
- Повышение оперативности управления.- Снижение затрат ЛПР на выполнение вспомогательных процессов.
- Повышение степени обоснованности принимаемых решений.

Нормализация баз данных — процесс организации данных в базе данных.

Это включает в себя создание таблиц и установление отношений между ними согласно правилам, которые помогают защитить данные и сделать базу данных более гибкой, устраняя избыточность и несогласованные зависимости.

Шесть нормальных форм — это шаги нормализации, каждый из которых предоставляет определенный уровень целостности данных.

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

- Существует также шестая нормальная форма (6NF), которая предназначена для обработки временных данных и рассматривается как конечный этап нормализации для баз данных, которые требуют работы с временными интервалами.

Примеры нормализации баз данных

1. CRM-системы (Управление взаимоотношениями с клиентами):
• Исходные данные: таблица Клиенты с полями Имя, Фамилия, Телефон, Адрес, Заказы.
• Нормализация: разделение на таблицы Клиенты (с полями Имя, Фамилия, Телефон, Адрес) и Заказы (с полями ID_клиента, Дата_заказа, Сумма_заказа), чтобы избежать дублирования информации о клиенте при каждом новом заказе.

2. Интернет-магазины:
• Исходные данные: таблица Товары с полями Название, Описание, Цена, Категория, Производитель.
• Нормализация: создание отдельных таблиц Категории (с полями ID_категории, Название_категории) и Производители (с полями ID_производителя, Название_производителя), что позволяет уменьшить избыточность и упростить обновление информации о категориях и производителях.

3. Библиотечные системы:
• Исходные данные: таблица Книги с полями Название, Автор, Жанр, Год_издания, Издательство.
• Нормализация: разделение на таблицы Книги (с полями Название, Год_издания), Авторы (с полями ID_автора, Имя_автора), Жанры (с полями ID_жанра, Название_жанра) и Издательства (с полями ID_издательства, Название_издательства), что облегчает поиск и управление данными.

4. Учет рабочего времени:
• Исходные данные: таблица Табель с полями Сотрудник, Дата, Часы_работы, Проект.
• Нормализация: создание таблиц Сотрудники (с полями ID_сотрудника, Имя, Фамилия), Проекты (с полями ID_проекта, Название_проекта) и Табель (с полями ID_сотрудника, Дата, Часы_работы, ID_проекта), что позволяет точно отслеживать время, затраченное на разные проекты.

LOLCODE — это уникальный язык программирования, основанный на интернет-меме "LOLcats". Программы на LOLCODE выглядят как текст на "языке" LOLcats.

Пример простой программы на LOLCODE, которая выводит "Hello World!":

HAI 1.2
CAN HAS STDIO?
VISIBLE "HAI WORLD!"
KTHXBYE

HAI 1.2 — начало программы, указывающее версию языка.
CAN HAS STDIO? — импорт стандартной библиотеки ввода-вывода.
VISIBLE "HAI WORLD!" — вывод строки "HAI WORLD!" на экран.
KTHXBYE — завершение программы.

Текст на "языке" LOLcats обычно выглядит как забавные и искаженные фразы, часто сопровождаемые изображениями кошек.

I CAN HAS CHEEZBURGER?
OH HAI! U CAN HAS CHEEZBURGER!

Cтиль письма стал популярен благодаря интернет-мемам с изображениями кошек и смешными подписями.

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

Основные методы процедурной графики:

1. Фракталы:

Геометрические фигуры, которые повторяются на разных масштабах. Они используются для создания природных объектов, таких как горы, деревья и облака. Примером фрактала является множество Мандельброта.

2. Шум Перлина:

Метод генерации псевдослучайных значений, который используется для создания текстур и поверхностей. Он часто применяется для моделирования природных явлений, таких как земля, вода и огонь.

3. L-системы:

(Системы Линдемаера) — это формальные грамматики, используемые для моделирования роста растений и других органических структур. Они позволяют создавать сложные и реалистичные модели деревьев, кустарников и других растений.

4. Процедурные текстуры:

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

5. Процедурная анимация:

Использует алгоритмы для автоматического создания движений и деформаций объектов. Это позволяет создавать реалистичные анимации без необходимости ручного управления каждым кадром.

Пример кода на Python для генерации шума Перлина:

import numpy as np
import matplotlib.pyplot as plt

def perlin_noise(size, scale):
    def f(t):
        return 6*t**5 - 15*t**4 + 10*t**3

    def lerp(a, b, t):
        return a + t * (b - a)

    def gradient(h, x, y):
        vectors = np.array([[0,1], [0,-1], [1,0], [-1,0]])
        g = vectors[h % 4]
        return g[:, :, 0] * x + g[:, :, 1] * y

    lin = np.linspace(0, scale, size, endpoint=False)
    x, y = np.meshgrid(lin, lin)
    p = np.arange(256, dtype=int)
    np.random.shuffle(p)
    p = np.stack([p, p]).flatten()
    xi = x.astype(int)
    yi = y.astype(int)
    xf = x - xi
    yf = y - yi
    u = f(xf)
    v = f(yf)
    n00 = gradient(p[p[xi]+yi], xf, yf)
    n01 = gradient(p[p[xi]+yi+1], xf, yf-1)
    n11 = gradient(p[p[xi+1]+yi+1], xf-1, yf-1)
    n10 = gradient(p[p[xi+1]+yi], xf-1, yf)
    x1 = lerp(n00, n10, u)
    x2 = lerp(n01, n11, u)
    return lerp(x1, x2, v)

size = 512
scale = 10
noise = perlin_noise(size, scale)
plt.imshow(noise, cmap='gray')
plt.colorbar()
plt.show()

Этот код генерирует изображение шума Перлина размером 512x512 пикселей и отображает его с помощью библиотеки Matplotlib.

Доменные имена — уникальные адреса, используемые для идентификации веб-сайтов в интернете. Служат для упрощения доступа к ресурсам, так как запомнить доменное имя гораздо проще, чем числовой IP-адрес. Доменные имена состоят из нескольких частей, разделенных точками, иерархически организованных от правого к левому.

Основные компоненты доменного имени:

Корневой домен:
Самая правая часть доменного имени, обычно обозначается точкой ("."). В большинстве случаев пользователи не видят корневой домен, так как он подразумевается автоматически.

Домен верхнего уровня (TLD):
Часть доменного имени, следующая сразу за корневым доменом. Примеры TLD включают .com, .org, .net, .ru и многие другие. Существуют также новые TLD, такие как .tech, .store и т.д.

Домен второго уровня:
Это часть доменного имени, расположенная слева от TLD. Например, в доменном имени example.com, "example" является доменом второго уровня.

Поддомены:
Это части доменного имени, расположенные слева от домена второго уровня. Например, в доменном имени blog.example.com, "blog" является поддоменом.

Пример структуры доменного имени:

www.example.com
│ │ │
│ │ └ Домен второго уровня
│ └ Поддомен
└ Префикс (необязательный)

Регистрация доменных имен осуществляется через аккредитованных регистраторов доменов. Процесс регистрации включает выбор доступного доменного имени и его оплату на определенный период времени (обычно от одного года и более).

DNS (Domain Name System) — система, которая переводит доменные имена в IP-адреса, необходимые для маршрутизации запросов в интернете. Когда пользователь вводит доменное имя в браузере, DNS-серверы выполняют поиск соответствующего IP-адреса и направляют запрос к нужному серверу.

SSL/TLS (Secure Socket Layer/Transport Layer Security) - протокол, который используется для шифрования данных, передаваемых по сети. Он обеспечивает защиту данных от несанкционированного доступа и перехвата. SSL/TLS состоит из двух основных компонентов: SSL (Secure Socket Layer) и TLS (Transport Layer Security).

SSL был разработан компанией Netscape Communications в 1994 году и был впервые представлен в Netscape Navigator 2.0. Впоследствии он был заменен на TLS, который был разработан в IETF (Internet Engineering Task Force) в начале 1990-х годов. TLS 1.0 был опубликован в 1999 году, а TLS 1.1 и TLS 1.2 были опубликованы в 2006 и 2008 годах соответственно.

SSL/TLS использует асимметричное шифрование для генерации ключей шифрования и обмена информацией между клиентом и сервером. Во время установки соединения клиент и сервер обмениваются информацией о своих сертификатах, которые содержат открытые ключи. Затем клиент и сервер используют эти открытые ключи для генерации сессионного ключа, который будет использоваться для шифрования и дешифрования данных.

Оперативная память - высокоскоростная электронная память, которая используется для хранения данных и инструкций, которые процессор использует для выполнения программ. ОЗУ является временным хранилищем данных и не сохраняет информацию после выключения компьютера.

ОЗУ состоит из множества ячеек памяти, каждая из которых может хранить бит (0 или 1). Эти ячейки объединяются в блоки, которые образуют адресуемые блоки памяти. Каждый блок имеет свой адрес, по которому процессор может получить доступ к данным, хранящимся в этом блоке.

Когда процессор загружает программу в память, он размещает инструкции и данные программы в различных блоках ОЗУ. Процессор использует адресную шину для определения местоположения блока памяти, в котором хранятся данные или инструкции. Затем процессор использует данные из ОЗУ для выполнения операций и обработки информации.

ОЗУ имеет ограниченную емкость, поэтому если программа использует больше памяти, чем доступно в ОЗУ, процессор может использовать виртуальную память. Виртуальная память использует жёсткий диск компьютера для хранения данных, которые не помещаются в ОЗУ. При этом часть данных перемещается из ОЗУ на жёсткий диск, чтобы освободить место для новых данных.

Некоторые из самых сложных алгоритмов и структур данных в реальных примерах:

1. Алгоритм Дейкстры для нахождения кратчайшего пути между двумя вершинами в графе. Он может использоваться, например, в системах навигации GPS для определения наиболее эффективного маршрута от точки А до точки Б.

2. Алгоритм оптимального кодирования Хаффмана: Этот алгоритм используется для сжатия данных с минимальной потерей информации. Он основан на частоте встречаемости символов в исходном наборе данных и строит оптимальное префиксное кодирование для кодирования символов. Используется в сжатии файлов, видео и аудио данных.

3. Структура данных B-дерево: B-дерево является сбалансированным деревом поиска, которое эффективно поддерживает операции вставки, удаления и поиска элементов. Оно широко используется в базах данных и файловых системах для хранения и обработки больших объемов данных.

4. Алгоритм динамического программирования: Этот алгоритм используется для решения оптимизационных задач путем разделения задачи на более мелкие подзадачи и рекурсивного решения этих подзадач. Алгоритм динамического программирования может быть применен в различных областях, включая решение задачи коммивояжера, оптимизацию расписания и анализ последовательности ДНК.

Примеры экзотических языков запросов данных:

XQuery: язык запросов, предназначенный для работы с данными в формате XML.
Ищем все книги, написанные Дж. К. Роулинг, и возвращаем их заголовки:

for $book in doc("books.xml")//book
where $book/author = "J.K. Rowling"
return <result>{ $book/title }</result>

SPARQL: язык запросов для работы с данными в формате RDF (Resource Description Framework).
Ищем всех людей, знакомых с Алисой, и возвращаем их имена:

PREFIX foaf: <http://xmlns.com/foaf/0.1/>
SELECT ?name WHERE {
 ?person foaf:name ?name .
 ?person foaf:knows <http://example.org/Alice>
}

MQL (MongoDB Query Language): язык запросов для работы с документоориентированной базой данных MongoDB.
Ищем все книги, написанные Дж. К. Роулинг:

db.books.find({ "author": "J.K. Rowling" })

Gremlin: язык запросов для работы с графовыми базами данных, такими как Apache TinkerPop.
Ищем имена всех друзей Алисы:

g.V().has('name', 'Alice').out('knows').values('name')

Cypher: язык запросов для работы с графовыми базами данных, такими как Neo4j.
Ищем имена всех друзей Алисы:

MATCH (p:Person)-[:KNOWS]->(friend)
WHERE p.name = 'Alice'
RETURN friend.name

Векторизация (параллельные вычисления)

Векторизация — вид распараллеливания программы, при котором однопоточные приложения, выполняющие одну операцию в каждый момент времени, модифицируются для выполнения нескольких однотипных операций одновременно.

Скалярные операции, обрабатывающие по паре операндов заменяются на операции над массивами, обрабатывающие несколько элементов вектора в каждый момент времени.

Пример:
Показан фрагмент программы, который поэлементно перемножает два массива, состоящие из чисел:
for (i = 0; i < 1024; i++)
    C[i] = A[i] * B[i];
   
Данный цикл может быть векторизован так:
for (i = 0; i < 1024; i+=4)
     C[i:i+3] = A[i:i+3] * B[i:i+3];
    
Запись C[i:i+3] означает вектор из 4 элементов — от C[i] до C[i+3] включительно, а под * понимается операция поэлементного умножения векторов.

Функции CPU

CPU (central processing unit) или же процессор — основной элемент аппаратного обеспечения вычислительного устройства, с помощью которого происходит обработка информации.

Процессор состоит из ядра процессора, состоящее из арифметико-логического устройства, внутренней памяти (регистров) и быстрой памяти (кэш), а также шины - устройства управления всеми операциями и внешними компонентами. Через шины в CPU попадает информация, которую затем обрабатывает ядро.

Таким образом, в основные функции процессора входит:
 1. обработка информации с помощью арифметических и логических операций;
 2. управление работой всего аппаратного обеспечения компьютера.