Теоретические основы информатики

Вопросы
0. Введение в дисциплину
1. Исходные понятия информатики. Начальные определения.
2. Формы представления информации.
3. Преобразование сообщений.

Информатика - фундаментальная естественная наука, изучающая общие свойства информации, процессы, методы и средства ее обработки (сбор, хранение, преобразование, перемещение, выдача).
определение академиков А.П. Ершова и Б.Н. Наумова

Наумов Борис Николаевич
Дата рождения:
10 июля 1927
Дата смерти:
11 июня 1988
Институт автоматики и телемеханики, 1950 г., За 17 лет, проведённых в стенах превратился в крупного специалиста по нелинейным системам автоматического управления. Уже были защищены кандидатская (1955 г.) и докторская (1965 г.) диссертации, и — когда Б. Н. Наумову исполнилось 40 лет (1967 г.) — ему предложили возглавить Институт электронных управляющих машин.

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

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

Прикладная информатика
обеспечивает:
1). Создание информационных систем (ИС).
2). Разработку программного обеспечения для ИС.
3). Применение ИС для решения практических задач.

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

Литература
Стариченко Б. Е. Теоретические основы информатики: Учебное пособие для вузов. - 2-е изд. перераб. и доп. - М.: Горячая линия - Телеком, 2003. - 312 с.; ил.
Теоретические основы информатики: Учебное пособие. Стандарт третьего поколения, Забуга А.А.
2014. – 208 с.; ил.

Раздел 1.
ТЕОРИЯ ИНФОРМАЦИИ
Теория информации возникла в ходе решения задачи:
«Обеспечить надежную и эффективную передачу информации от источника к приемнику при условии, что передаче этой препятствуют помехи»

«Математическая теория связи» статья, 1948 г. сделавшая его всемирно известным.
Основатель теории информацииОснователь теории информации, нашедшей применение в современных высокотехнологических системах связи. Шеннон внес огромный вклад в теорию вероятностных схем, теорию автоматовОснователь теории информации, нашедшей применение в современных высокотехнологических системах связи. Шеннон внес огромный вклад в теорию вероятностных схем, теорию автоматов и теорию систем управленияОснователь теории информации, нашедшей применение в современных высокотехнологических системах связи. Шеннон внес огромный вклад в теорию вероятностных схем, теорию автоматов и теорию систем управления — области наук, входящие в понятие «кибернетика».
В 1948 году предложил использовать слово «бит» для обозначения наименьшей единицы информации.
Клод Э́лвуд Ше́ннон
(Claude Elwood Shannon);
30 апреля30 апреля 1916
24 февраля24 февраля 2001

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

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

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

Определение: Сигнал - изменение характеристики носителя, которое используется для представления информации.
Определение: Параметр сигнала -значение этой характеристики отнесенное к некоторой шкале измерений.

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

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

Определение. Соответствие между сообщением и содержащейся в нем информацией называется правилом интерпретации сообщения.
1) однозначное - имеет лишь одно правило интерпретации.
2) неоднозначное.

Определение: Источник информации - это субъект или объект, порождающий информацию и представляющий ее в виде сообщения.
Определение: Приемник информации - это субъект или объект, принимающий сообщение и способный правильно его интерпретировать.

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

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

«непрерывное сообщение» и «дискретное сообщение».
«непрерывная информация» и «дискретная информация».
«информация, представленная посредством непрерывных сигналов»
и «информация, представленная посредством дискретных сигналов»

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

Природа знака - жест, рисунок, буква, сигнал светофора, определенный звук и т.д.
Природа знака определяется носителем сообщения и формой представления информации в сообщении.
Определение: Набор знаков, в котором установлен порядок их следования, называется алфавитом.

1.3. Преобразование сообщений

Преобразование типа
N1 → N2
Примерами устройств: микрофон (звук преобразуется в электрические сигналы); магнитофон и видеомагнитофон (чередование областей намагничения ленты превращается в электрические сигналы, которые затем преобразуются в звук и изображение); и др.
Особенностью - всегда сопровождается частичной потерей информации. Потери связаны с помехами (шумами), которые порождает само информационное техническое устройство и шумы извне.

Преобразованию типа
N1 → D2
Необходимо заменить непрерывную функцию времени Z(t) на некотором отрезке [t1, t2] конечным множеством (массивом) {Zi, ti}
(i - 0...n, где n - количество точек разбиения временного интервала).
Подобное преобразование – дискретизация непрерывного сигнала.
Осуществляется посредством двух операций: 1) развертки по времени
2) квантования по величине сигнала.

Определение: Развертка по времени - в определенные моменты времени с интервалом ∆t, производится наблюдение за значением величины Z.
(1)
Определение: Квантование по величине - это отображение вещественных значений параметра сигнала в конечное множество чисел.
Шаг квантования - ∆Z.

При дискретизации может происходить потеря части информации, связанной с особенностями функции Z(t), поскольку n - величина конечная.

Влади́мир Алекса́ндрович Коте́льников (24 августа [6 сентябряВлади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908Влади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, КазаньВлади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, Казань, Российская империяВлади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, Казань, Российская империя — 11 февраляВлади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, Казань, Российская империя — 11 февраля 2005Влади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, Казань, Российская империя — 11 февраля 2005, МоскваВлади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, Казань, Российская империя — 11 февраля 2005, Москва, РоссияВлади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, Казань, Российская империя — 11 февраля 2005, Москва, Россия) — советский и российский учёный в области радиотехники, радиосвязи и радиолокации планетВлади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, Казань, Российская империя — 11 февраля 2005, Москва, Россия) — советский и российский учёный в области радиотехники, радиосвязи и радиолокации планет, академик Академии наук СССРВлади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, Казань, Российская империя — 11 февраля 2005, Москва, Россия) — советский и российский учёный в области радиотехники, радиосвязи и радиолокации планет, академик Академии наук СССР (1953) и Российской академии наукВлади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, Казань, Российская империя — 11 февраля 2005, Москва, Россия) — советский и российский учёный в области радиотехники, радиосвязи и радиолокации планет, академик Академии наук СССР (1953) и Российской академии наук, дважды Герой Социалистического ТрудаВлади́мир Алекса́ндрович Коте́льников (24 августа [6 сентября] 1908, Казань, Российская империя — 11 февраля 2005, Москва, Россия) — советский и российский учёный в области радиотехники, радиосвязи и радиолокации планет, академик Академии наук СССР (1953) и Российской академии наук, дважды Герой Социалистического Труда (1969, 1978), председатель Верховного совета РСФСР (1973—1980). Один из основоположников советской секретной радио- и телефонной связи.

Теорема отсчетов. Теорема Котельникова 1933 г. (формулировка 1)
Непрерывный сигнал можно полностью отобразить и точно воссоздать по последовательности измерений или отсчетов величины этого сигнала через одинаковые интервалы времени, меньшие или равные половине периода максимальной частоты, имеющейся в сигнале.

Теорема отсчетов (Котельникова) (формулировка 2). Развертка по времени может быть осуществлена без потери информации, связанной с особенностями непрерывного (аналогового) сигнала, если шаг развертки не будет превышать ∆t, определяемый в соответствии с (2).
(2)

Например, для точной передачи речевого сигнала с частотой до Vm = 4000 Гц при дискретной записи должно производиться не менее n=8000 отсчетов в секунду; в телевизионном сигнале Vm = 4 МГц, следовательно, для его точной передачи потребуется около n=8000000 отсчетов в секунду.
Преобразование сигналов типа N1 → D2, как и обратное D1 → N2, может осуществляться без потери содержащейся в них информации.