Алгоритм (нестрогое определение) - это точно определенная (однозначная) последовательность простых (элементарных) действий, обеспечивающих решение любой задачи из некоторого класса. Алгоритм - это любая конечная система правил преобразования информации (данных) над любым конечным алфавитом (определение В.М. Глушкова). Алгоритм структурный, если он может быть представлен стандартным функциональным блоком. Алфавит - набор знаков, в котором установлен порядок их следования (лексикографический порядок). Анализ - метод исследования, основанный на выделении отдельных компонентов системы и рассмотрении их свойств и связей. Бит - единица измерения энтропии при двух возможных равновероятных исходах опыта. Внешние запоминающие устройства (ВЗУ) - устройства, выполняющие операции, связанные с сохранения и считывания данных на материальном носителе. Данные - это сведения, характеризующие какую-то систему, явление, процесс или объект, представленные в определенной форме и предназначенные для дальнейшего использования. Декодирование - операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов. Дискретные устройства - те, у которых дискретны множества внутренних состояний, входных и выходных сигналов, а также множество моментов времени, в которые поступают входные сигналы, меняются внутренние состояния и выдаются выходные сигналы. Документ - продукт, сформированный в результате исполнения некоторой программы. Запись логическая - поименованная совокупность элементарных данных, имеющая смысловую завершенность. Запись физическая - элемент поверхности носителя, на котором в соответствии с физическими принципами функционирования носителя размещаются данные, составляющие логическую запись. Запоминающие устройства с произвольным доступом - те, в которых доступ к данным осуществляется по адресу ячейки, где они хранятся. Знак - элемент некоторого конечного множества отличных друг от друга сущностей, используемого для представления дискретных сигналов. Избыточность кода относительная - характеристика, показывающая, во сколько раз требуется удлинить сообщение, чтобы обеспечить его надежную (безошибочную) передачу (хранение). Информатика - фундаментальная естественная наука, изучающая общие свойства информации, процессы, методы и средства ее обработки (сбор, хранение, преобразование, перемещение, выдача) (определение А.П. Ершова и Б.Н. Наумова). Информация (статистическое определение) - это содержание сообщения, понижающего неопределенность некоторого опыта с неоднозначным исходом; убыль связанной с ним энтропии является количественной мерой информации. Информационный процесс - это изменение с течением времени содержания информации или представляющего его сообщения. Исполнитель алгоритма - это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий. Источник информации - это субъект или объект, порождающий информацию и представляющий ее в виде сообщения. Класс - это множество объектов, обладающих одним или несколькими одинаковыми атрибутами; эти атрибуты называются полем свойств класса. Классификация - это распределение однотипных объектов в соответствии с выделенными свойствами (признаками, категориями, классами). Конечным автомат - система <X, Y, Q, Y, Q> , в которой X и Y являются конечными входным и выходным алфавитами, Q - конечным множеством внутренних состояний, Y (x, q) - функцией переходов и Q (x, q) - функцией выходов. Код - (1) правило, описывающее соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита. (2) знаки вторичного алфавита, используемые для представления знаков или их сочетаний первичного алфавита. Кодирование - перевод информации, представленной посредством первичного алфавита, в последовательность кодов. Массив - упорядоченная линейная совокупность однородных данных. Материальный носитель информации - материальный объект или среда, которые служат для представления или передачи информации. Машинное слово - (1) совокупность двоичных элементов, обрабатываемая как единое целое в устройствах и памяти компьютера; (2) данные, содержащиеся в одной ячейке памяти компьютера. Моделирование - построение упрощенного варианта прототипа, обеспечивающего приемлемую для данной задачи точность описания его строения или поведения. Моделирование имитационное - метод исследования, основанный на том, что изучаемый прототип заменяется ее имитатором - натурной или информационной моделью - с которым и проводятся эксперименты с целью получения информации об особенностях прототипа. Модель - это объединение составных частей (элементов) и связей между ними, отражающая существенные для данной задачи свойства прототипа. Модель математическая - это множество элементов произвольной природы, на которых определено конечное множество отношений. Модель проверяемая - та, у которой результат ее использования может быть соотнесен (сравнен) с прототипом. Набор знаков - набор знаков, в котором установлен порядок их следования. Объект - простейшая составляющая сложного объединения, обладающая следующими качествами: · в рамках данной задачи он не имеет внутреннего устройства и рассматривается как единое целое; · у него имеется набор свойств (атрибутов), которые изменяются в результате внешних воздействий; · он идентифицирован, т.е. имеет имя (название). Правило интерпретации сообщения - соотношение (закон), устанавливающий соответствие между сообщением и содержащейся в нем информацией. Приемник информации - это субъект или объект, способный принять сообщение и правильно его интерпретировать. Программа - последовательность действий по обработке информации исполнителем «компьютер». Программный объект - это совокупность некоторого набора данных и процедур, определяющих возможности их изменения. Свойство (атрибут) - качество объекта, для которого установлена мера. Сигнал - изменение характеристики материального носителя, которое используется для представления информации. Сигнал непрерывный (аналоговый) - его параметр может принимать любое значение в пределах некоторого интервала. Сигнал дискретный - его параметр может принимать конечное число значений в пределах некоторого интервала. Синтез- (1) метод исследования (изучения) системы в целом (т.е. компонентов в их взаимосвязи), сведение в единое целое данных, полученных в результате анализа; (2) создание системы путем соединения отдельных компонентов на основании законов, определяющих их взаимосвязь. Система - совокупность взаимодействующих компонентов, каждый из которых в отдельности не обладает свойствами системы в целом, но является ее неотъемлемой частью. Система счисления - это правило записи чисел с помощью заданного набора специальных знаков - цифр. Система счисления позиционная - те, в которых значение каждой цифры в изображении числа определяется ее положением (позицией) в ряду других цифр. Сложность алгоритма временная - это функция, которая каждой входной длине слова п ставит в соответствие максимальное (для всех конкретных однотипных задач длиной п) время, затрачиваемое алгоритмом на ее решение. Сообщение - последовательность сигналов. Сообщения шенноновские - те, в которых вероятность появления каждого отдельного знака не меняется со временем. Структура данных - перечень объединяемых одиночных данных, их характеристики, а также особенности связей между ними образуют. Схема - это комбинация базисных элементов, в которой выходы одних элементов присоединяются к входам других. Тезиса Тьюринга: всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга. Тезис Черча: Класс алгоритмически (или машинно) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций. Теорема Бома-Джакопини: любой алгоритм может быть сведен к структурному. Теорема Котельникова (теорема отсчетов): Непрерывный сигнал можно полностью отобразить и точно воссоздать по последовательности измерений или отсчетов величины этого сигнала через одинаковые интервалы времени, меньшие или равные половине периода максимальной частоты, имеющейся в сигнале. Терема Шеннона (первая): при отсутствии помех передачи всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак кодируемого алфавита, будет сколь угодно близко к отношению средних информации на знак первичного и вторичного алфавитов. Терема Шеннона (вторая): при передаче информации по каналу с шумом всегда имеется способ кодирования, при котором сообщение будет передаваться со сколь угодно высокой достоверностью, если скорость передачи не превышает пропускной способности канала. Условие Фано: неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом какого-либо иного более длинного кода. Файл - определенным образом оформленная совокупность физических записей, рассматриваемая как единое целое и имеющая описание в системе хранения информации. Формальная грамматика - система правил, описывающая множество конечных последовательностей символов формального алфавита. Формальный исполнитель - субъект или устройство, способные воспринимать и анализировать указания алгоритма, изменять в соответствии с ним свое состояние, а также обладающие механизмом исполнения, способным производить пошаговую обработку информации. Формальная система - это математическая модель, задающая множество дискретных компонентов путем описания исходных объектов и правил построения новых компонентов из исходных и уже построенных. Функциональный блок - часть алгоритма, организованная как простое действие, т.е. имеющая один вход (выполнение начинается всегда с одного и того же действия) и один выход. Черный ящик - это система, строение которой неизвестно пользователю, однако, известна ее реакция на определенные внешние воздействия. Ширина полосы пропускания - интервал частот, используемый данным каналом связи для передачи сигналов. Экономичность системы счисления - то количество чисел, которое можно записать в данной системе с помощью определенного количества цифр. Энтропия есть мера неопределенности опыта, в котором проявляются случайные события, равная средней неопределенности всех возможных его исходов. |
Постановка задачи кодирования, Первая теорема Шеннона Вернуться в оглавление: Теоретические основы информатики |