Общая характеристика процессов сбора, передачи и обработки информации

Самарский государственный архитектурно-строительный университет

 

О.В. Прохорова

 

ИНФОРМАТИКА

 

Курс лекций

 

Самара 2012

 

Оглавление

1. Информация, ее представление и измерение. 4

2. Общая характеристика процессов сбора, передачи и обработки информации.. 15

2.1. Системы счисления и действия в них. 15

2.2. Общая характеристика процессов передачи информации.. 19

2.3. Кодирование и шифрование информации.. 23

2.4. Компьютерные вирусы.. 32

3. Модели решения функциональных и вычислительных задач. 35

3.1. Модели и моделирование. 35

3.2. Основные свойства модели и моделирования. 41

3.3. Классификация видов моделирования. 44

3.4. Компьютерное моделирование. 46

3.5. Функции алгебры логики.. 48

3.6. Булева алгебра. Функциональная полнота. 51

3.7. Минимизация функций алгебры логики.. 53

4. Программные средства реализации информационных процессов. 58

5. Технические средства реализации информационных процессов. 61

6. Алгоритмизация и программирование. 68

7. Архитектура ЭВМ. Локальные и глобальные сети. 80

7.1. Архитектура ЭВМ.. 80

7.2. Cеть передачи данных. 84

7.3. Аппаратные средства сети.. 85

7.4. Локальная вычислительная сеть. 93

7.5. Топология сети.. 96

7.6. Глобальная вычислительная сеть. 97

7.7. Сетевая модель OSI 99

7.8. Стек протоколов TCP / IP.. 100

8. Программное обеспечение. 106

8.1. Классификация и основные характеристики ПО.. 106

8.2. Структура технического обеспечения. 107

8.3.Состав операционной системы и ее основные функции.. 108

9. Технология программирования. 114

9.1. Организация данных в ЭВМ.. 114

9.2. Стеки и очереди.. 118

9.3. Графы.. 120

9.4. Деревья. 123

10. Базы данных. 126

10.1. Основные понятия. 126

10.2. Модели данных в СУБД.. 128

10.3. Основные понятия реляционной модели.. 135

11. Объектно – ориентированное программирование. 137

11.1. Основные положения ООП.. 137

11.2. Инкапсуляция. 138

11.3. Полиморфизм.. 139

11.5. Наследование. 141

Литература. 144

 

Информация, ее представление и измерение

Информатика – это наука об информационных процессах, о моделях, об алгоритмах и алгоритмизации, о программах и программировании, об исполнителях… Можно отметить три основные ветви информатики: теоретическую, практическую и… Теоретическая информатика (brainware, "мозговое" обеспечение) изучает теоретические проблемы информационных…

X+ 20 = y.

Отсюда получаем систему двух алгебраических уравнений:

Решая эту систему, окончательно получаем, x = –76,5, у = –56,5.

Для измерения информации используются различные подходы и методы, например, с использованием меры информации по Р. Хартли и К. Шеннону.

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

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

Рассмотрим различные меры информации. Сначала рассмотри меру Р. Хартли.

Пусть известны N состояний системы S (N - число опытов с различными, равновозможными, последовательными состояниями системы). Если каждое состояние системы закодировать двоичными кодами, то длину кода dнеобходимо выбрать так, чтобы число всех различных комбинаций было бы не меньше, чем N:

Логарифмируя это неравенство, можно записать:

Наименьшее решение этого неравенства или мера разнообразия множества состояний системы и задается формулой Р. Хартли:

H = log₂N (бит).

Если во множестве X = {x₁, x₂, ..., x_n} искать произвольный элемент, то для его нахождения (по Хартли) необходимо иметь не менее log₂n (единиц) информации.

Уменьшение Н говорит об уменьшении разнообразия состояний N системы.

Увеличение Н говорит об увеличении разнообразия состояний N системы.

Мера Хартли подходит лишь для идеальных, абстрактных систем, так как в реальных системах состояния системы не равновероятны.

Для таких систем используют меру К. Шеннона.

Мера Шеннона оценивает информацию отвлеченно от ее смысла:

где n – число состояний системы; р_i – вероятность (относительная частота) перехода системы в i-е состояние (сумма всех p_i должна равняться 1).

Если все состояния рассматриваемой системы равно возможны, равновероятны, то есть рi = 1/n , то из формулы Шеннона можно получить (как частный случай) формулу Хартли:

I = log₂n ,

производя нехитрые алгебраические действия:

Пример. Если положение точки в системе из 10 клеток известно, например если точка находится только в одной - во второй клетке, то есть

р_i = 0, i = 1, 3, 4, …, 10, р₂ = 1 ,

то тогда получаем количество информации, равное нулю:

I = log₂1 = 0 .

Введем величину:

f_i = –nlog₂p_i.

В термодинамике известен так называемый коэффициент Больцмана

k = 1.38 * 10^–16 (эрг/град)

и выражение (формула Больцмана) для энтропии или меры хаоса в термодинамической системе:

Сравнивая выражения для I и S, можно заключить, что величину I можно понимать как энтропию из-за нехватки информации в системе (о системе).

