Лекции по дисциплине «Информатика» (стр. 1 )

Министерство образования и науки Российской Федерации

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

им. А. Н. ТУПОЛЕВА

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

Лекции по дисциплине

«Информатика»

Направление 230100 "Информатика и вычислительная техника"

Специальность 230101 – "Вычислительные машины, комплексы, системы и сети"

Учебно-методическое пособие

Казань 2007г.

Лекция 1.

.  Введение. История информатики. Измерение

.  и кодирование информации.

. 

Интуитивно мы понимаем, что такое информация и, поэтому, при получении сообщения используем различные выражения, например:

“ это сообщение не дает мне никакой информации”,

что приводит к пониманию взаимоотношения между информацией и передаваемым сообщением.

В связи с этим и было введено первоначальное понятие: информация (от латинского informatio) - разъяснение, изложение, осведомленность. В дальнейшем, в связи развитием информатизации общества понятие существенно расширилось. Таким образом, широта применения информатики влечет за собой колоссально большую “емкость" понятия информации и, следовательно, большую степень неопределенности и избыточности.

В социальных, “ручных” системах основной носитель информации - документы и, соответственно, - знаки, символы, графики, рисунки, чертежи.

Функция, выдаваемая источником, x(t) может быть непрерывная, дискретная и смешанная (рис.1.1):

- непрерывные функции x(t) c непрерывным аргументом t, т. е. значение функции может иметь бесконечное число значений в интервале (xmin, xmax ) и бесконечное число значений в интервале (tmin , tmax );

- непрерывные функции x(t) с дискретным аргументом t, т. е. значения функции имеют существенные значения только в определенные выделенные моменты времени ti, i = 1 ¸ n ;

- дискретные функции xi(t), с непрерывным аргументом t, т. е. функция может принимать только конечное число значений, в заданном интервале, x1 (t), x2 (t),..., xn (t), в то время как аргумент t - произвольное количество значений в заданном интервале;

- дискретные функции xi(t), с дискретным аргументом ti, т. е. и функция и аргумент принимают конечное число значений в заданных интервалах.

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

Съем информации по времени t осуществляется только в определенные моменты ti,, i = 1 ¸ n, например, через равные промежутки Dt (в принципе интервалы могут быть любыми) (рис.1). Такое преобразование называют дискретизацией (рис.1.1а).

Аналогичные преобразования производят и по значениям функции. Для этого на интервале значений функции (xmin, xmax) выделяют несколько значений, уровней, например, через равные промежутки (случай, аналогичный предыдущему). Такое преобразование называют квантованием по уровню (рис.1.1б, в).

Каждой выделенной точке можно сопоставить символ, букву, число (как символ) и т. п., т. е. кодировать, представить в виде некоторых данных, для чего выбираются методы кодирования.

Кодирование- установление соответствия между элементом данных и совокупностью символов, называемой кодовой комбинацией (словом кода); отожествление данных с их кодовой комбинацией.

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

Рис.1.1. Преобразование исходной информации

Информация преобразуется к двоичному представлению, при хранении – это биты, и каждый элемент данных формируется как знаки “1” и “0”. Преобразователи сопоставляют знакам электрические сигналы. На рис. 1.2а. “1”- соответствует высокий потенциал, “0” - низкий на рис.1.2б. - “1” - соответствует серия импульсов, 0” – их отсутствие (динамическая форма).

Рис.1.2. Представление сигналов в дискретном виде

Таким образом, здесь фактически выбран алфавит из знаков “1” и “0”.

Измерение информации

Бурное развитие средств и систем связи в 30-х годах нашего столетия привело к необходимости разработки методов оценки количества информации. Основные теоретические положения были сформулированы в 40-х годах в работах К. Шеннона в связи с необходимостью развития системы передачи военной информации. В качестве единицы количества информации было принято то количество информации, которое содержится в некотором стандартном сообщении.

Одно из представлений направлений включает следующие системы показателей: прагматическая, семантическая, синтаксическая, познавательная.

Прагматическое направление и показатели предназначено для систем передачи обработки и хранения информации, т. е. для технических параметров систем информации.

Дискретные значения аргумента и функции представляют в виде набора символов некоторого алфавита. Если обработка этих значений осуществляется арифметическими преобразованиями, то символы определяются цифровыми символами в выбранной системе счисления.

