Тема 2.1
Основы алгоритмизации
Понятие алгоритма, эффективность и сравнение алгоритмов, способы формализации, языки программирования.
Понятие вычислительного алгоритма
Свойства алгоритма:
- дискретность — процесс разбит на отдельные шаги;
- определённость (детерминированность) — каждый шаг однозначен, повторение даёт тот же результат;
- результативность и конечность — результат получается за конечное число шагов;
- массовость — применимость ко всему классу однотипных задач;
- понятность — использует только команды, доступные исполнителю.
Эффективность и сравнение алгоритмов
Эффективность оценивают по затратам времени (число элементарных операций) и памяти как функции размера входа n. Сравнивают по асимптотической скорости роста — O-нотации: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ). Константы и младшие члены отбрасываются; различают оценку в худшем, среднем и лучшем случаях.
| Сложность | Типичный пример | n = 10⁶, условных операций |
|---|---|---|
| O(log n) | двоичный поиск в отсортированном массиве | ≈ 20 |
| O(n) | линейный поиск, один проход массива | 10⁶ |
| O(n log n) | быстрая сортировка, сортировка слиянием | ≈ 2·10⁷ |
| O(n²) | пузырьковая сортировка, сортировка вставками | 10¹² |
| O(2ⁿ) | полный перебор подмножеств | астрономически много |
O-нотация отвечает на вопрос «во сколько раз вырастет время, если вход вырастет в 10 раз?». O(n): в 10 раз. O(n²): в 100 раз. O(log n): прибавится константа. O(2ⁿ): даже +10 элементов удвоит время десять раз (в 1024 раза). Поэтому «какой алгоритм» важнее, чем «какой компьютер»: пузырьковая сортировка на суперкомпьютере проиграет быстрой сортировке на телефоне уже на миллионе элементов.
Поиск слова в словаре на 100 000 статей. Линейный: листаем подряд — в худшем случае 100 000 сравнений. Двоичный: открываем середину, решаем «раньше или позже», отбрасываем половину — log₂ 100 000 ≈ 17 сравнений. Человек интуитивно ищет в словаре двоичным поиском — потому что словарь отсортирован. В этом вся цена сортировки: она делает возможным быстрый поиск.
Быстрая сортировка на массиве [5, 2, 8, 1, 9, 3], опорный — последний элемент.
- Опорный 3. Меньшие — влево, большие — вправо: [2, 1] 3 [5, 8, 9]. Опорный встал на своё окончательное место.
- Рекурсивно слева: [2, 1] → опорный 1 → [] 1 [2]. Справа: [5, 8, 9] → опорный 9 → [5, 8] 9 [].
- [5, 8] → опорный 8 → [5] 8. Готово: [1, 2, 3, 5, 8, 9].
Каждый уровень рекурсии просматривает все n элементов, уровней ~log n (массив делится примерно пополам) — отсюда O(n·log n) в среднем. Худший случай — уже отсортированный массив с крайним опорным: деление «1 и все остальные», O(n²); лечится случайным выбором опорного.
Сортировка слиянием тех же данных идёт с другого конца: режем пополам до одиночных элементов, затем сливаем отсортированные половины, всегда беря меньший из двух «верхних»: [5, 2, 8] и [1, 9, 3] → [2, 5, 8] и [1, 3, 9] → слияние: 1, 2, 3, 5, 8, 9. Гарантированные O(n·log n) в любом случае, плата — дополнительный массив на n элементов.
Рекурсия: n! = n·(n−1)!, 0! = 1. Вызов fact(4) разворачивается в стек: fact(4) → fact(3) → fact(2) → fact(1) → fact(0) = 1, затем результаты сворачиваются обратно: 1 → 1 → 2 → 6 → 24. Два обязательных элемента: базовый случай (иначе бесконечный спуск и переполнение стека) и сведение задачи к меньшей. Любая рекурсия механически переписывается в цикл со своим стеком — и наоборот; рекурсивная запись короче там, где структура задачи сама рекурсивна (деревья, быстрая сортировка, обход графа).
Линейные структуры данных
Алгоритм всегда работает над данными, и способ их организации определяет цену операций. Линейные структуры выстраивают элементы в последовательность «один за другим»:
- Массив — элементы одного типа в непрерывной области памяти. Доступ по индексу — O(1) (адрес = начало + i·размер), но вставка/удаление в середине — O(n) (сдвиг хвоста), а размер фиксирован (динамические массивы решают это перевыделением с запасом).
- Связный список — элементы-узлы «где угодно» в памяти, каждый хранит данные и ссылку на следующий (односвязный) или на следующего и предыдущего (двусвязный). Вставка и удаление при известном узле — O(1) (переставить ссылки), но доступ к i-му элементу — O(n): только последовательным проходом от головы.
- Стек — доступ с одного конца: LIFO (last in — first out), операции push/pop с вершины. Применения: вызовы подпрограмм и рекурсия, откат (Undo), разбор выражений.
- Очередь — добавление в хвост, извлечение из головы: FIFO (first in — first out). Применения: буферы ввода-вывода, планировщики ОС, обход в ширину. Дек — очередь с двумя открытыми концами.
| Операция | Массив | Связный список |
|---|---|---|
| Доступ по индексу | O(1) | O(n) |
| Поиск по значению | O(n) (O(log n), если отсортирован) | O(n) |
| Вставка/удаление в начале | O(n) | O(1) |
| Вставка/удаление у известного узла | O(n) | O(1) |
| Память | плотно, без накладных расходов | + ссылка (ссылки) в каждом узле |
Массив — полка с пронумерованными ячейками: к любой сразу дотянулся, но чтобы вставить книгу в середину, двигаешь все правые. Список — цепочка людей, где каждый держит за руку следующего: вставить нового человека — просто расцепить одну пару рук, но «кто седьмой?» — только пересчётом от начала.
Нелинейные структуры данных: деревья и графы
Классификация: двоичное дерево (не более двух потомков), двоичное дерево поиска (слева меньше, справа больше — поиск O(log n) при сбалансированности), сбалансированные (АВЛ, красно-чёрные — автоматически поддерживают высоту log n), B-деревья — широкие узлы под дисковые страницы (индексы БД — разобраны в разделе 3). Обходы двоичного дерева: прямой (корень–лево–право), симметричный (лево–корень–право — даёт отсортированный порядок в дереве поиска), обратный (лево–право–корень).
Представление в памяти: матрица смежности n×n (бит «есть ребро» — проверка ребра O(1), но память O(n²)) или списки смежности (у каждой вершины — список соседей: память O(n+m), обход соседей быстрый) — стандартный выбор для разреженных графов.
Алгоритмы обхода — систематическое посещение всех вершин:
- В глубину (DFS) — «идти, пока идётся»: от текущей вершины к любому непосещённому соседу, в тупике — откат назад. Реализация: рекурсия или явный стек. Применения: поиск компонент связности, топологическая сортировка, поиск циклов.
- В ширину (BFS) — «волнами»: сначала все соседи старта, потом соседи соседей. Реализация: очередь. Находит кратчайшие пути по числу рёбер; основа волнового алгоритма трассировки.
Информация, кодирование и сжатие
Подходы к измерению информации:
- Объёмный (алфавитный) — просто длина кода: бит, байт, килобайт… Не учитывает содержание.
- Вероятностный, формула Хартли: если возможны N равновероятных исходов, сообщение об одном из них несёт I = log₂N бит. Одно из 8 равновероятных — ровно 3 бита.
- Формула Шеннона — исходы неравновероятны: H = −Σ pᵢ·log₂pᵢ (энтропия — средняя информативность символа). Чем предсказуемее источник, тем меньше энтропия; у текста на русском ≈ 1,5–2 бита на букву вместо 5 «объёмных» — эта избыточность и есть резерв сжатия.
Хартли на пальцах. Загадано число от 1 до 64. Каждый вопрос «да/нет» даёт 1 бит, а нужно I = log₂64 = 6 бит — двоичный поиск угадывает за 6 вопросов, и быстрее в общем случае нельзя.
Сжатие без потерь — данные восстанавливаются в точности; работает за счёт устранения избыточности:
- RLE — серии повторов заменяются парой «символ × длина» (живое демо — в теме про графику ниже);
- Хаффман — частым символам короткие коды, редким — длинные (префиксное дерево по частотам);
- Словарные (LZ-семейство) — повторяющиеся цепочки заменяются ссылками на предыдущее вхождение (ZIP, PNG).
Сжатие с потерями — необратимо выбрасывается то, что человек почти не воспринимает: JPEG отбрасывает высокочастотные детали и тонкости цвета (глаз к ним нечувствителен), MP3/AAC — маскируемые звуки, видеокодеки — межкадровые повторы. Выигрыш в разы и десятки раз против процентов у сжатия без потерь; цена — качество, поэтому для текстов, программ и БД оно неприменимо.
Методы формализации алгоритмов
- словесное описание — по шагам на естественном языке;
- блок-схема (ГОСТ 19.701-90): овал — начало/конец, параллелограмм — ввод/вывод, прямоугольник — действие, ромб — ветвление;
- псевдокод — формализованный «полуязык» без привязки к синтаксису;
- запись на языке программирования — окончательная, исполняемая форма.
Базовые управляющие конструкции структурного программирования: следование, ветвление, цикл — их достаточно для записи любого алгоритма (теорема Бёма–Якопини).
Языки программирования и средства реализации
- По уровню: низкого уровня (машинные коды, ассемблер — близко к архитектуре) и высокого уровня (C, C++, Java, Python…).
- По способу исполнения: компилируемые (исходный текст переводится в машинный код целиком — C/C++), интерпретируемые (выполняются построчно — Python, JavaScript), гибридные (байт-код + виртуальная машина — Java, C#).
- По парадигме: процедурные (алгоритм как последовательность процедур), объектно-ориентированные (классы, инкапсуляция, наследование, полиморфизм), функциональные, логические (Prolog).
- Средства реализации: трансляторы (компиляторы/интерпретаторы), компоновщики, отладчики, интегрированные среды (IDE), библиотеки и системы контроля версий.
Трансляторы: виды и состав
Виды по функциональному назначению:
- компилятор — переводит программу на языке высокого уровня в машинные коды целиком, без выполнения; результат — эквивалентная объектная программа;
- интерпретатор — переводит каждую конструкцию алгоритмического языка с одновременным выполнением; медленнее, зато интерактивен и переносим;
- ассемблер — переводит программу с языка низкого уровня (мнемоник) в машинные коды;
- дополнительно: кросс-транслятор — код для другой машины (так собирают прошивки ПЛК и микроконтроллеров); JIT-компиляция — гибрид: байт-код компилируется в машинный код прямо во время выполнения (Java, C#, современные JS-движки).
Состав компилятора. Компилятор выполняет анализ исходной программы и синтез объектного кода; три основные части:
- Лексический анализатор — читает текст и выделяет лексемы (идентификаторы, числа, ключевые слова, знаки операций), отбрасывая пробелы и комментарии.
- Синтаксический анализатор — распознаёт предложения программы как конструкции формальной грамматики языка, строит дерево разбора / внутреннее представление. Грамматика описывает синтаксис (форму записи), но не семантику (смысл); семантические проверки — типы, описанность идентификаторов — выполняются на этом же этапе (семантический анализ).
- Генератор кода — по внутреннему представлению порождает объектный код; перед генерацией выполняется машинно-независимая оптимизация (удаление лишних вычислений, вынос инвариантов из циклов). Далее компоновщик собирает объектные модули и библиотеки в исполняемый файл.
Вопросы к собеседованию
Дайте определение алгоритма и перечислите его свойства.
Алгоритм — конечная последовательность точно определённых действий над данными, приводящая за конечное число шагов к результату. Свойства: дискретность, определённость (детерминированность), результативность/конечность, массовость, понятность для исполнителя.
Как оценивают эффективность алгоритма? Что означает запись O(n log n)?
По времени (число элементарных операций) и памяти как функциям размера входа n; сравнивают асимптотику через O-нотацию — верхнюю оценку скорости роста с точностью до константы. O(n log n) значит: время растёт пропорционально n·log n — так работают лучшие универсальные сортировки (слиянием, быстрая в среднем). Различают худший, средний и лучший случаи.
Сравните линейный и двоичный поиск; пузырьковую и быструю сортировку.
Линейный поиск — O(n), работает на любом массиве; двоичный — O(log n), но требует отсортированности. Пузырьковая сортировка — O(n²) сравнений; быстрая — O(n log n) в среднем (в худшем O(n²) при неудачных опорных элементах), сортировка слиянием — гарантированно O(n log n), но требует дополнительной памяти.
Какие существуют способы формализации (записи) алгоритма?
Словесное пошаговое описание; блок-схема по ГОСТ (овал — начало/конец, ромб — условие, прямоугольник — действие, параллелограмм — ввод/вывод); псевдокод; запись на языке программирования. Любой алгоритм выражается тремя базовыми конструкциями: следование, ветвление, цикл.
Классифицируйте языки программирования.
По уровню: низкого (ассемблер) и высокого уровня. По исполнению: компилируемые (C/C++), интерпретируемые (Python), гибридные с байт-кодом и виртуальной машиной (Java, C#). По парадигме: процедурные, объектно-ориентированные, функциональные, логические. Выбор определяется задачей: близость к железу, скорость разработки, переносимость.
Назовите этапы трансляции программы.
Лексический анализ (разбиение текста на токены), синтаксический анализ (построение дерева разбора по грамматике языка), семантический анализ (проверка типов, областей видимости), генерация промежуточного и машинного кода, оптимизация. Далее компоновщик собирает объектные модули и библиотеки в исполняемый файл.
Какие бывают линейные структуры данных и каковы операции над ними?
Массив — непрерывная память, доступ по индексу O(1), вставка/удаление в середине O(n). Связный список (одно- и двусвязный) — узлы со ссылками: вставка и удаление при известном узле O(1), доступ к i-му элементу O(n). Стек — LIFO, push/pop с вершины (рекурсия, откат). Очередь — FIFO, добавление в хвост, извлечение из головы (буферы, планировщики); дек открыт с обоих концов.
Что такое дерево и граф? Как граф представляют в памяти?
Дерево — иерархия с корнем, где между любыми узлами один путь (двоичные, деревья поиска, сбалансированные, B-деревья). Граф — множество вершин и рёбер, самая общая структура: ориентированные, взвешенные, связные. Представление: матрица смежности (проверка ребра O(1), память O(n²)) или списки смежности (память O(n+m) — стандарт для разреженных графов).
Сравните обходы графа в глубину и в ширину.
DFS идёт от вершины к непосещённому соседу, пока не упрётся, затем откатывается; реализуется рекурсией или стеком; применяется для компонент связности, топологической сортировки, поиска циклов. BFS раскрывает граф «волнами» через очередь: сначала все соседи старта, затем их соседи; находит кратчайшие пути по числу рёбер. Оба — O(n + m).
Какие виды трансляторов существуют?
По функциональному назначению: компилятор — переводит программу на языке высокого уровня в машинные коды целиком без выполнения; интерпретатор — переводит каждую конструкцию с одновременным выполнением; ассемблер — переводит с языка низкого уровня. Дополнительно: кросс-трансляторы (код для другой машины) и JIT-компиляция (байт-код компилируется во время выполнения).
Из каких частей состоит компилятор?
Компилятор выполняет анализ исходной программы и синтез объектного кода. Три основные части: лексический анализатор (текст → лексемы), синтаксический анализатор (распознавание конструкций формальной грамматики, построение внутреннего представления; здесь же семантические проверки) и генератор кода (внутреннее представление → объектный код, плюс оптимизация). По числу чтений программы компиляторы бывают одно-, двух- и трёхпроходные.
Как измеряют количество информации?
Объёмный подход — длина двоичного кода (биты, байты). Формула Хартли для N равновероятных исходов: I = log₂N бит. Формула Шеннона для неравновероятных: H = −Σpᵢ·log₂pᵢ — энтропия, средняя информативность символа; чем предсказуемее источник, тем она ниже. Избыточность реальных данных (энтропия меньше длины кода) — основа сжатия.
Чем сжатие без потерь отличается от сжатия с потерями?
Без потерь данные восстанавливаются в точности — устраняется только избыточность: RLE (серии повторов), Хаффман (частым символам — короткие коды), словарные LZ (ссылки на повторяющиеся цепочки); применяется к текстам, программам, БД. С потерями необратимо отбрасывается слабо воспринимаемое человеком (JPEG — высокие частоты, MP3 — маскируемые звуки): выигрыш в десятки раз, но только для мультимедиа.
Тема 2.2
Операционная среда ЭВМ. Системное программирование
Типы ОС, доступ к ресурсам, режимы использования ЭВМ, защита информации.
Назначение и типы операционных систем
Классификация ОС:
- по числу одновременных задач — однозадачные (MS-DOS) и многозадачные (с вытесняющей или кооперативной многозадачностью);
- по числу пользователей — однопользовательские и многопользовательские (с разграничением прав);
- по организации обслуживания — пакетной обработки (максимальная загрузка ЭВМ, задания очередью), разделения времени (каждому пользователю/задаче — квант процессора, интерактивность), реального времени (гарантированная реакция за заданный срок — управление объектами);
- сетевые (доступ к ресурсам сети) и распределённые (сеть машин выглядит как одна ЭВМ);
- по архитектуре ядра — монолитные и микроядерные.
Ключевые понятия: процесс — программа в ходе выполнения со своим адресным пространством; поток — единица планирования внутри процесса; виртуальная память — каждому процессу выделено собственное адресное пространство, страницы которого отображаются на физическую память или вытесняются на диск.
Процесс — квартира: свои стены (адресное пространство), чужие туда не войдут. Потоки — жильцы этой квартиры: работают каждый над своим, но холодильник (память процесса) общий — потому потокам легко обмениваться данными и легко же устроить беспорядок (гонки данных). Виртуальная память — каждому процессу выдают «личную» нумерацию комнат от нуля: процесс думает, что владеет всей памятью, а ОС тайком отображает его номера на реальные физические страницы, лишнее выгружая на диск.
Страничная адресация в числах. Страница 4 Кбайт (2¹²), виртуальный адрес 0x3A7F.
- Делим адрес: старшие биты — номер страницы 0x3 (три), младшие 12 бит — смещение 0xA7F.
- Смотрим в таблицу страниц процесса: запись №3 → физический кадр №17 (0x11).
- Физический адрес = кадр · 4К + смещение = 0x11A7F.
Если в записи №3 стоит бит «страница на диске» — происходит страничное прерывание (page fault): ОС подгружает страницу с диска, при нехватке места вытесняя другую (алгоритмы замещения — например, LRU: выгружается дольше всех не использовавшаяся). Так процессу «кажется», что памяти больше физической.
Как ОС делит один процессор между 50 процессами (вытесняющая многозадачность):
- планировщик выдаёт процессу квант времени (~10–100 мс);
- квант истёк → аппаратный таймер вызывает прерывание;
- ОС сохраняет контекст процесса (регистры, счётчик команд);
- выбирает следующий процесс по приоритету, восстанавливает его контекст;
- и так сотни раз в секунду — отсюда иллюзия одновременности.
В кооперативной многозадачности ОС ждала, пока программа сама отдаст управление — одна зависшая программа вешала всю систему.
Доступ к ресурсам и режимы использования ЭВМ
- Виды доступа пользователя к ресурсам: монопольный (вся машина — одному) и коллективный; локальный и удалённый (терминальный, сетевой).
- Режимы использования ЭВМ: пакетный — задания готовятся заранее и выполняются очередью без вмешательства; диалоговый (интерактивный) — работа в темпе пользователя, основан на разделении времени; режим реального времени — обработка событий в темпе управляемого процесса.
- Аппаратная основа защиты ОС: два режима процессора — привилегированный (ядра) и пользовательский; обращение к ядру только через системные вызовы.
Алгоритмы планирования процессора — три процесса пришли почти одновременно, длительности: A = 24 мс, B = 3 мс, C = 3 мс.
| Алгоритм | Порядок выполнения | Ожидание A, B, C | Среднее |
|---|---|---|---|
| FCFS (в порядке прихода) | A(0–24), B(24–27), C(27–30) | 0; 24; 27 | 17 мс |
| SJF (кратчайший первым) | B(0–3), C(3–6), A(6–30) | 6; 0; 3 | 3 мс |
| RR, квант 4 мс | A(0–4), B(4–7), C(7–10), A(10–…) | 6; 4; 7 | 5,7 мс |
FCFS страдает «эффектом конвоя»: короткие задачи ждут длинную. SJF оптимален по среднему ожиданию, но требует знать длительности и может бесконечно откладывать длинную задачу (голодание). Round Robin ничего не знает заранее и даёт всем отзывчивость — цена: переключения контекста. Реальные ОС используют многоуровневые очереди с приоритетами поверх RR.
Синхронизация: семафор и взаимоблокировка. Два потока одновременно выполняют счёт = счёт + 1 при счёте 100: оба читают 100, оба пишут 101 — одно увеличение потеряно (гонка данных). Решение — семафор/мьютекс: перед критической секцией P(S) (занять), после — V(S) (освободить); второй поток ждёт, итог корректный — 102.
Взаимоблокировка (deadlock): поток 1 захватил ресурс А и ждёт Б, поток 2 захватил Б и ждёт А — оба стоят вечно. Четыре условия возникновения: взаимное исключение, удержание с ожиданием, отсутствие принудительного отъёма, циклическое ожидание. Классическая профилактика — разрушить цикл: захватывать ресурсы всегда в одном и том же порядке.
Защита информации
Факторы, повышающие уязвимость информации: рост объёмов и концентрация данных в ЭВМ; расширение круга пользователей, имеющих доступ; удалённый и сетевой доступ; усложнение ПО (ошибки и уязвимости); человеческий фактор.
Основные каналы потери (утечки) информации:
- несанкционированный доступ к данным и носителям (в т.ч. хищение носителей);
- перехват в каналах связи и побочные электромагнитные излучения;
- вредоносные программы (вирусы, трояны) и программные закладки;
- ошибки и умышленные действия персонала, сбои аппаратуры и ПО.
Источники угроз классифицируют по происхождению и умыслу: внешние (злоумышленники, конкуренты, вредоносное ПО из сети) и внутренние (персонал — по статистике до половины инцидентов); случайные (ошибки пользователей, сбои техники, стихийные события) и преднамеренные (атаки). Риск — комбинация вероятности реализации угрозы и величины ущерба: защиту строят от угроз с наибольшим риском, а не «от всего сразу».
Основные формы атак на информацию:
- перехват данных в каналах связи и «человек посередине» (MitM) — злоумышленник незаметно встраивается между сторонами;
- несанкционированный доступ: подбор и кража паролей, использование уязвимостей ПО, повышение привилегий;
- вредоносное ПО: вирусы, черви (распространяются сами по сети), трояны, шифровальщики-вымогатели;
- социальная инженерия и фишинг — атака на человека, а не на технику: поддельные письма и сайты, выманивающие пароли;
- отказ в обслуживании (DoS/DDoS) — лавина запросов, исчерпывающая ресурсы сервера;
- атаки на веб-приложения: SQL-инъекции (подмена запроса к БД через поле ввода), XSS (внедрение скрипта в чужие страницы).
Подходы к защите — три эшелона, работающие вместе: правовые (законодательство о защите информации и персональных данных, ответственность), организационные (политика безопасности, регламенты доступа, обучение персонала, физическая охрана) и программно-технические (всё перечисленное ниже).
Принципы обеспечения безопасности — комплексность и эшелонированность:
- идентификация и аутентификация пользователей (пароли, токены, биометрия);
- разграничение доступа — дискреционное (владелец назначает права: списки ACL) и мандатное (метки секретности); принцип минимума привилегий;
- криптографическая защита — симметричное (один секретный ключ, быстрое — AES, ГОСТ) и асимметричное шифрование (пара открытый/закрытый ключ — RSA; электронная подпись);
- аудит — протоколирование событий безопасности;
- резервное копирование и отказоустойчивость (сохранность и целостность);
- антивирусная защита, межсетевые экраны, физическая защита.
Идентификация и аутентификация
Три разных шага допуска в систему, которые важно не путать:
- Идентификация — субъект называет себя: логин, номер карты, имя сертификата.
- Аутентификация — субъект доказывает, что он тот, кем назвался.
- Авторизация — система решает, что ему разрешено (разграничение доступа по правам).
Факторы аутентификации — чем можно доказывать:
- знание — пароль, PIN, кодовая фраза; самое дешёвое и самое уязвимое средство (подбор, фишинг, повторное использование);
- владение — токен, смарт-карта, USB-ключ, телефон с одноразовыми кодами;
- биометрия — отпечаток пальца, лицо, радужка, голос; удобно, но «пароль» нельзя сменить при компрометации.
Двухфакторная аутентификация (2FA) комбинирует факторы разных типов (пароль + код на телефон): кража одного фактора не даёт доступа. В корпоративных системах применяются централизованные службы аутентификации и каталогов (Kerberos, LDAP/Active Directory, RADIUS для сетевого доступа).
Как хранить пароли на сервере. Никогда — открытым текстом: утечка БД отдаст все учётные записи. Хранят хеш пароля с солью (случайной добавкой): при входе хешируют введённое и сравнивают. Хеш необратим — по нему пароль не восстановить, а соль не даёт атаковать по заранее посчитанным таблицам и скрывает совпадающие пароли разных пользователей. Именно поэтому «восстановить пароль» невозможно — только сбросить.
Криптография и криптосистемы
Виды криптосистем:
- Симметричные — один секретный ключ на шифрование и расшифровку: блочные (AES, ГОСТ Р 34.12 «Кузнечик» — шифруют блоками по 128 бит) и поточные (бит за битом). Быстрые, но требуют защищённой передачи ключа каждой паре собеседников.
- Асимметричные (с открытым ключом) — пара математически связанных ключей: открытый публикуется, закрытый хранится у владельца (RSA — на сложности факторизации больших чисел, эллиптические кривые). Решают проблему обмена ключами, но в сотни раз медленнее.
- Гибридные — асимметрично согласуют сеансовый ключ, данные шифруют быстрым симметричным алгоритмом; так устроен HTTPS/TLS.
- Хеш-функции (SHA-256, ГОСТ «Стрибог») — необратимая «свёртка» любого сообщения в короткий отпечаток; изменение одного бита меняет хеш до неузнаваемости — контроль целостности и основа ЭЦП.
Симметричное — идея на игрушечном шифре Цезаря (сдвиг букв на k = 3):
- сила: быстро (AES шифрует гигабайты в секунду);
- слабость: как передать ключ собеседнику по открытому каналу?
Асимметричное решает проблему передачи ключа:
- открытый ключ публикуется всем — «вот навесной замок, защёлкните им посылку»;
- закрытый хранится у владельца — «ключ от замка только у меня»;
- зашифровать может любой, расшифровать — только владелец.
На практике комбинируют: асимметрично передают маленький сеансовый ключ, поток шифруют быстрым AES — так работает HTTPS.
Электронная подпись — те же ключи наоборот: автор подписывает хеш документа закрытым ключом, любой проверяет открытым — подтверждаются авторство и неизменность.
Каждая буква сдвигается по алфавиту на k. Ключ один — и на шифрование, и на расшифровку (симметричная схема). Взлом тривиален: ключей всего 33 — переберите слайдером; на длинном тексте помогает и частотный анализ (буква «О» — самая частая в русском). Современный AES отличается не идеей «перемешать», а размером ключа: 2¹²⁸ вариантов не переберёшь.
Современные ОС вычислительных комплексов: семейство Windows (NT-ядро), UNIX-подобные — Linux (серверы, суперкомпьютеры, встраиваемые системы), macOS; отечественные на базе Linux (Astra Linux, ALT); для мобильных — Android, iOS; для реального времени — QNX, VxWorks.
Вопросы к собеседованию
Что такое операционная система и каковы её функции?
Комплекс программ, управляющий ресурсами ЭВМ и организующий выполнение прикладных программ. Функции: управление процессами (создание, планирование процессорного времени), управление памятью (в т.ч. виртуальной), управление вводом-выводом и файловой системой, интерфейс пользователя, защита и разграничение доступа.
Классифицируйте типы операционных систем.
Одно-/многозадачные; одно-/многопользовательские; по обслуживанию — пакетной обработки (максимум загрузки, без диалога), разделения времени (кванты процессора, интерактивность), реального времени (гарантированный срок реакции); сетевые и распределённые; по ядру — монолитные и микроядерные.
Какие существуют режимы использования ЭВМ?
Пакетный — задания подготавливаются заранее и проходят очередью без участия пользователя (эффективная загрузка машины); диалоговый (интерактивный) — работа в темпе пользователя на основе разделения времени; режим реального времени — реакция на события управляемого объекта за гарантированное время. Доступ к ресурсам может быть монопольным или коллективным, локальным или удалённым.
Чем процесс отличается от потока? Что такое виртуальная память?
Процесс — выполняющаяся программа с собственным адресным пространством и ресурсами; поток — единица планирования внутри процесса, потоки процесса разделяют его память. Виртуальная память даёт каждому процессу своё логическое адресное пространство: страницы отображаются на физическую память, неиспользуемые вытесняются на диск — это изолирует процессы и позволяет выполнять программы больше физической памяти.
Какие факторы повышают уязвимость информации в компьютерных системах?
Концентрация больших объёмов данных в одном месте; расширение круга лиц с доступом; удалённый и сетевой доступ; усложнение программного обеспечения и, как следствие, рост числа ошибок и уязвимостей; человеческий фактор (небрежность, умысел персонала).
Назовите основные каналы потери информации.
Несанкционированный доступ к системе и хищение носителей; перехват данных в каналах связи и побочные электромагнитные излучения; вредоносные программы и закладки; ошибки и злоупотребления персонала; сбои и отказы аппаратуры и ПО (потеря целостности и доступности).
Перечислите принципы (методы) обеспечения безопасности компьютерных систем.
Комплексная, эшелонированная защита: идентификация и аутентификация; разграничение доступа (дискреционное — ACL, мандатное — метки секретности; минимум привилегий); криптография (симметричная — AES/ГОСТ, асимметричная — RSA, электронная подпись); аудит событий; резервное копирование и отказоустойчивость; антивирусы и межсетевые экраны; организационные и физические меры.
Чем симметричное шифрование отличается от асимметричного?
Симметричное использует один секретный ключ для шифрования и расшифровки — быстрое, но требует защищённой передачи ключа (AES, ГОСТ). Асимметричное — пара ключей: открытым шифруют (или проверяют подпись), закрытым расшифровывают (или подписывают) — решает задачу распределения ключей, но медленнее; на практике комбинируют: асимметрично передают сеансовый симметричный ключ.
Назовите источники, риски и формы атак на информацию.
Источники: внешние (злоумышленники, вредоносное ПО) и внутренние (персонал); случайные (ошибки, сбои) и преднамеренные. Риск — вероятность угрозы × ущерб; защита строится от наибольших рисков. Формы атак: перехват и MitM, несанкционированный доступ (подбор паролей, уязвимости), вредоносное ПО (вирусы, черви, трояны, шифровальщики), социальная инженерия и фишинг, DoS/DDoS, атаки на веб (SQL-инъекции, XSS). Подходы к защите: правовые, организационные, программно-технические.
Чем идентификация отличается от аутентификации и авторизации?
Идентификация — субъект называет себя (логин). Аутентификация — доказывает подлинность: фактором знания (пароль), владения (токен, телефон) или биометрией; 2FA комбинирует разные факторы. Авторизация — определение прав уже опознанного субъекта (что ему можно). Пароли на сервере хранятся только в виде хеша с солью.
Что такое криптосистема? Какие виды криптосистем существуют?
Криптосистема — совокупность алгоритмов шифрования/расшифрования, множества ключей и правил их применения; по принципу Керкгоффса секретен ключ, а не алгоритм. Виды: симметричные (один секретный ключ — блочные AES/ГОСТ и поточные), асимметричные (пара открытый/закрытый — RSA, эллиптические кривые), гибридные (асимметричный обмен сеансовым ключом + симметричный поток — HTTPS); плюс хеш-функции для целостности и электронная подпись для подлинности.
Тема 2.3
Геометрическое моделирование и машинная графика
Растровые алгоритмы, преобразования и проекции, удаление скрытых поверхностей, освещение, кривые Безье, форматы — по методичкам Васильева.
Базовые растровые алгоритмы
- Алгоритм Брезенхема для отрезка — строит растровое приближение прямой только целочисленными операциями: на каждом шаге по ведущей оси накапливается ошибка, знак которой решает, смещаться ли по второй оси.
- Алгоритм Брезенхема для окружности — считается один октант (остальное — симметрия), выбор следующего пиксела по знаку ошибки.
- Заполнение области: затравочное (от внутренней точки, 4- или 8-связность, через стек) и построчное сканирование с чётно-нечётным правилом пересечения границ.
- Окна и отсечение — алгоритм Коэна–Сазерленда: концам отрезка присваиваются 4-битные коды положения относительно окна, что позволяет быстро принять/отбросить отрезок или отсечь по границе.
- Текстурирование — наложение растрового изображения на поверхность через отображение текстурных координат (u, v) на пикселы.
Текстуры подробнее
Каждой вершине поверхности приписываются текстурные координаты (u, v) ∈ [0;1]² — «широта и долгота» на картинке-текстуре; для точек внутри треугольника они интерполируются. Проблема в том, что пиксел экрана почти никогда не попадает точно в тексель (пиксел текстуры) — нужен выбор:
- Ближайший сосед — берём один ближайший тексель: быстро, но при увеличении картинка распадается на квадраты, при движении — «кипит»;
- Билинейная фильтрация — взвешенное среднее четырёх соседних текселей: гладко, ценой четырёх выборок;
- Мип-уровни (mip-mapping) — заранее построенная пирамида уменьшенных копий текстуры; для далёких поверхностей берётся мелкая копия — иначе множество текселей «толпились» бы в одном пикселе и мерцали (алиасинг);
- при перспективной проекции координаты (u, v) нельзя интерполировать линейно по экрану — нужна перспективная коррекция (интерполируют u/w, v/w, 1/w), иначе текстура «плывёт» по треугольнику.
ЦДА (DDA) — простейший алгоритм растеризации того же отрезка (0;0) → (5;2): идём по ведущей оси x с шагом 1, а y наращиваем на дробный шаг dy/dx = 0,4 и округляем:
Просто и понятно, но на каждом шаге — вещественное сложение и округление, а накопление ошибок округления на длинных отрезках заметно. Брезенхем (ниже) получает те же пикселы целочисленно — потому и стал стандартом.
Брезенхем для отрезка (0;0) → (5;2): dx = 5, dy = 2, ошибка e = 2dy − dx = −1. На каждом шаге x увеличивается на 1; если e > 0 — поднимаемся по y и уменьшаем e на 2dx; всегда прибавляем 2dy:
| шаг | e до | e > 0 → y+1? | пиксел |
|---|---|---|---|
| 1 | −1 | нет | (1; 0) |
| 2 | +3 | да, e −= 10 | (2; 1) |
| 3 | −3 | нет | (3; 1) |
| 4 | +1 | да, e −= 10 | (4; 2) |
| 5 | −5 | нет | (5; 2) |
Ни одного умножения и деления — только сложения целых чисел. Именно такие циклы графический контроллер гоняет миллиардами в секунду.
Сжатие графических данных и форматы
- RLE — кодирование длин серий одинаковых байтов (BMP, PCX);
- LZW — словарное сжатие повторяющихся цепочек (GIF, TIFF);
- Хаффман — частым символам короткие коды;
- JPEG — сжатие с потерями: переход в YCbCr, разбиение на блоки 8×8, дискретное косинусное преобразование, квантование высокочастотных коэффициентов, энтропийное кодирование.
RLE на пальцах — кодируем длины серий:
- скриншоты и чертежи с одноцветными полями RLE ужимает в разы;
- на фотографии соседние пикселы разные — серии длиной 1, файл может даже вырасти.
Хаффман: частым символам — короткие битовые коды, редким — длинные. «Е» в тексте получает 3 бита вместо 8, «Ф» — все 10; в среднем текст ужимается почти вдвое.
Почему JPEG «портит», но этого не видно: глаз плохо различает мелкие перепады яркости и ещё хуже — мелкие перепады цвета. ДКП раскладывает блок 8×8 на «крупный фон + мелкая рябь»; квантование огрубляет и обнуляет коэффициенты «ряби», которую глаз всё равно не видит, — их и не храним. Чем выше степень сжатия, тем больше ряби выброшено; артефакты-«квадратики» — это и есть границы блоков 8×8, где выброшено слишком много.
| Формат | Сжатие | Цвет | Особенности |
|---|---|---|---|
| BMP | без сжатия / RLE | до 24 бит | простой растровый, большой размер |
| PNG | без потерь (Deflate) | до 48 бит + альфа | прозрачность, схемы и скриншоты |
| GIF | LZW без потерь | палитра ≤ 256 | анимация, прозрачный цвет |
| JPEG | с потерями (DCT) | 24 бит | фотографии; артефакты на резких границах |
Геометрические 2D- и 3D-преобразования
Аффинные преобразования (перенос, поворот, масштабирование, отражение, сдвиг) записываются матрицами в однородных координатах (x, y, 1) — 3×3 для 2D и 4×4 для 3D. Однородные координаты нужны, чтобы перенос тоже стал умножением на матрицу, и сложное преобразование получалось перемножением матриц. Порядок важен: матрицы не коммутируют — поворот вокруг точки = перенос в начало · поворот · перенос обратно.
Повернём точку (1; 0) на 90° против часовой стрелки:
Почему порядок матриц важен — одна и та же точка (1; 0):
- повернуть, потом сдвинуть на (2; 0): (1;0) → (0;1) → (2;1);
- сдвинуть, потом повернуть: (1;0) → (3;0) → (0;3) — другая точка!
Итоговая матрица собирается справа налево: M = T·R значит «сначала R, потом T».
Зачем городить однородные координаты с «лишней» единицей? Без неё поворот — умножение на матрицу, а перенос — сложение с вектором, и цепочку из десяти преобразований пришлось бы таскать как десять операций. С единицей всё, включая перенос, — умножение матриц: десять преобразований схлопываются в одну матрицу 3×3, и каждая точка модели обрабатывается одним умножением. Для сцены из миллиона вершин это и есть разница между «летает» и «тормозит».
Проекции и способы задания 3D-объектов
- Параллельные проекции: ортографические (виды спереди/сверху/сбоку), аксонометрические (изометрия — равные углы осей), косоугольные; сохраняют параллельность, применяются в чертежах.
- Центральная (перспективная) проекция — лучи из центра проецирования; удалённые предметы меньше, есть точки схода; реалистичное восприятие.
- Методы задания 3D-объектов: каркасные (вершины и рёбра); поверхностные — полигональные сетки и параметрические поверхности (Безье, B-сплайны); твердотельные — конструктивная блочная геометрия CSG (булевы операции над примитивами), граничное представление B-rep; воксельные.
Удаление скрытых поверхностей
- Z-буфер — для каждого пиксела хранится глубина ближайшей закрашенной точки; новый фрагмент рисуется, только если он ближе. Прост, аппаратно реализован в GPU; расход памяти на буфер глубины.
- Метод приоритетов (художника) — грани сортируются по глубине и рисуются от дальних к ближним; проблемы при пересечениях и циклическом перекрытии.
- Метод Варнока — рекурсивное разбиение экрана: если в окне ситуация «простая», оно закрашивается, иначе делится на 4 подокна.
- BSP-дерево — сцена рекурсивно делится плоскостями граней на полупространства; порядок вывода для любой камеры получается обходом дерева (сортировка предвычислена).
Z-буфер в числах. Экран 2×2, буфер глубины заполнен ∞.
- Рисуем синий треугольник: пикселы (0;0) и (1;0), глубины z = 5 и 6. Оба ближе ∞ → записаны. Буфер: [5, 6, ∞, ∞].
- Рисуем красный: пиксел (0;0) с z = 3 — ближе, чем 5 → перекрашен в красный, буфер 3.
- Его же пиксел (1;0) с z = 8 — дальше, чем 6 → отброшен, остаётся синий.
Порядок рисования не важен — буфер сам разрешает видимость в каждом пикселе. За это z-буфер и любят GPU: никакой сортировки сцены.
Тени: теневые карты (сцена «глазами» источника, сравнение глубин), теневые объёмы, а в трассировке лучей — теневые лучи к источнику.
Модели освещения и закраска
Локальная модель освещения (Фонга) складывает три компоненты:
- фоновая (ambient) — рассеянный свет среды;
- диффузная (Ламберта) — пропорциональна косинусу угла между нормалью N и направлением на источник L, не зависит от наблюдателя;
- зеркальная (Фонга) — блик, зависит от угла между отражённым лучом R и направлением на наблюдателя V; показатель n задаёт «резкость» блика.
Закраска Гуро: интенсивность вычисляется в вершинах и линейно интерполируется по грани — быстро, но блики «теряются» внутри граней. Закраска Фонга: по грани интерполируется нормаль, освещение считается в каждом пикселе — качественные блики, дороже.
Числа к модели освещения (Iл = 1, kd = 0,7):
- грань под 60° к источнику: диффузная = 0,7·cos 60° = 0,35 — вдвое темнее прямого освещения;
- блик при n = 30: отклонение взгляда от зеркального луча на 15° гасит блик до cos³⁰15° ≈ 0,36;
- тот же угол при n = 5: cos⁵15° ≈ 0,84 — блик почти не потускнел.
Большой n — маленький резкий блик (полированный металл); малый n — широкий тусклый (пластик).
Обратная трассировка лучей (реалистическая графика): из глаза через каждый пиксел пускается луч; в точке пересечения с ближайшим объектом считается освещение, рекурсивно порождаются отражённый и преломлённый лучи, теневые лучи к источникам. Даёт зеркала, преломления, точные тени; вычислительно дорога.
Построение теней
Тень — то, чего «не видит» источник света: точка затенена, если между ней и источником есть препятствие. Без теней объекты «висят в воздухе» — тень привязывает их к опоре и передаёт взаимное расположение. Три классических алгоритма:
- Проективные (плоские) тени — каждая вершина объекта проецируется лучом из источника на плоскость пола/стены; спроецированный силуэт закрашивается тёмным. Дёшево, но тень ложится только на плоскость и не самозатеняет.
- Карта теней (shadow map) — сцена сначала «рисуется» из положения источника, но сохраняются только глубины (Z-буфер источника). При основном рендеринге каждая точка пересчитывается в координаты источника: если она дальше, чем записано в карте, — между ней и светом что-то есть, точка в тени. Два прохода, работает с любой геометрией — стандарт в играх и на GPU.
- Теневые объёмы (shadow volumes) — от контура объекта в направлении от источника вытягивается объёмный «столб тени»; точка затенена, если находится внутри такого объёма (подсчёт пересечений через трафаретный буфер). Точные резкие границы, но дорого при сложных контурах.
В трассировке лучей тени получаются «бесплатно» — теневым лучом к источнику; мягкие полутени дают протяжённые источники (частично заслонённые).
Графические библиотеки
Прикладная программа не работает с видеокартой напрямую — она вызывает графическую библиотеку (API), а драйвер превращает вызовы в команды GPU. Уровни:
- OpenGL — открытый кроссплатформенный стандарт 3D-графики (по методичке Васильева): конвейер «вершины → преобразования и освещение → растеризация → фрагменты → буфер кадра», состояние-машина, начиная с современных версий — программируемые шейдеры (вершинные и фрагментные программы на GLSL). OpenGL ES — версия для мобильных, WebGL — для браузера.
- Direct3D (DirectX) — API Microsoft для Windows и Xbox; Vulkan и Metal — современные низкоуровневые API с явным управлением памятью и многопоточностью — меньше накладных расходов драйвера.
- Высокоуровневые надстройки: движки и сцены (Unity, Unreal, OpenSceneGraph), 2D-канвасы (Canvas API, Qt Painter), построение графиков (matplotlib, gnuplot) — используют нижние API, скрывая конвейер.
Иерархия как в сетях: прикладная библиотека — «прикладной уровень», OpenGL/Vulkan — «транспорт», драйвер и GPU — «физика». Чем ниже спускаешься, тем больше контроля и тем больше ручной работы: matplotlib строит график одной строкой, Vulkan требует сотни строк на первый треугольник.
Параметрические кривые и поверхности
Кривая задаётся параметрически: P(t) = (x(t), y(t), z(t)), t ∈ [0, 1]; для кубических кривых P(t) — полином 3-й степени.
- Форма Эрмита — по двум концевым точкам и двум касательным векторам в них.
- Форма Безье — по четырём контрольным точкам: кривая проходит через P₀ и P₃, касательные в концах направлены на P₁ и P₂; кривая лежит в выпуклой оболочке контрольных точек. Базис — полиномы Бернштейна.
- B-сплайны — гладкая составная кривая по многим контрольным точкам: перемещение точки влияет только локально; непрерывность C² в узлах; кривая в общем случае не проходит через контрольные точки.
- Поверхности Безье/Эрмита/B-сплайновые — тензорное произведение кривых по двум параметрам (u, v) с сеткой контрольных точек (16 для бикубического куска Безье).
Точка кривой Безье при t = 0,5 для P₀(0;0), P₁(1;3), P₂(3;3), P₃(4;0). Веса Бернштейна при t = 0,5:
Сумма весов равна 1 при любом t: точка кривой — «среднее взвешенное» контрольных точек, поэтому кривая не выскочит из их выпуклой оболочки. Шрифты TrueType, контуры CorelDraw и траектории станков с ЧПУ — всё кривые Безье.
Алгоритм де Кастельжо — та же точка B(0,5), но без полиномов, одними серединами отрезков:
- Середины сторон ломаной P₀P₁P₂P₃: (0,5; 1,5), (2; 3), (3,5; 1,5).
- Середины полученных отрезков: (1,25; 2,25), (2,75; 2,25).
- Середина последнего отрезка: (2; 2,25) — совпало с расчётом по Бернштейну ✓.
Для произвольного t точки делят отрезки в отношении t : (1−t). Алгоритм численно устойчивее прямого вычисления полиномов и заодно разрезает кривую на две кривые Безье (левые/правые промежуточные точки) — так строят кривую рекурсивным дроблением до пиксельной точности.
Контрольные точки — «магниты»: кривая тянется к P₁ и P₂, не обязана их касаться, и вся конструкция ведёт себя предсказуемо, как гибкая линейка с двумя грузиками. Дизайнер двигает точку — кривая плавно следует. B-сплайн — цепочка таких кусков, сшитых гладко: подвинул точку — «дышит» только соседний кусок, остальная кривая стоит на месте (локальность), поэтому им моделируют кузова и корпусы.
Вопросы к собеседованию
Что такое текстурные координаты и зачем нужна фильтрация текстур?
Текстурные координаты (u, v) ∈ [0;1]² приписываются вершинам и интерполируются по поверхности — они задают, какая точка картинки-текстуры попадает в данный пиксел. Пиксел почти никогда не совпадает с текселем, поэтому нужна фильтрация: ближайший сосед (быстро, «квадраты»), билинейная (среднее четырёх текселей — гладко). При уменьшении используют мип-уровни — пирамиду уменьшенных копий против алиасинга; при перспективе координаты интерполируют с перспективной коррекцией.
В чём идея алгоритма Брезенхема и почему он эффективен?
Отрезок (или окружность) растеризуется только целочисленной арифметикой: на каждом шаге по ведущей оси накапливается величина ошибки — отклонения растровой линии от идеальной, и по её знаку решается, смещаться ли по второй оси. Нет умножений, делений и вещественных чисел, поэтому алгоритм быстр и реализуется аппаратно. Для окружности считается один октант, остальные — симметрией.
Какие методы заполнения области вы знаете?
Затравочное заполнение: из внутренней точки-затравки соседние пикселы (4- или 8-связные) закрашиваются рекурсивно/через стек до границы. Построчное сканирование: для каждой строки находятся пересечения с границей многоугольника, закрашиваются интервалы между парами пересечений (чётно-нечётное правило). Для отсечения по окну применяют алгоритм Коэна–Сазерленда с 4-битными кодами концов отрезка.
Зачем в графике однородные координаты?
В обычных координатах перенос — сложение, а не умножение, и его нельзя объединить с поворотом/масштабом в одну матрицу. В однородных координатах (x, y, 1) все аффинные преобразования — умножение на матрицу 3×3 (в 3D — 4×4), поэтому цепочка преобразований сворачивается в одну матрицу-произведение. Порядок множителей важен: матрицы не коммутируют. Также однородная координата w реализует перспективное деление.
Какие бывают проекции трёхмерных объектов?
Параллельные — проецирующие лучи параллельны: ортографические (виды), аксонометрические (изометрия, диметрия), косоугольные; сохраняют параллельность и пропорции вдоль осей — чертежи. Центральные (перспективные) — лучи из центра проецирования, есть точки схода, дальние объекты меньше — реалистичная визуализация.
Назовите методы задания 3D-объектов.
Каркасное (вершины + рёбра); поверхностное — полигональные сетки и параметрические поверхности (Безье, B-сплайны, Кунса); твердотельное — CSG (булевы операции объединения/пересечения/разности над примитивами) и граничное представление B-rep; воксельное (объёмные элементы). Выбор зависит от задачи: визуализация, САПР, медицина.
Опишите алгоритм z-буфера. Его достоинства и недостатки?
Параллельно буферу кадра ведётся буфер глубины: для каждого пиксела — z ближайшей уже нарисованной точки. Каждый фрагмент каждой грани сравнивается по глубине: если ближе — записывается цвет и обновляется z. Достоинства: простота, любой порядок вывода граней, аппаратная реализация в GPU. Недостатки: память под буфер, перерисовка невидимых фрагментов, проблемы точности (z-fighting).
Сравните метод приоритетов, метод Варнока и BSP-дерево.
Метод художника: грани сортируются по глубине и рисуются от дальних к ближним; сложности при пересечении и циклическом перекрытии граней. Варнок: экран рекурсивно делится на 4 подокна, пока ситуация в окне не станет простой для закраски — алгоритм пространства изображения. BSP-дерево: сцена заранее разбивается плоскостями на полупространства; обход дерева даёт правильный порядок вывода для любого положения камеры — сортировка предвычислена, выгодно для статичных сцен.
Из каких компонент складывается локальная модель освещения?
Фоновая (ambient) — постоянный рассеянный свет; диффузная по Ламберту — I ~ cos угла между нормалью и направлением на источник, не зависит от наблюдателя; зеркальная по Фонгу — блик, I ~ cosⁿ угла между отражённым лучом и направлением на наблюдателя, n определяет резкость блика. Итог — сумма компонент по всем источникам.
Чем закраска Гуро отличается от закраски Фонга?
Гуро: освещённость считается в вершинах грани и линейно интерполируется по её площади — быстро, но зеркальные блики внутри грани пропадают или искажаются. Фонг: по грани интерполируется вектор нормали, и модель освещения вычисляется в каждом пикселе — корректные блики, но существенно дороже. Не путать закраску Фонга с моделью освещения Фонга.
Как работает обратная трассировка лучей?
Из положения глаза через каждый пиксел экрана пускается первичный луч; находится ближайшее пересечение со сценой; в точке считается локальное освещение, к источникам пускаются теневые лучи, и рекурсивно порождаются отражённый и преломлённый лучи (до заданной глубины). Метод «обратный», потому что лучи идут от глаза к источникам. Даёт зеркальные отражения, преломления и точные тени ценой больших вычислений.
Сравните кривые Эрмита, Безье и B-сплайны.
Эрмита — задаётся концевыми точками и касательными в них: удобно для стыковки, но касательные ненаглядны. Безье — четырьмя контрольными точками: проходит через крайние, касательные направлены на внутренние, лежит в выпуклой оболочке; изменение одной точки влияет на всю кривую. B-сплайн — составная кривая по многим точкам с локальным влиянием каждой и гладкостью C² в стыках; в общем случае не проходит через контрольные точки. Поверхности строятся тензорным произведением по (u, v).
Сравните форматы BMP, PNG, GIF и JPEG. Как устроено сжатие в JPEG?
BMP — несжатый растр (или RLE), большие файлы. PNG — сжатие без потерь (Deflate), полноцвет + альфа-канал: схемы, скриншоты. GIF — палитра до 256 цветов, LZW без потерь, анимация. JPEG — с потерями: RGB→YCbCr, прореживание цветовых каналов, блоки 8×8, дискретное косинусное преобразование, квантование (обнуление высоких частот — здесь и потери), зигзаг + Хаффман. Для фото JPEG даёт максимальное сжатие; на чертежах — артефакты у резких границ.
Приведите пример алгоритма построения теней.
Карта теней (shadow map): сцена рендерится из положения источника света с сохранением только глубин; затем при основном рендеринге каждая видимая точка переводится в координаты источника и её расстояние сравнивается с записанным в карте — если точка дальше, между ней и светом есть препятствие, значит она в тени. Альтернативы: проективные тени (проекция силуэта на плоскость лучами из источника) и теневые объёмы (точка в тени, если внутри «столба», вытянутого от контура объекта); в трассировке лучей — теневой луч к источнику.
Какие графические библиотеки вы знаете?
Низкоуровневые API: OpenGL — открытый кроссплатформенный стандарт (конвейер, шейдеры GLSL; версии OpenGL ES для мобильных, WebGL для браузера), Direct3D — Windows/Xbox, современные Vulkan и Metal с явным управлением ресурсами. Над ними — движки и высокоуровневые средства: Unity/Unreal, Canvas API, Qt, matplotlib для графиков. Приложение вызывает API, драйвер превращает вызовы в команды GPU.