Основное функциональное соотношение между энтропией и информацией имеет вид:

I + S(log₂e) / k = const.

Из этой формулы следуют важные выводы:

1. Увеличение меры Шеннона свидетельствует об уменьшении энтропии (увеличении порядка) системы;

2. Уменьшение меры Шеннона свидетельствует об увеличении энтропии (увеличении беспорядка) системы.

Положительная сторона формулы Шеннона – ее отвлеченность от смысла информации. Кроме того, в отличие от формулы Хартли, она учитывает различие состояний, что делает ее пригодной для практических вычислений. Основная отрицательная сторона формулы Шеннона – она не распознает различные состояния системы с одинаковой вероятностью.

Методы получения информации можно разбить на три большие группы.

1. Эмпирические методы или методы получения эмпирических данных.

2. Теоретические методы или методы построения различных теорий.

3. Эмпирико-теоретические методы (смешанные) или методы построения теорий на основе полученных эмпирических данных об объекте, процессе, явлении.

Охарактеризуем кратко эмпирические методы.

1. Наблюдение – сбор первичной информации об объекте, процессе, явлении.

2. Сравнение – обнаружение и соотнесение общего и различного.

3. Измерение – поиск с помощью измерительных приборов эмпирических фактов.

4. Эксперимент – преобразование, рассмотрение объекта, процесса, явления с целью выявления каких-то новых свойств.

Кроме классических форм их реализации, в последнее время используются опрос, интервью, тестирование и другие.

Охарактеризуем кратко эмпирико-теоретические методы получения информации:

1. Абстрагирование – выделение наиболее важных для исследования свойств, сторон исследуемого объекта, процесса, явления и игнорирование несущественных и второстепенных.

2. Анализ – разъединение целого на части с целью выявления их связей.

3. Декомпозиция – разъединение целого на части с сохранением их связей с окружением.

4. Синтез – соединение частей в целое с целью выявления их взаимосвязей.

5. Композиция — соединение частей целого с сохранением их взаимосвязей с окружением.

6. Индукция – получение знания о целом по знаниям о частях.

7. Дедукция – получение знания о частях по знаниям о целом.

8. Эвристики, использование эвристических процедур – получение знания о целом по знаниям о частях и по наблюдениям, опыту, интуиции, предвидению.

9. Моделирование (простое моделирование), использование приборов – получение знания о целом или о его частях с помощью модели или приборов.

10. Логический метод– поиск знаний путем воспроизведения частей, связей или элементов в мышлении.

11. Макетирование– получение информации по макету, представлению частей в упрощенном, но целостном виде.

12. Актуализация– получение информации с помощью перевода целого или его частей (а следовательно, и целого) из статического состояния в динамическое состояние.

13. Визуализация– получение информации с помощью наглядного или визуального представления состояний объекта, процесса, явления.

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

Информационная система – это система, в которой элементы, структура, цель, ресурсы рассматриваются на информационном уровне.

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

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

Общая характеристика процессов сбора, передачи и обработки информации

Системы счисления и действия в них

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

Общая характеристика процессов передачи информации

Пространство сообщений. Коды обнаружения и исправления ошибок Введем пространство сообщений в виде E(n, Um), где Um - алфавит, m - размерность алфавита, n - число символов из…

Кодирование и шифрование информации

Одна из наиболее важных задач информатизации процессов – кодирование сообщений и шифрование информации. Вопросами защиты и скрытия информации занимается наука кpиптология.… Цели этих направлений пpотивоположны. Кpиптогpафия занимается построением и исследованием математических методов…

При кодировании нет такого секретного ключа, так как кодирование ставит целью лишь более сжатое, компактное представление сообщения.

  Традиционные симметричные криптосистемы  

Компьютерные вирусы