Для однозначного описания каждого уровня функции (или точки аргумента ti рис.1.6) выделим некоторое количество символов - q, например, знаков выбранного алфавита (в русском q будет равно 33, в английском – 26 и т. п.) и некоторое количество позиций, длину слова, - n. Тогда общее возможное количество описываемых уровней функции будет определяться количеством общим числом комбинаций (числом произвольных слов, смысловая составляющая здесь не учитывается) и определится как N = qn. При слове длины n = 2 и русском алфавите, число комбинаций N = 332 = 1089, т. е. можно обозначить такое количество уровней.

В ИС, для простоты реализации, в цифровых системах, практически всегда выбирают двоичный алфавит, состоящий только из символов “1” и “0” Количество комбинаций двоичного слова длины n будет N = 2n. Двоичное слово длины n называют байтом, в настоящее время принято считать n=8.

Объем информации может измеряться длиной необходимого слова в выбранном алфавите, так если имеется N – “количество информации”, число уровней, и выбран алфавит размерности q, то требуется найти n. Так как N = qn, то n = logq N, это для технической информатики не выгодно (средства реализации!), поэтому все (количество информации - I(q)) сводят к определению количества необходимых бит

I(q) = n log2 q

Один бит соотносят одному элементу информации, тогда общее количество информации от множества k источников с алфавитами длиной qi, равно

I(q1, q2, qk) = I(q1) + I(q2) + I(q3) + ….+ I(qk)

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

В целом заранее не известен вид и количество информации поступающей информации об объектах, она может быть произвольной, случайной. Аддитивная мера, в условиях неопределенности, “полагает”, что каждый знак поступает с равной вероятностью (“приближенно” – с равной частотой, возможностью).

В реальных условиях в сообщениях информация поступает с разной возможностью (вероятностью) для различных знаков. В этом случае объем информации определяют как

I = - S pi log2 pi,

где i – номер знака (символа), i - 1¸ n, pi – вероятность (возможность) появления знака (символа) в сообщении, pi принимает значение 0£pi£ I. I – называют энтропией , очевидно, что она определяет возможность появления различных знаков в условиях “неопределенности”, случайного появления знаков. Подобная оценка называется статистической мерой информации и широко используется в технических системах.

В систему показателей количества и качества информации включаются следующие показатели:

- важность - значимость информации с точки зрения тех задач, для решения которых используется оцениваемая информация, полнота информации для решаемых задач;

- адекватность - соответствие текущему состоянию соответствующих объектов или процессов;

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

- толерантность поступающей информации

Важность информации всецело определяется необходимостью и достаточностью для решения конкретных задач.

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

Объективность, очевидно, зависит от способа получения значений характеристик предмета, процесса или явления и качества реализации (использования) способа в процессе получения этих знаний. Значения адекватности точно определить сложно (в отличие от статистических методов), поэтому методы сводятся к введению некоторых характеристик и коэффициентов.

Релевантность - характеристика соответствия содержания потребностям решаемой задачи. Количественно релевантность определяется коэффициентом Кp = Np / No, где - Np - количество релевантной информации, No - общее количество информации. Проблема заключается в сложности, а порою и невозможности, определения количества информации.

Толерантность - показатель удобства восприятия и использования информации для решаемых задач. Определение является неопределенным, субъективным и значение показателя представляется качественно.

Система семантических показателей - характеризует смысловое содержание оцениваемой информации. Оценки ценности информации осуществляется двумя методами.

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

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

Остальные показатели используются в различных направлениях и находятся в стадии разработки.

Таким образом: количество, качество и ценность информации в целом по информационной системе определяется оценкой по всей системе показателей.

.  Раздел 2

.  Логические основы информатики

Лекция 2. Основные понятия и определения

В ЭВМ обрабатывается числовая информация, представленная в двоичной системе счисления (0 и 1). Любую схему ЭВМ можно рассматривать как устройство, имеющее n входных сигналов и m выходных. Поступления на входы некоторой последовательности 0 и 1 вызывает появление на выходах вполне определенной последовательности 0 и 1.

