Классификация и грамматика ФЯ
Кто в 1956 году предложил классификацию формальных языков, ставшую фундаментом теории вычислений?
Ноам Хомский
Как расшифровывается аббревиатура ДКА, НКА в теории автоматов? Для чего они используются?
Детерминированный конечный автомат, недетерминированный конечный автомат.
Оба они относятся к классу конечных автоматов — абстрактных машин, которые имеют набор состояний и переходят из одного состояния в другое в ответ на входные сигналы (символы).
Несмотря на абстрактность, эти ребята работают «под капотом» множества привычных вещей:
Регулярные выражения (RegEx): Когда вы пишете поиск почты по шаблону [a-z]+@[a-z]+\.com, движок часто преобразует это выражение сначала в НКА (его проще построить по правилам), а затем в ДКА (его быстрее исполнять компьютеру).
Лексический анализ: Компиляторы (GCC, Clang) и интерпретаторы (Python) используют конечные автоматы, чтобы разбивать ваш код на токены: ключевые слова, имена переменных, числа.
Протоколы связи: Описание состояний сетевого соединения (например, в TCP) — это классический конечный автомат (соединение установлено, ожидание, закрыто).
Проектирование «железа»: Цифровые микросхемы и контроллеры часто проектируются как логические автоматы.
Как называется минимальная единица измерения количества информации, соответствующая одному выбору между двумя равновероятными исходами?
Бит
Как называется свойство кода, при котором ни одно кодовое слово не является началом другого, что позволяет декодировать сообщение мгновенно?
Префиксность (префиксный код).
Какой алгоритм сжатия (сочетающий идеи LZ77 и кодирование Хаффмана) является базовым для популярного формата ZIP?
Deflate
Как называется тип грамматик (Тип 3), который используется для описания простейших конструкций, таких как идентификаторы или числа в языках программирования?
Регулярные грамматики
Как называется графическое представление синтаксиса языка, альтернативное текстовым правилам EBNF?
Синтаксические диаграммы (или диаграммы Вирта)
Как в теории информации называется мера неопределенности или случайности системы?
Энтропия (Шеннона).
Какой алгоритм использует «жадную» стратегию построения кодового дерева снизу вверх, объединяя символы с наименьшими вероятностями?
Алгоритм Хаффмана.
На каком математическом преобразовании (ДКП) основан метод сжатия в формате JPEG?
Дискретное косинусное преобразование.
Какая форма записи, являющаяся расширением Бэкуса-Наура, использует квадратные скобки для обозначения необязательных элементов и фигурные — для повторений?
EBNF (Extended Backus-Naur Form).
Эквивалентны ли по своей распознающей способности детерминированные (ДКА) и недетерминированные (НКА) конечные автоматы?
Да (любой НКА можно преобразовать в эквивалентный ДКА).
Как называется способность системы сохранять или восстанавливать информацию при наличии шумов или сбоев в канале связи?
Отказоустойчивость
К какому классу алгоритмов сжатия относятся методы Хаффмана и Фано: с потерями или без потерь?
Без потерь (Lossless).
Почему формат JPEG считается форматом «с потерями»?
Потому что в процессе квантования часть высокочастотной визуальной информации безвозвратно удаляется.
К какому типу по Хомскому относятся языки, распознаваемые автоматами с магазинной памятью (PDA)?
Контекстно-свободные языки (Тип 2)
Какой математический аппарат используется для компактного описания множества строк, принимаемых конечным автоматом?
Регулярные выражения.
Что происходит с энтропией сообщения, если символы в нем становятся сильно зависимыми друг от друга (появляется предсказуемость)?
Энтропия уменьшается.
Какое условие (неравенство) связывает длины кодовых слов в префиксном коде и является необходимым для его существования?
Неравенство Крафта.
Как называется структура данных, имитирующая бесконечную ленту и используемая автоматами Келлера для анализа вложенных конструкций?
Стек (или магазинная память).
Какое ключевое ограничение накладывается на правила вывода в контекстно-зависимых грамматиках (Тип 1) относительно длины строк?
Длина правой части правила должна быть не меньше длины левой части (правила не должны быть сокращающими)
Какая теорема (лемма) используется для доказательства того, что конкретный язык (например, $a^n b^n$) не является регулярным?
Лемма о разрастании (Pumping Lemma).
Какое понятие описывает наличие в сообщении данных, которые можно удалить без потери смысла (разность между физической длиной и информационной емкостью)?
Избыточность.
В чем заключается главное отличие построения кодов в алгоритме Фано по сравнению с алгоритмом Хаффмана?
Фано строит дерево «сверху вниз», последовательно разделяя алфавит на две группы с примерно равными вероятностями.
Какая часть процесса сжатия в JPEG отвечает за фактическое уменьшение объема данных после выполнения ДКП и квантования?
Энтропийное кодирование (обычно алгоритм Хаффмана или арифметическое кодирование).