По мере появления новых компьютерных вирусов разработчики антивирусных программ пишут вакцину против нее – так называемую антивирусную программу,… Пример. Одну из самых популярных антивирусных программ AIDSTESTавтор (Д.… Вирусы бывают следующих основных видов: загрузочные – заражающие стартовые секторы дисков, где находится самая…

Модели решения функциональных и вычислительных задач

Модели и моделирование

По уровню, "глубине" моделирования модели бывают: · эмпирические - на основе эмпирических фактов (опытов); · теоретические - на основе математических описаний;

Основные свойства модели и моделирования

Как правило, модель включает в себя: объект О, субъект А (не обязательно) , задачу Z, ресурсы B, среду моделирования С. Модель можно представить формально в виде: М = < O, А, Z, B, C >. Основные свойства любой модели: целенаправленность - модель всегда отображает некоторую систему, т.е. имеет цель…

Классификация видов моделирования

Рис. 3.3. Классификация видов моделирования

Прифизическом моделированиииспользуется сама система, либо подобная ей в виде макета, например, летательный аппарат в аэродинамической трубе.

Математическое моделированиеесть процесс установления соответствия реальной системе S математической модели M и исследование этой модели, позволяющее получить характеристики реальной системы.

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

Аналитическая модель может быть исследована методами:

· аналитическими (устанавливаются явные зависимости, получаются, в основном, аналитические решения);

· численными (получаются приближенные решения);

Компьютерное математическое моделированиеформулируется в виде алгоритма (программы для ЭВМ), что позволяет проводить над моделью вычислительные эксперименты.

Численное моделированиеиспользует методы вычислительной математики.

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

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

Применение математического моделирования позволяет исследовать объекты, реальные эксперименты над которыми затруднены или невозможны.

Экономический эффект при математическом моделировании состоит в том, что затраты на проектирование систем в среднем сокращаются в 50 раз.

Компьютерное моделирование

Компьютерное моделирование от постановки задачи до получения результатов проходит следующие этапы: 1. Постановка задачи: · формулировка задачи;

Функции алгебры логики

Определение.Функцией алгебры логики называется функция, дающая однозначное отображение X в Y. Определение.Если две функции алгебры логики f1(x1... xn) и f2( x1... xn) принимают на всех наборах значений аргументов одинаковые значения, то их называют равными.

Коммутативность

x₁ & x₂ = x₂ & x_1.

 

x₁ v x₂ = x₂ v x_1.

 

Ассоциативность

x₁ v (x₂ v x₃) = (x₁ v x₂) v x_3.

 

x₁ & (x₂ & x₃) = (x₁ & x₂) & x_3.

Дистрибутивность

x1 v (x2 & x3) = (x1 v x2) & ( x1 v x3 ). Отметим также важные соотношения:  

Булева алгебра. Функциональная полнота

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

Ø называется булевой алгеброй. Будем обозначать ее символом S_B.

Рассмотрим свойства булевой алгебры.

Замкнутость

 

для " A и B Î S_B

A v B Î S_B

A & B Î S_B

 

Коммутативность

 

A & B = B & A

A v B = B v A

 

3. Ассоциативность

 

A v ( B v C) = (A v B) v C

 

Дистрибутивность

 

A & ( B v C) = (A & B) v (A & C)

A v ( B & C) = (A v B) & (A v C)

 

Идемпотентность

A v A = A & A = A.   6.Булева алгебра содержит элементы 0,1 , такие что для всякого

Закон поглощения

 

A & (A v B) = A v A & B = A.

 

 

Закон Де Моргана

 

 

Минимизация функций алгебры логики

  Работа конечного автомата может быть полностью описана с помощью следующей…  

...

y_m= f_m (x₁ ... x_n )

 

Здесь Pi = ( X1, X2, ...,Xn ); Qj = ( y1, y2, ...,ym ) - соответственно входное и выходное слово. Работа автомата может быть задана либо в виде конечных таблиц, либо в виде аналитической записи функций f_{i .}

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

- метод вынесения за скобки;

- метод неопределенных коэффициентов;

- метод с использованием карт Карно;

- метод Мак - Класки;

- метод Блэка.

Рассмотрим метод минимизации совершенной дизъюнктивной нормальной формы (СДНФ) с помощью карт Карно. Карта Карно - это диаграмма, состоящая из 2ⁿ квадратов, где n - число переменных. Клетка карты - одна из возможных конъюнкций, входящих в СДНФ. Минимизация на основе карт Карно осуществляется путем локализации на карте прямоугольных областей из числа клеток кратного 2.

Для работы с картой необходимо по таблице истинности составить СДНФ, затем для каждой элементарной конъюнкции проставить 1 в соответствующие клетки карты. Затем единицы объединяются таким образом, чтобы минимизировалось число логических сложений, умножений или отрицаний, что важно для экономного конструирования ЭВМ.

Рассмотрим карты Карно.

 

 

Для двух переменных: Для трех переменных:

a a

c

 

b

 

 

b

Для четырех переменных:

 

a

c

cd

d

b

Пример. Для логической функции заданной таблицей

 

x1	x2	x3	f

 

построить карту Карно и на ее основе минимизировать функцию.

 

Решение. Построим карту согласно описанным выше правилам.

x₁

1 1 f = x1 v x2 & x3

x_{2 1 1 1}

x₃

 

Рассмотрим пример представления простейшей функции картой Карно

a

c 1 1

c 1 1d

f = b

1 1d

1 1

b

 

 

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

 

f1 = V2 & V4 v V3 & ØV1 & ØV2 v ØV3 & ØV4 & V1.

V1

V2

V3

V4

& & & & &

 

& &

&

&

1

F1

Программные средства реализации информационных процессов

n число команд в тексте программы; n объем промежуточной памяти; n время вычисления программы, которое характеризуется двумя величинами:

Технические средства реализации информационных процессов

Логический вентиль (вентиль) – это своего рода элемент, из которого состоят электронные узлы ЭВМ. Он работает по принципу крана, открывая или… Логические схемы предназначены для реализации различных функций алгебры логики… Логические функции отрицания, дизъюнкции и конъюнкции реализуют логические схемы, называемые инвертором, дизъюнктором…

Алгоритмизация и программирование

"Алгоритм" является базовым основополагающим понятием информатики, а алгоритмизация (программирование) – основным разделом курса… Современное значение слова алгоритм во многом аналогично таким понятиям как… Алгоритм — это не просто набор конечного числа правил, задающих последовательность выполнения операций для решения…