В ЭВМ различают два больших класса схем: класс комбинационных (логических) схем и класс конечных автоматов. В комбинационных схемах значение выходных сигналов в момент времени t однозначно определяется входными сигналами в тот же момент времени. В конечных автоматах выходные сигналы определяются не только входными сигналами, но и состоянием схемы (конечные автоматы содержат элементы памяти).

Построение схем ЭВМ решается с помощью аппарата математической логики. При этом используется только самая простая ее часть – алгебра логики. Основным понятием в той части алгебры логики, на которой основывается ее применение к построению схем ЭВМ, является понятие переключательной функции.

Переключательной или булевой функцией называется функция f(x1, ,x2, … xn), способная принимать как и ее аргументы x1, … , xn только два значения 0 или 1. Любая переключательная функция (ПФ) может быть задана таблицей ее значений в зависимости от значений ее аргументов. Такая таблица называется таблицей истинности.

Пример. Зададим ПФ трех аргументов f(x1, x2, x3). Так как каждый из аргументов принимает лишь 2 значения, поэтому мы имеем 8 различных комбинаций 3 переменных. Эти комбинации называют набором. Наборы обычно пишут в так называемом естественном порядке, когда наборы принимают значения (000), (001), … Для получения следующего набора прибавляют 1 к правому разряду – применяется как бы сложение чисел. Наборам присваивается номер, равный двоичному числу, соответствующему данному набору. Сопоставляя каждому набору одно из двух значений ПФ, мы и получим таблицу истинности (например, представленную в табл.2.1).

Таблица 2.1

x1 x2 x3 f(x1,x2,x3) 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

Любая ПФ n аргументов определена на 2n наборах. Число различных ПФ n аргументов равно при n = 1, число различных ПФ равно 4, при n = 2 – 16, при n = 3 – 256, при n =4 – 65536, при n=5 – примерно 4,3´109. Ясно, что прямое изучение ПФ с помощью таблиц истинности возможно для небольшого числа аргументов.

Возьмем какую либо комбинационную схему (КС) (рис.2.1).

 

Рис.2.1. Комбинационная схема

Если значения ПФ отождествить с выходным сигналом КС, а аргументов - с входными сигналами, то ПФ будет описывать процесс преобразования входных сигналов в выходные, т. е.

y1 = f1(x1,x2,…,xn);

y2 = f2 (x1,x2,…,xn);

.

ym = fm (x1,x2,…,xn).

Любые сложные схемы ЭВМ строятся из простых схем, которые называют логическими элементамиÌ.

Логическим элементом называется электронная схема, реализующая элементарную ПФ, имеющая количество входов, равное числу аргументов ПФ и только один выход.

При составлении сложных схем используют два приема: последовательное соединение элементов и перестановку входов элементов. Последовательное соединение логических элементов показано на рис.2.2.

 

Рис.2.2. Последовательное соединение элементов

Последовательное соединение двух логических элементов позволяет получить функцию f3 трех аргументов. Подстановка в функцию вместо ее аргументов других функций называется суперпозицией.

Перестановка входов элементов показана на рис.2.3.

В общем случае функция f4(x1,x2,x3) отличается от функции f3(x1,x2,x3). Замена одних аргументов функции другими или изменение порядка записи аргументов называется подстановкой аргументов.

 

Рис.2.3. Перестановка входов элементов

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

.   

Переключательные функции одного и двух переменных

Рассмотрим некоторые ПФ одного и двух аргументов. В табл. 2.2 представлены все 4 функции одного аргумента.

Таблица 2.2

x	f0(x)	f1(x)	f2(x)	f3(x)
0	0	0	1	1
1	0	1	0	1

Функция f0 (x) равно нулю (константа нуля), f3(x) равна единице (константа единицы), функция f1(x) повторяет значение аргумента, т. е. f1(x)=x. Наиболее интересной и имеющей важное значение является функция f2(x), которая принимает значения, обратные значению аргумента - логическое отрицание или функция НЕ и обозначается как:

ù х (читается не х).

Все ПФ двух аргументов приведены в табл.2.3.

Таблица 2.3

х1	х2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Функции f0(x1,x2) и f15(x1,x2) не зависят от значений аргументов: f0(x1,x2)=0 и f15(x1,x2)=1. Функции f3(x1,x2), f5(x1, x2), f10(x1,x2) и f12(x1,x2) являются фактически функциями одного аргумента: