Тема 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 сравнений. Человек интуитивно ищет в словаре двоичным поиском — потому что словарь отсортирован. В этом вся цена сортировки: она делает возможным быстрый поиск.
Помимо времени оценивают пространственную (ёмкостную) сложность — дополнительную память: сортировке слиянием нужен вспомогательный массив O(n), быстрой — O(log n) на стек рекурсии, пузырьковой — O(1). Время и память часто разменивают друг на друга: предвычисленная таблица ускоряет счёт ценой памяти, и наоборот.
Пределы эффективности. Для сортировки сравнениями доказана нижняя граница Ω(n log n) — быстрее нельзя ни на каком компьютере. Задачи делят на классы: P — решаемые за полиномиальное время; NP — те, у которых готовое решение быстро проверяется; NP-полные (коммивояжёр, рюкзак, выполнимость логических формул) — «самые трудные» в NP: для них известны только переборные по сути алгоритмы, на практике используют приближённые и эвристические методы. Вопрос «P = NP?» — главная открытая проблема информатики.
Быстрая сортировка на массиве [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(n log n).
- Жадные алгоритмы — на каждом шаге выбирается локально лучший вариант без пересмотра решений: алгоритм Дейкстры (кратчайшие пути во взвешенном графе), построение кода Хаффмана, задачи выбора заявок. Быстро и просто, но глобальный оптимум гарантирован не для всякой задачи.
- Динамическое программирование — задача разбивается на перекрывающиеся подзадачи; каждая решается один раз, результат запоминается в таблице: задача о рюкзаке, редакционное расстояние между строками, оптимальные маршруты.
- Перебор с возвратом (backtracking) — систематический обход дерева вариантов с откатом из тупиков и отсечением бесперспективных ветвей: расстановка ферзей, судоку, раскраска графа.
Почему запоминание решает: числа Фибоначчи «в лоб» — fib(n) = fib(n−1) + fib(n−2) — порождают дерево повторных вызовов: fib(40) пересчитывает fib(20) сотни тысяч раз, сложность O(2ⁿ). Динамическое программирование заполняет таблицу от f₀ к fₙ — каждое число считается один раз, O(n). Тот же ответ: порядка 10⁹ операций против 40.
Линейные структуры данных
Алгоритм всегда работает над данными, и способ их организации определяет цену операций. Линейные структуры выстраивают элементы в последовательность «один за другим»:
- Массив — элементы одного типа в непрерывной области памяти. Доступ по индексу — 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(1). Коллизии (два ключа попали в одну ячейку) разрешают цепочками (список в ячейке) или открытой адресацией (поиск ближайшей свободной ячейки); при заполнении примерно на 70% таблицу расширяют с перехешированием. Худший случай — O(n), если хеш-функция «сваливает» всё в одну ячейку. На хеш-таблицах построены словари Python, объекты JavaScript и поиск «по равенству» в СУБД.
Нелинейные структуры данных: деревья и графы
Классификация: двоичное дерево (не более двух потомков), двоичное дерево поиска (слева меньше, справа больше — поиск O(log n) при сбалансированности), сбалансированные (АВЛ, красно-чёрные — автоматически поддерживают высоту log n), B-деревья — широкие узлы под дисковые страницы (индексы БД — разобраны в разделе 3). Обходы двоичного дерева: прямой (корень–лево–право), симметричный (лево–корень–право — даёт отсортированный порядок в дереве поиска), обратный (лево–право–корень).
Двоичное дерево поиска в работе. Вставляем по очереди 50, 30, 70, 20, 40: 50 — корень; 30 < 50 — влево; 70 > 50 — вправо; 20 — влево от 30; 40 — вправо от 30. Поиск 40: 40 < 50 → влево, 40 > 30 → вправо, найдено — 3 сравнения вместо 5 при линейном просмотре; а симметричный обход (лево–корень–право) выдаёт 20, 30, 40, 50, 70 — отсортированный список «бесплатно».
Ловушка: вставка уже отсортированной последовательности 20, 30, 40, 50, 70 вырождает дерево в список — каждый следующий элемент уходит вправо, и поиск снова O(n). Сбалансированные деревья (АВЛ, красно-чёрные) лечат это поворотами: после вставки высоты поддеревьев выравниваются, и O(log n) гарантирован при любом порядке вставки.
Представление в памяти: матрица смежности 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).
Код Хаффмана в числах. Алфавит и частоты: А — 0,5; Б — 0,25; В — 0,15; Г — 0,1. Дерево строится снизу вверх — на каждом шаге объединяются два самых редких узла:
- В + Г = 0,25. Остались: А (0,5), Б (0,25), [ВГ] (0,25).
- Б + [ВГ] = 0,5. Остались: А (0,5), [БВГ] (0,5).
- Корень: А + [БВГ] = 1. Коды читаются по пути от корня (влево 0, вправо 1): А = 0, Б = 10, В = 110, Г = 111.
Средняя длина: 1·0,5 + 2·0,25 + 3·0,15 + 3·0,1 = 1,75 бита на символ против 2 бит равномерного кода; энтропия Шеннона этих частот ≈ 1,74 бита — код почти достиг теоретического предела. Код префиксный: ни одно кодовое слово не является началом другого, поэтому поток 0110111 читается однозначно: 0·110·111 = АВГ.
Сжатие с потерями — необратимо выбрасывается то, что человек почти не воспринимает: JPEG отбрасывает высокочастотные детали и тонкости цвета (глаз к ним нечувствителен), MP3/AAC — маскируемые звуки, видеокодеки — межкадровые повторы. Выигрыш в разы и десятки раз против процентов у сжатия без потерь; цена — качество, поэтому для текстов, программ и БД оно неприменимо.
Методы формализации алгоритмов
- словесное описание — по шагам на естественном языке;
- блок-схема (ГОСТ 19.701-90): овал — начало/конец, параллелограмм — ввод/вывод, прямоугольник — действие, ромб — ветвление;
- псевдокод — формализованный «полуязык» без привязки к синтаксису;
- запись на языке программирования — окончательная, исполняемая форма.
Базовые управляющие конструкции структурного программирования: следование, ветвление, цикл — их достаточно для записи любого алгоритма (теорема Бёма–Якопини).
Основные символы блок-схем по ГОСТ 19.701-90 (ИСО 5807):
| Символ | Обозначает |
|---|---|
| овал (терминатор) | начало и конец алгоритма |
| прямоугольник (процесс) | действие, вычисление |
| ромб (решение) | проверка условия, ветвление «да / нет» |
| параллелограмм (данные) | ввод и вывод |
| прямоугольник с двойными боковыми линиями | предопределённый процесс — вызов подпрограммы |
| шестиугольник (подготовка) | заголовок цикла с параметром |
| кружок (соединитель) | разрыв линии потока, продолжение в другом месте схемы |
Другие графические нотации: структурограммы Насси–Шнейдермана — алгоритм изображается вложенными прямоугольниками без единой стрелки, произвольный переход goto в этой нотации невозможно даже нарисовать — она навязывает структурность; HIPO-диаграммы — иерархия модулей программы плюс схема «вход – обработка – выход» для каждого модуля; операторные схемы — компактная запись алгоритма цепочкой символов операторов с индексами переходов.
Один алгоритм — три формы записи. НОД по Евклиду для пары (a, b):
- словесно: «пока b ≠ 0, заменять пару (a, b) на (b, a mod b); когда b станет нулём, ответ — a»;
- псевдокод:
пока b ≠ 0: (a, b) ← (b, a mod b); вернуть a; - блок-схема: овал «начало» → параллелограмм «ввод a, b» → ромб «b ≠ 0?» → ветвь «да»: прямоугольник замены и возврат к ромбу; ветвь «нет»: вывод a → овал «конец».
НОД(48, 18): (48, 18) → (18, 12) → (12, 6) → (6, 0) — ответ 6. Все три записи задают одно и то же вычисление, различается лишь степень формальности.
Языки программирования и средства реализации
- По уровню: низкого уровня (машинные коды, ассемблер — близко к архитектуре) и высокого уровня (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) и многозадачные (с вытесняющей или кооперативной многозадачностью);
- по числу пользователей — однопользовательские и многопользовательские (с разграничением прав);
- по организации обслуживания — пакетной обработки (максимальная загрузка ЭВМ, задания очередью), разделения времени (каждому пользователю/задаче — квант процессора, интерактивность), реального времени (гарантированная реакция за заданный срок — управление объектами);
- сетевые (доступ к ресурсам сети) и распределённые (сеть машин выглядит как одна ЭВМ);
- по архитектуре ядра — монолитные и микроядерные.
Отдельно об ОС реального времени: критерий — не средняя скорость, а гарантированность срока реакции. В системах жёсткого реального времени срыв срока равносилен отказу (управление двигателем, подушка безопасности), в системах мягкого — лишь снижает качество (пропуск кадра видео). Планировщик РВ использует фиксированные приоритеты с немедленным вытеснением, а время всех обработчиков ограничено и предсказуемо (QNX, VxWorks, FreeRTOS).
Ключевые понятия: процесс — программа в ходе выполнения со своим адресным пространством; поток — единица планирования внутри процесса; виртуальная память — каждому процессу выделено собственное адресное пространство, страницы которого отображаются на физическую память или вытесняются на диск.
Процесс — квартира: свои стены (адресное пространство), чужие туда не войдут. Потоки — жильцы этой квартиры: работают каждый над своим, но холодильник (память процесса) общий — потому потокам легко обмениваться данными и легко же устроить беспорядок (гонки данных). Виртуальная память — каждому процессу выдают «личную» нумерацию комнат от нуля: процесс думает, что владеет всей памятью, а ОС тайком отображает его номера на реальные физические страницы, лишнее выгружая на диск.
Страничная адресация в числах. Страница 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 захватил Б и ждёт А — оба стоят вечно. Четыре условия возникновения: взаимное исключение, удержание с ожиданием, отсутствие принудительного отъёма, циклическое ожидание. Классическая профилактика — разрушить цикл: захватывать ресурсы всегда в одном и том же порядке.
Межпроцессное взаимодействие (IPC). Процессы изолированы адресными пространствами, поэтому обмен данными организует ОС: программные каналы (pipe — байтовый поток «выход одного — вход другого», как в ls | grep), очереди сообщений, разделяемая память (самый быстрый способ — общий участок памяти, но нужна синхронизация), сигналы — асинхронные уведомления о событиях, и сокеты — универсальный механизм, одинаково работающий в пределах машины и между машинами по сети.
Файловая система
- Файл — именованная область данных на носителе; атрибуты: имя, размер, времена создания и изменения, владелец, права доступа. Каталоги образуют иерархическое дерево; путь — маршрут от корня к файлу.
- Пространство диска выделяется кластерами (блоками). Учёт «какие кластеры принадлежат файлу» ведут по-разному: таблица размещения FAT (цепочки кластеров), индексные узлы (inode в UNIX — у каждого файла структура со ссылками на его блоки), экстенты — непрерывные диапазоны блоков (NTFS, ext4).
- Фрагментация: внешняя — файл раздроблен по несмежным кластерам (на HDD — лишние перемещения головок), внутренняя — потери в последнем недозаполненном кластере.
- Журналирование (NTFS, ext4, XFS) — изменения метаданных сначала записываются в журнал, затем применяются: после сбоя питания ФС восстанавливается быстрой прокруткой журнала, а не полной проверкой диска.
- Примеры: FAT32/exFAT — простые и совместимые (флешки), без прав доступа; NTFS — журнал, права ACL, сжатие и шифрование; ext4, XFS — стандарт в Linux; ZFS, Btrfs — контрольные суммы данных и мгновенные снимки состояния.
Каталог — это тоже файл, только его содержимое — список пар «имя → запись о файле». Поэтому переименование и перенос в пределах диска мгновенны: данные не копируются, меняется одна запись в каталоге. А «удаление» лишь помечает кластеры свободными — на этом работают программы восстановления удалённых файлов, и отсюда же требование гарантированного затирания носителей в защите информации.
Кластеры и фрагментация в числах. Диск с кластером 4 Кбайт, файл 10 Кбайт. Файлу выдаются 3 кластера (12 Кбайт): в последнем пропадают 2 Кбайт — внутренняя фрагментация; в среднем теряется по полкластера на файл, так что миллион мелких файлов «съедает» ~2 Гбайт впустую. Пусть кластеры файла — №5, №9 и №12 (подряд места не нашлось): в FAT это цепочка записей 5 → 9 → 12 → «конец файла», и чтение на HDD требует лишних перемещений головок — внешняя фрагментация замедляет доступ. Дефрагментация переписывает файл в смежные кластеры; на SSD произвольный доступ бесплатен, и дефрагментация не нужна (даже вредна — лишний износ ячеек).
Защита информации
Факторы, повышающие уязвимость информации: рост объёмов и концентрация данных в ЭВМ; расширение круга пользователей, имеющих доступ; удалённый и сетевой доступ; усложнение ПО (ошибки и уязвимости); человеческий фактор.
Основные каналы потери (утечки) информации:
- несанкционированный доступ к данным и носителям (в т.ч. хищение носителей);
- перехват в каналах связи и побочные электромагнитные излучения;
- вредоносные программы (вирусы, трояны) и программные закладки;
- ошибки и умышленные действия персонала, сбои аппаратуры и ПО.
Источники угроз классифицируют по происхождению и умыслу: внешние (злоумышленники, конкуренты, вредоносное ПО из сети) и внутренние (персонал — по статистике до половины инцидентов); случайные (ошибки пользователей, сбои техники, стихийные события) и преднамеренные (атаки). Риск — комбинация вероятности реализации угрозы и величины ущерба: защиту строят от угроз с наибольшим риском, а не «от всего сразу».
Основные формы атак на информацию:
- перехват данных в каналах связи и «человек посередине» (MitM) — злоумышленник незаметно встраивается между сторонами;
- несанкционированный доступ: подбор и кража паролей, использование уязвимостей ПО, повышение привилегий;
- вредоносное ПО: вирусы, черви (распространяются сами по сети), трояны, шифровальщики-вымогатели;
- социальная инженерия и фишинг — атака на человека, а не на технику: поддельные письма и сайты, выманивающие пароли;
- отказ в обслуживании (DoS/DDoS) — лавина запросов, исчерпывающая ресурсы сервера;
- атаки на веб-приложения: SQL-инъекции (подмена запроса к БД через поле ввода), XSS (внедрение скрипта в чужие страницы).
Подходы к защите — три эшелона, работающие вместе: правовые (законодательство о защите информации и персональных данных, ответственность), организационные (политика безопасности, регламенты доступа, обучение персонала, физическая охрана) и программно-технические (всё перечисленное ниже).
Принципы обеспечения безопасности — комплексность и эшелонированность:
- идентификация и аутентификация пользователей (пароли, токены, биометрия);
- разграничение доступа — дискреционное (владелец назначает права: списки ACL) и мандатное (метки секретности); принцип минимума привилегий;
- криптографическая защита — симметричное (один секретный ключ, быстрое — AES, ГОСТ) и асимметричное шифрование (пара открытый/закрытый ключ — RSA; электронная подпись);
- аудит — протоколирование событий безопасности;
- резервное копирование и отказоустойчивость (сохранность и целостность);
- антивирусная защита, межсетевые экраны, физическая защита.
Сохранность и отказоустойчивость в деталях. Резервное копирование строится по правилу «3-2-1»: три копии, на двух разных типах носителей, одна — вне площадки; различают полное, инкрементное (изменения с последней копии любого типа) и дифференциальное (изменения с последнего полного) копирование. Отказоустойчивость дисков дают массивы RAID: RAID 1 — зеркалирование, RAID 5 — чередование с распределённой чётностью (переживает отказ одного диска), RAID 10 — зеркало поверх чередования; RAID 0 (чередование без избыточности) лишь ускоряет и не защищает. Важно: RAID — не замена резервному копированию, он не спасает от ошибочного удаления, шифровальщика и пожара.
Схемы резервного копирования в числах. База 100 Гбайт, за день меняется 5 Гбайт. Полная копия каждый день — 700 Гбайт за неделю. Полная по воскресеньям + инкрементные в будни (изменения с последней копии любого типа) — 100 + 6·5 = 130 Гбайт, но восстановление на среду требует цепочки «полная + все инкременты до среды», и потеря одного звена рушит цепь. Полная + дифференциальные (изменения с последней полной) — 100 + 5 + 10 + 15 + … ≈ 205 Гбайт: объём растёт к концу недели, зато восстановление всегда из двух файлов — полная плюс последняя дифференциальная. Классический размен: объём хранения против скорости и надёжности восстановления.
Идентификация и аутентификация
Три разных шага допуска в систему, которые важно не путать:
- Идентификация — субъект называет себя: логин, номер карты, имя сертификата.
- Аутентификация — субъект доказывает, что он тот, кем назвался.
- Авторизация — система решает, что ему разрешено (разграничение доступа по правам).
Факторы аутентификации — чем можно доказывать:
- знание — пароль, PIN, кодовая фраза; самое дешёвое и самое уязвимое средство (подбор, фишинг, повторное использование);
- владение — токен, смарт-карта, USB-ключ, телефон с одноразовыми кодами;
- биометрия — отпечаток пальца, лицо, радужка, голос; удобно, но «пароль» нельзя сменить при компрометации.
Двухфакторная аутентификация (2FA) комбинирует факторы разных типов (пароль + код на телефон): кража одного фактора не даёт доступа. В корпоративных системах применяются централизованные службы аутентификации и каталогов (Kerberos, LDAP/Active Directory, RADIUS для сетевого доступа).
Как хранить пароли на сервере. Никогда — открытым текстом: утечка БД отдаст все учётные записи. Хранят хеш пароля с солью (случайной добавкой): при входе хешируют введённое и сравнивают. Хеш необратим — по нему пароль не восстановить, а соль не даёт атаковать по заранее посчитанным таблицам и скрывает совпадающие пароли разных пользователей. Именно поэтому «восстановить пароль» невозможно — только сбросить.
Криптография и криптосистемы
Виды криптосистем:
- Симметричные — один секретный ключ на шифрование и расшифровку: блочные (AES, ГОСТ Р 34.12 «Кузнечик» — шифруют блоками по 128 бит) и поточные (бит за битом). Быстрые, но требуют защищённой передачи ключа каждой паре собеседников.
- Асимметричные (с открытым ключом) — пара математически связанных ключей: открытый публикуется, закрытый хранится у владельца (RSA — на сложности факторизации больших чисел, эллиптические кривые). Решают проблему обмена ключами, но в сотни раз медленнее.
- Гибридные — асимметрично согласуют сеансовый ключ, данные шифруют быстрым симметричным алгоритмом; так устроен HTTPS/TLS.
- Хеш-функции (SHA-256, ГОСТ «Стрибог») — необратимая «свёртка» любого сообщения в короткий отпечаток; изменение одного бита меняет хеш до неузнаваемости — контроль целостности и основа ЭЦП.
Симметричное — идея на игрушечном шифре Цезаря (сдвиг букв на k = 3):
- сила: быстро (AES шифрует гигабайты в секунду);
- слабость: как передать ключ собеседнику по открытому каналу?
Асимметричное решает проблему передачи ключа:
- открытый ключ публикуется всем — «вот навесной замок, защёлкните им посылку»;
- закрытый хранится у владельца — «ключ от замка только у меня»;
- зашифровать может любой, расшифровать — только владелец.
На практике комбинируют: асимметрично передают маленький сеансовый ключ, поток шифруют быстрым AES — так работает HTTPS.
Электронная подпись — те же ключи наоборот: автор подписывает хеш документа закрытым ключом, любой проверяет открытым — подтверждаются авторство и неизменность.
RSA на игрушечных числах. Берём простые p = 3, q = 11.
- n = p·q = 33; функция Эйлера φ = (p−1)(q−1) = 20.
- Выбираем открытую экспоненту e = 3 (взаимно проста с 20); закрытую d находим из условия e·d mod φ = 1: d = 7 (3·7 = 21 ≡ 1 mod 20).
- Открытый ключ (e = 3, n = 33) публикуем, закрытый d = 7 храним в секрете.
- Шифрование сообщения m = 4: c = me mod n = 4³ mod 33 = 64 mod 33 = 31.
- Расшифровка закрытым ключом: cd mod n = 31⁷ mod 33 = 4 — исходное сообщение восстановлено.
Для взлома надо разложить n на множители p и q: при n в 33 бита это мгновенно, при 2048 битах — за пределами возможностей современной техники. В этом и асимметрия: перемножить p·q легко, разложить обратно — вычислительно неподъёмно.
Инфраструктура открытых ключей (PKI) закрывает последнюю брешь асимметричной схемы — подмену открытого ключа: сертификат связывает открытый ключ с владельцем и подписан удостоверяющим центром, которому доверяют обе стороны; браузер проверяет цепочку сертификатов сайта вплоть до корневого центра. Российские криптостандарты: подпись ГОСТ Р 34.10 (эллиптические кривые), хеш-функция ГОСТ Р 34.11 «Стрибог». Смежный приём — стеганография: скрывается сам факт передачи (сообщение прячут, например, в младших битах пикселей изображения), тогда как криптография скрывает только содержание.
Каждая буква сдвигается по алфавиту на 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) |
Ни одного умножения и деления — только сложения целых чисел. Именно такие циклы графический контроллер гоняет миллиардами в секунду.
Брезенхем для окружности, R = 5, центр в начале координат. Считается только октант от (0; 5) вправо-вниз — остальные семь получаются симметрией. Параметр решения d показывает, с какой стороны от идеальной окружности лежит середина между кандидатами; старт d = 3 − 2R = −7. При d < 0 шаг вправо (E, d += 4x + 6), иначе — вправо-вниз (SE, d += 4(x − y) + 10):
| шаг | d до шага | ход | пиксел |
|---|---|---|---|
| 1 | −7 < 0 → E | вправо | (1; 5) |
| 2 | −1 < 0 → E | вправо | (2; 5) |
| 3 | +9 ≥ 0 → SE | вправо-вниз | (3; 4) |
| 4 | +7 ≥ 0 → SE | вправо-вниз | (4; 3) |
На (4; 3) октант закончился (x ≥ y); зеркальными отражениями по осям и диагоналям достраивается вся окружность. Как и для отрезка — только целочисленные сложения.
Построчное заполнение многоугольника с чётно-нечётным правилом. Треугольник с вершинами (2; 1), (10; 3), (4; 8); заполняем строку y = 4.
- Пересечения строки y = 4 с рёбрами: ребро (2;1)–(4;8) даёт x ≈ 2,86; ребро (10;3)–(4;8) даёт x = 8,8; ребро (2;1)–(10;3) лежит ниже и строку не пересекает.
- Сортируем абсциссы: 2,86 и 8,8 — одна пара.
- Закрашиваем пикселы между парами пересечений (нечётные интервалы — «внутри»): x = 3…8.
Правило работает для любых, даже невыпуклых контуров: точка внутри, если луч из неё пересекает границу нечётное число раз. В отличие от затравочного метода не нужны ни внутренняя точка, ни стек — многоугольник обходится строка за строкой, поэтому именно так растеризуют полигоны GPU.
Отсечение многоугольника выполняет алгоритм Сазерленда–Ходжмена: контур последовательно «прогоняется» через каждую из четырёх границ окна; на каждой границе вершины либо сохраняются, либо отбрасываются, а пересекающие границу рёбра порождают новые вершины в точках пересечения. Для выпуклого окна результат корректен за один проход по каждой границе.
Сжатие графических данных и форматы
- RLE — кодирование длин серий одинаковых байтов (BMP, PCX);
- LZW — словарное сжатие повторяющихся цепочек (GIF, TIFF);
- Хаффман — частым символам короткие коды;
- JPEG — сжатие с потерями: переход в YCbCr, разбиение на блоки 8×8, дискретное косинусное преобразование, квантование высокочастотных коэффициентов, энтропийное кодирование.
RLE на пальцах — кодируем длины серий:
- скриншоты и чертежи с одноцветными полями RLE ужимает в разы;
- на фотографии соседние пикселы разные — серии длиной 1, файл может даже вырасти.
Хаффман: частым символам — короткие битовые коды, редким — длинные. «Е» в тексте получает 3 бита вместо 8, «Ф» — все 10; в среднем текст ужимается почти вдвое.
LZW — словарный метод (GIF, TIFF): повторяющиеся цепочки заменяются кодами из словаря, который строится на лету и не передаётся — приёмник восстанавливает его сам по тем же правилам. Кодируем «АБАБАБ» (начальный словарь: А = 1, Б = 2):
- Читаем «А» — есть в словаре; «АБ» — нет: выводим код 1 (А), заносим АБ = 3.
- «Б» есть, «БА» — нет: выводим 2 (Б), заносим БА = 4.
- «АБ» есть (код 3), «АБА» — нет: выводим 3, заносим АБА = 5.
- Остаток «АБ»: выводим 3. Итог: 1 2 3 3 — четыре кода вместо шести символов.
Чем длиннее данные, тем длиннее цепочки накапливаются в словаре и тем сильнее сжатие; на коротких файлах выигрыша почти нет.
Почему 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, и каждая точка модели обрабатывается одним умножением. Для сцены из миллиона вершин это и есть разница между «летает» и «тормозит».
Базовые матрицы преобразований
Отражение — масштаб с отрицательным коэффициентом (sx = −1 — зеркало относительно оси y). В 3D матрицы 4×4, поворотов три — вокруг каждой оси; произвольный поворот — их композиция. Перспективная проекция тоже записывается матрицей 4×4: она формирует однородную координату w ~ z, после умножения выполняется перспективное деление (x/w, y/w) — именно оно уменьшает дальние объекты. Полный конвейер вершины в 3D-графике: координаты модели → матрица модели → мировые координаты → матрица вида (камеры) → видовые → матрица проекции и деление на w → экранные; вся цепочка заранее перемножается в одну матрицу.
Проекции и способы задания 3D-объектов
- Параллельные проекции: ортографические (виды спереди/сверху/сбоку), аксонометрические (изометрия — равные углы осей), косоугольные; сохраняют параллельность, применяются в чертежах.
- Центральная (перспективная) проекция — лучи из центра проецирования; удалённые предметы меньше, есть точки схода; реалистичное восприятие.
- Методы задания 3D-объектов: каркасные (вершины и рёбра); поверхностные — полигональные сетки и параметрические поверхности (Безье, B-сплайны); твердотельные — конструктивная блочная геометрия CSG (булевы операции над примитивами), граничное представление B-rep; воксельные.
Классификация проекций уточняется углами. В изометрии все три оси наклонены к картинной плоскости одинаково (проекции осей — под 120°, коэффициенты искажения равны ≈ 0,82; по ГОСТ для простоты принимают 1), в диметрии равны два коэффициента, в триметрии все разные. Косоугольные проекции (кавальерная, кабинетная) проецируют параллельными лучами не по нормали к плоскости — фронтальная грань изображается без искажений. У перспективной проекции считают точки схода — точки, в которых сходятся изображения параллельных прямых: одно-, двух- или трёхточечная перспектива в зависимости от того, сколько осей объекта не параллельны картинной плоскости.
Перспективная проекция в числах. Центр проецирования в начале координат, картинная плоскость z = d = 2. Точка (2; 1; 4) проецируется лучом в (x·d/z; y·d/z) = (1; 0,5); такая же точка вдвое дальше, (2; 1; 8), — в (0,5; 0,25): вдвое дальше — вдвое меньше, это и есть перспективное сокращение. В параллельной ортографической проекции обе точки легли бы в одно место (2; 1) — размер от глубины не зависит; поэтому чертежи выполняют в параллельных проекциях: по ним можно измерять.
Удаление скрытых поверхностей
- 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: никакой сортировки сцены.
Методы удаления скрытых поверхностей делят на работающие в пространстве объекта (сравнивается сама геометрия сцены — точно при любом увеличении, но дорого при большом числе граней: метод приоритетов, BSP-дерево) и в пространстве изображения (видимость решается по-пиксельно с точностью экрана: z-буфер, Варнок). Сводное сравнение:
| Метод | Пространство | Сильная сторона | Слабая сторона |
|---|---|---|---|
| Z-буфер | изображения | прост, любой порядок граней, аппаратен (GPU) | память под буфер, точность глубины (z-fighting) |
| Приоритетов (художника) | объекта | без буфера, естественен для полупрозрачности | сортировка каждый кадр; пересечения и циклические перекрытия граней |
| Варнока | изображения | адаптивен: дробит экран только в сложных местах | в худшем случае рекурсия до отдельного пиксела |
| BSP-дерево | объекта | сортировка предвычислена — быстрый вывод с любой камеры | дорогое построение; не подходит для динамичной геометрии |
Тени: теневые карты (сцена «глазами» источника, сравнение глубин), теневые объёмы, а в трассировке лучей — теневые лучи к источнику.
Алгоритм «плавающего горизонта»
Классический метод удаления невидимых линий при изображении поверхности z = f(x, y) сеткой кривых (по методичке Васильева). Кривые рисуются от ближней к дальней, и в каждом столбце экрана поддерживаются два массива — верхний и нижний горизонты: максимальная и минимальная высота уже нарисованного. Точка очередной кривой видима, только если она выше верхнего горизонта или ниже нижнего — иначе она заслонена более близкими кривыми и не рисуется; после отрисовки горизонты обновляются. Так строятся привычные «каркасные» 3D-графики функций.
Модели освещения и закраска
Модели освещения делятся на локальные — учитывают только свет от источников и ориентацию поверхности — и глобальные — учитывают также свет, отражённый другими объектами сцены и прошедший сквозь них (переотражения, зеркала, каустики); глобальную модель реализует трассировка лучей. Локальная модель освещения (Фонга) складывает три компоненты:
- фоновая (ambient) — рассеянный свет среды;
- диффузная (Ламберта) — пропорциональна косинусу угла между нормалью N и направлением на источник L, не зависит от наблюдателя;
- зеркальная (Фонга) — блик, зависит от угла между отражённым лучом R и направлением на наблюдателя V; показатель n задаёт «резкость» блика.
Уточнения модели: при нескольких источниках диффузная и зеркальная компоненты суммируются по всем источникам; для точечных вводится ослабление с расстоянием — множитель 1/(a + b·d + c·d²). Типы источников: направленный (солнце — лучи параллельны), точечный, прожектор (конус с углом отсечки). Векторы N, L, R, V — единичные; отражённый луч R = 2(N·L)N − L. В аппаратной реализации вместо R·V часто берут «половинный вектор» H = (L + V)/|L + V| и скалярное произведение N·H — модель Блинна–Фонга, дешевле и численно стабильнее.
Закраска Гуро: интенсивность вычисляется в вершинах и линейно интерполируется по грани — быстро, но блики «теряются» внутри граней. Закраска Фонга: по грани интерполируется нормаль, освещение считается в каждом пикселе — качественные блики, дороже.
Числа к модели освещения (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 для бикубического куска Безье).
Форма Эрмита в развёрнутом виде — через концевые точки P₀, P₁ и касательные векторы R₀, R₁:
Формы взаимно пересчитываются: касательные Эрмита выражаются через внутренние точки Безье — R₀ = 3(P₁ − P₀), R₁ = 3(P₃ − P₂). Гладкое соединение сегментов: C⁰ — общая точка стыка; C¹ — равные касательные (у двух кривых Безье точки P₂, P₃ первой и P₀, P₁ второй лежат на одной прямой, стык — посередине); G¹ — касательные сонаправлены, но могут различаться длиной (геометрическая непрерывность). Бикубическая поверхность Безье — тензорное произведение: P(u, v) = ΣΣ Bi(u)·Bj(v)·Pij по сетке 4×4 из 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.
Как работает алгоритм «плавающего горизонта»?
Метод удаления невидимых линий при изображении поверхности z = f(x, y) семейством кривых-сечений. Кривые рисуются от ближней к дальней; для каждого столбца экрана хранятся верхний и нижний горизонты — максимум и минимум уже нарисованного. Точка новой кривой видима, только если она выше верхнего или ниже нижнего горизонта; после отрисовки горизонты обновляются. Используется для каркасных 3D-графиков функций.