Астахова Е.В. Теоретические основы информатики

Подождите немного. Документ загружается.

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

ГОУ ВПО «Алтайский государственный технический университет

им. И. И. Ползунова»

Е. В. АСТАХОВА

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

ИНФОРМАТИКИ

Учебное пособие

Барнаул 2010

УДК 681.3

Астахова Е. В. Теоретические основы информатики: Учебное пособие/ Алт.

госуд. технич. ун-т им. И. И. Ползунова.- Барнаул, 2010.- 191 с.

В данном учебном пособии конспективно изложен лекционный материал

дисциплины ЕН.Ф.02 «Теоретические основы информатики». Пособие предназначено

для студентов, обучающихся по направлениям 231000 «Информатика и

вычислительная техника», 230100 «Программная инженерия», а также может быть

использовано студентами технических специальностей с углубленным изучением курса

информатики.

Рекомендовано заседанием

кафедры «Прикладная математика»

Протокол № 1 от 8.09.2010

ПРЕДИСЛОВИЕ

В современном мире деятельность людей зависит от уровня их

информированности и способности эффективно использовать полученные

знания. Чтобы свободно ориентироваться в потоках информации современный

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

закладывает дисциплина «Информатика». Информационная культура означает,

и умение целенаправленно работать с информацией, и профессиональное

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

передачи. Информация расценивается как стратегический ресурс общества, во

многом определяющий уровень развития государства.

Четкие границы информатики определить трудно, если вообще

возможно, поскольку она интегрирует знания из многих областей. Владение

основными понятиями из области информатики, информационных технологий

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

обществе. Информатика является дисциплиной не только практического плана,

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

компьютере, но и дисциплиной социальной, гуманитарной направленности,

способствующей формированию определенного мировоззрения.

Учебное пособие содержит относительно стабильные базовые

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

представления об информатике и ее роли в современной социально-

экономической жизни общества, о возможностях, способах и целях

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

Учиться сегодня надо основательно, но при этом быстро и экономно.

Чтобы стать впоследствии грамотным специалистом мало одних фактических

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

Познавательный труд нелегок, но нужно постараться сделать его максимально

продуктивным.

Обучение строится по схеме модульного изложения материала. Модуль

представляет собой логически завершенную часть материала, изучение

которого имеет определенную цель. Учебное пособие состоит из 8 модулей.

Учебный материал модуля состоит из базовой информации, комментариев и

дополнительного материала, отмеченных символом . Определения выделены

в тексте курсивом и отмечены значком

;

. Особо важные моменты и

практические задания помечены символом S.

Начиная работу с учебным пособием, ознакомьтесь с темой,

разделами, перечнем знаний, приведенными на титульном листе данного

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

самоконтроля самостоятельно или найти ответ в тексте модуля. Оцените

степень усвоения материала, опираясь на тезис, что специалист должен

уверенно ориентироваться в данном материале. Вернитесь к титульному листу

модуля и проверьте себя на усвоение перечисленных там знаний. Это то, что

Вы должны ЗНАТЬ, а, следовательно, тот материал учебного пособия, в

котором должны ОЧЕНЬ ХОРОШО РАЗОБРАТЬСЯ.

Необходимо помнить, что при начальном поверхностном ознакомлении

с любым изучаемым материалом запоминается 10-30% информации.

УСПЕХА!

Модуль 1

ВВЕДЕНИЕ В ИНФОРМАТИКУ

1 ВВЕДЕНИЕ ................................................................................................................................................................. 5

1.1 История развития вычислительной техники .............................................................................................. 5

1.2 Информационный рынок .................................................................................................................................. 6

1.3 Информационная культура ............................................................................................................................. 7

1.4 Информатика, как комплексная естественнонаучная дисциплина ........................................................... 7

1.5 Информация: свойства, качество .................................................................................................................. 8

1.6 Информация: адекватность, количество, мера........................................................................................... 9

1.7 Положения комбинаторики, используемые в измерении информации ..................................................... 12

1.8 Информационный процесс ............................................................................................................................. 13

1.9 Информационные системы ........................................................................................................................... 14

1.10 Методы получения и использования информации .................................................................................... 14

2 ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ ............................................................................................................................... 15

2.1 Основные понятия

алгебры логики ............................................................................................................. 15

2.2 Формализация высказываний ........................................................................................................................ 17

2.3 Логические схемы ........................................................................................................................................... 17

3 АЛГОРИТМЫ ........................................................................................................................................................... 18

3.1 Понятие алгоритма ...................................................................................................................................... 18

3.2 Запись алгоритмов ........................................................................................................................................ 19

3.3 Структуры алгоритмов................................................................................................................................ 20

4 СТРУКТУРЫ ДАННЫХ ............................................................................................................................................ 22

5 КОМАНДЫ И ПРОГРАММЫ ................................................................................................................................... 24

5.1 Машинные команды ........................................................................................................................................ 24

5.2 Свойства цифровых вычислительных машин ............................................................................................ 25

5.3 Трансляция и выполнение программ ............................................................................................................ 26

6 КЛАССЫ МОДЕЛЕЙ. МОДЕЛИРОВАНИЕ ............................................................................................................ 27

6.1 Классификация моделей ..............................................................................................................................

.. 27

6.2 Моделирование ............................................................................................................................................... 28

Вопросы для самоконтроля ................................................................................................................................... 29

ПОСЛЕ ИЗУЧЕНИЯ МОДУЛЯ ВЫ ДОЛЖНЫ ЗНАТЬ:

¾ Элементную и программную базы поколений ЭВМ.

¾ В чем проявляется информационная культура.

¾ Различие понятий «информация», «сообщение», «данные».

¾ Понятие и формы адекватности информации.

¾ По каким критериям можно измерять информацию.

¾ Единицы измерения информации.

¾ Способы формирования подмножеств, применяемые в комбинаторике.

¾ Сущность информационного процесса.

¾ Понятие информационной системы

¾ Разницу между утверждением, высказыванием и предикатом в алгебре логики.

¾ Элементарные функции и аксиомы алгебры логики.

¾ В чем заключается формализация высказываний алгебры логики.

¾ Основные логические элементы компьютера.

¾ Что такое алгоритм, его особенности и базовые элементы представления.

¾ Какие структуры используются для описания данных с различной организацией.

¾ Правила работы функций div и mod.

¾ Структуру машинных команд.

¾ Этапы решения задач на ЭВМ.

¾ Принципы программного управления.

¾ Этапы компьютерного моделирования.

¾ Классификационные признаки моделей и приемы моделирования.

РЕЗУЛЬТАТ:

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

¾ Создание общеобразовательной базы для успешного овладения такими дисциплинами как

«Структуры и алгоритмы обработки данных», «Программирование на языках высокого

уровня», «Базы данных».

¾ Закладка фундамента информационной культуры.

¾ Пополнение профессионального словарного запаса.

1 ВВЕДЕНИЕ

1.1 ИСТОРИЯ РАЗВИТИЯ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

В соответствии с элементной базой и уровнем развития программного

обеспечения (ПО) выделяют 4 периода в развитии вычислительной техники:

1. 1946-1955 гг. В середине 40-х были созданы первые ламповые вычислительные

устройства. Программирование осуществлялось на машинном языке. Системное

программное обеспечение составляли библиотеки математических и служебных

подпрограмм.

2. 1955-1965 гг. Компьютеры второго поколения на базе полупроводниковых

элементов. Произошло разделение персонала на программистов и операторов,

эксплуатационщиков и разработчиков вычислительных машин. Появились первые

алгоритмические языки и первые системные программы — компиляторы.

3. 1965-1980 гг. Рост объема обрабатываемой информации способствует

появлению первых систем управления базами данных. Появился новый способ

организации вычислительного процесса — мультипрограммирование и новый тип

операционных систем (ОС) — системы разделения времени.

4. С 1980 г. по настоящее время. Эра персональных компьютеров (ПК),

разработка "дружественного" программного обеспечения для пользователей-

непрофессионалов. Среди операционных систем доминируют MS DOS и UNIX.

Таблица 1. Технические характеристики поколений ЭВМ

Технические

характеристики

1-е поколение 2-е поколение 3-е поколение 4-е поколение

1946-1955 1955-1965 1965-

1970

1970-

1980

С 1980…

Элементная

база

Реле,

электронные

лампы

Полупроводни-

ковые

элементы

ИС БИС Сверхбольшие БИС

Быстродействие 1 мс 1 мкс 10 нс 1 нс < 1нс

Плотность

упаковки

(элемент/см

)

0,1 2-3 10-20 1000 >10 000

Режим работы Однопрограм-

мный

Пакетный Разделения

времени

Персональная/сетевая

работа

;

Мультипрограммирование — это способ организации вычислительного процесса,

при котором на одном процессоре попеременно выполняются несколько программ.

 Автором проекта первой автоматической вычислительной машины является Чарльз

Бэббидж (1791-1871) — английский математик. В начале 40-х годов двадцатого века Говард Айкен

построил машину Mark I, которую назвали «осуществленной мечтой Бэббиджа».

 Ноутбук — портативный персональный компьютер. Osborn-1 — первая в мире

общедоступная модель (ОП 64Кб, тактовая частота 4 МГц, монохромный дисплей 8,75х6,6 см)

Первый коммерческий ноутбук был выпущен в 1981 году.

 Лучшей отечественной ЭВМ 2-го поколения считается БЭСМ-6 (ОП 128 Кбайт, тактовая

частота 10 МГц, мультипрограммный режим).

1.2 ИНФОРМАЦИОННЫЙ РЫНОК

;

Информационный рынок — это комплексная структура, включающая в себя

правовой статус субъектов, вступающих в отношения при оказании информационных

услуг и их использовании.

Предмет продажи или обмена на информационном рынке: информационные

системы, информационные технологии, лицензии, патенты, товарные знаки, ноу-хау,

инженерно-технические услуги, информация.

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

• слияние компьютерных и телекоммуникационных систем и систем

обработки информации в одну модель;

• переход от бумажной к электронной технологии оказания услуг

(электронные платежи, электронная почта).

Рис. 1 Компоненты информационного рынка

 Поставщики информации на рынке информационных услуг именуются

информационными корпорациями, информационными агентствами, информационными службами,

информационными центрами.

Основные участники рынка информационных услуг:

• производители информации (организации, добывающие, публикующие,

обрабатывающие информацию);

• продавцы информации (вендоры);

• пользователи информации.

Отличительные особенности информационного продукта от других товаров:

• информация может быть использована многократно;

• информация морально устаревает со временем по мере снижения

актуальности предоставляемых ею знаний;

• информация адресна, т.е. рассчитана на разных потребителей;

• производство информации намного дороже последующего тиражирования.

 Основным средством ликвидации «цифрового неравенства» в Великобритании,

Италии, Швеции является государственная поддержка покупки населением ПК. Для развитых стран

уровнем прекращения господдержки является показатель 75-80 ПК на 100 семей.

Компоненты

информационного рынка

Электронная информация: деловая, юридическая,

массовая

пот

ебительская

на

чно-техническая

Сетевые коммуникации: электронная почта,

телекон

ен

ии

со

иальные сети

Программное обеспечение: коммерческие

программные продукты, программы с открытым кодом

Электронные сделки: системы банковских операций,

электронные торги, системы резервирования билетов и

мест в гостиницах, системы заказа товаров

1.3 ИНФОРМАЦИОННАЯ КУЛЬТУРА

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

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

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

средства и методы.

Информационная культура проявляется в умении:

• использовать различные технические устройства от телефона до

персонального компьютера;

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

до Internet и эффективно ее использовать;

• работать с различной информацией, грамотно используя компьютерную

информационную технологию и методы аналитической обработки.

 Информационная культура невозможна без знаний в области кибернетики,

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

1.4 ИНФОРМАТИКА, КАК КОМПЛЕКСНАЯ ЕСТЕСТВЕННОНАУЧНАЯ

ДИСЦИПЛИНА

 Термин «информатика» возник в 60-х гг. во Франции для названия области,

занимающейся автоматизированной обработкой информации с помощью ЭВМ.

 Термин «Informatique» (информатика) образован путем слияния слов information

(информация) и automatique (автоматика) — "информационная автоматика или

автоматизированная переработка информации". В англоязычных странах этому термину

соответствует синоним computer science (наука о компьютерной технике).

 В 1983 г. на сессии годичного собрания Академии наук СССР было принято решение

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

;

Информатика — это область человеческой деятельности, связанная с процессами

преобразования информации с помощью компьютеров и их взаимодействием со средой

применения.

В самом общем смысле под информатикой понимают фундаментальную

естественную науку, изучающую процессы передачи, накопления и обработки

информации.

Ядро информатики определяют три связанные между собой части:

алгоритмические (Brainware), программные (Software) и технические средства (Hardware).

;

Hardware — это устройства, имеющиеся в компьютере.

;

Software — это совокупность всех программ, используемых на компьютере.

;

Brainware — это то, что должен знать и уметь делать пользователь, чтобы

правильно решать задачи.

Главная функция информатики — разработка методов и средств преобразования

информации и их использование в организации технологического процесса переработки

информации.

Задачи информатики:

• исследование информационных процессов любой природы;

• разработка информационной техники;

• создание новейших технологий переработки информации;

• решение научных и инженерных проблем создания, внедрения и

эффективного использования компьютерной техники и технологии.

1.5 ИНФОРМАЦИЯ: СВОЙСТВА, КАЧЕСТВО

 По данным некоторых исследований, при переходе от атомного уровня к

молекулярному количество информации увеличивается в 10

раза. Количество информации,

относящейся к организму человека, примерно в 10

раз больше информации, содержащейся в

одноклеточном организме.

 Термин «информация» происходит от латинского informatio, что означает разъяснение,

осведомление, изложение. Информация есть отражение реального мира с помощью сведений

(сообщений).

;

Информация — это сведения об объектах и явлениях окружающей среды, их

параметрах, свойствах и состоянии, которые уменьшают имеющуюся о них степень

неопределенности, неполноты знаний.

;

Сообщение — это реальная форма представления информации в виде речи, текста,

изображения, цифровых данных, графиков, таблиц и т. п.

;

Данные — это сигналы, образы, рассматриваемые безотносительно к их смыслу.

;

Знание — это продукт накопления, систематизации данных, их осмысление с целью

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

Данные могут рассматриваться как признаки или записанные наблюдения,

которые по каким-то причинам не используются, а только хранятся. Если появляется

возможность использовать эти данные для уменьшения неопределенности о чем-либо, то

они превращаются в информацию. Таким образом, информацией являются используемые

данные.

 Кибернетика — наука об управлении, связи и переработке информации. Отец

кибернетики — Норберт Винер.

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

Кибернетика изучает процессы хранения, передачи, переработки и восприятия

информации, способы ее кодирования. Н. Винер рассматривал информацию как данные, не

различая процессы приема и передачи данных автоматами и живыми существами.

 Автомат преобразует данные в соответствии с тем, какой смысл (алгоритм) заложил в

него человек.

Информация обладает тремя основными свойствами:

1. Синтаксис определяет способ представления информации на носителе

(например, параметры шрифта документа, формат бумаги).

2. Семантика определяет смысл информации и может рассматриваться как

соглашение о правилах ее интерпретации (например, дорожные знаки).

3. Прагматика определяет влияние информации на поведение потребителя

(например, успешная сдача экзамена по вождению автомобиля после изучения правил

дорожного движения).

S Свойства информации:

• полнота, актуальность, значимость;

• адекватность, точность, корректность;

• избирательность, адресность, конфиденциальность;

• кодируемость, сжимаемость, компактность;

• помехоустойчивость.

1.5.1 Потребительские показатели качества информации

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

отражения свойств объекта.

Содержательность. Семантическая емкость информации, отношение количества

семантической информации (I

в сообщении к объему обрабатываемых данных (V

): С =

/ V

S Объем обработанных данных составил 4 Гбайта. Содержательность 1000 Мбайт

семантической информации равна

С = I

/ V

= 1000 / (4*1024) = 0,24.

S Коэффициент содержательности 800 Мбайт семантической информации равен 0,15.

Объем обработанных данных составил

= I

/ С = 800 / 0,15 / 1024 = 5,2 Гбайт.

S Объем обработанных данных составил 4 Гбайта. Коэффициент содержательности

равен 0,8. Количество семантической информации равно

= СV

= 0,8*4 = 3,2 Гбайта.

Коэффициент информативности. Это отношение количества синтаксической

информации (по Шеннону) к объему данных Y = I / V

Достаточность (полнота) информации означает, что она содержит минимальный,

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

Доступность. Обеспечение соответствующих процедур получения и

преобразования информации.

Актуальность. Степень ценности информации в момент ее использования.

Своевременность. Поступление информации не позже заранее назначенного

момента времени.

Точность. Степень близости получаемой информации к реальному состоянию

объекта, процесса, явления и т. п.

Достоверность. Отражение реально существующих объектов с необходимой

точностью.

Устойчивость. Способность информации реагировать на изменения исходных

данных без нарушения необходимой точности.

1.6 ИНФОРМАЦИЯ: АДЕКВАТНОСТЬ, КОЛИЧЕСТВО, МЕРА

;

Адекватность информации — это уровень соответствия создаваемого с

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

Синтаксическая адекватность отражает формально-структурные характеристики

информации и не затрагивает ее смыслового содержания. Учитываются тип носителя,

способ представления информации, скорость передачи и обработки, надежность и

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

 Информацию, рассматриваемую только с синтаксических позиций, обычно называют

данными.

Семантическая (смысловая) адекватность определяет степень соответствия

образа объекта и самого объекта; предполагает учет смыслового содержания информации.

Прагматическая (потребительская) адекватность отражает отношение

информации и ее потребителя. Учитывается ценность, полезность использования

информации при выработке потребителем решения для достижения своей цели.

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

предметных областях по-разному

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

;

Количество информации — числовая величина, характеризующая информацию по

разнообразию, сложности, упорядоченности, определенности и т.п.

Для измерения информации вводятся параметры: I — количество информации, V

— объем данных.

S Количество семантической информации оценивается по формуле I

= CV

где C —

коэффициент содержательности.

S За основную единицу измерения количества информации принят 1 бит.

Для оценки состояния системы, которая может принимать одно из n возможных

состояний, используется мера информации (события).

;

Мера — непрерывная действительная неотрицательная функция, определенная на

множестве событий.

1.6.1 Мера Р. Хартли

S Формула Хартли: H = k log

N, где k — коэффициент пропорциональности, а —

основание системы меры.

S Формула Хартли не работает в случае различных состояний системы.

Хартли предложил оценивать количество информации в зависимости от мощности

алфавита I = L log

h, где L — длина сообщения, h — мощность исходного алфавита

(количество символов в алфавите).

Пусть известны N состояний системы S, которые необходимо закодировать

двоичным кодом. Вопрос: какой длины должен быть код? Число всех различных

комбинаций из {0,1} длины d должно быть не меньше, чем N, т.е. 2

≥N (*).

Прологарифмируем это неравенство: log

≥ log

N ⇒ d ≥ log

N. Наименьшее решение

этого неравенства называется мерой разнообразия множества состояний системы и

задается формулой Хартли для двоичной системы счисления: H = log

N (бит).

Пример 1. Чтобы узнать положение точки в системе из 4-х клеток необходимо

задать два вопроса ("Левая или правая клетка?"). В итоге, узнав положение точки, мы

увеличиваем суммарную информацию о системе на 2 бита (I = log

4).

Пример 2. Имеются 200 монет. Известно, что одна из них — фальшивая и более

легкая по весу. Вопрос: за сколько взвешиваний можно выявить ее? Предположим, что на

весы кладется равное количество монет. Тогда получим 3 независимые возможности: а)

левая чашка ниже; б) правая чашка ниже; в) чашки уравновешены. Таким образом, каждое

взвешивание дает количество информации I = log

3. Следовательно, для определения

фальшивой монеты нужно сделать не менее k взвешиваний, где наименьшее k

удовлетворяет условию log

log

200. Отсюда, k 5.

Пример 3. Пусть имеется система из 4-х светодиодов, каждый из которых может

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

разнообразных состояний системы. По формуле (*) имеем 2

≥ N, т.е N должно быть не

больше 16.

Пример 4. В системе из 4-х светодиодов может быть включен только один.

Вопрос: на сколько увеличится суммарная информация о системе при обнаружении

включенного светодиода? Число состояний системы N = 4. Воспользуемся утверждением

Хартли, что для обнаружения произвольного элемента x

∈ X = {x

, x

, …, x

} необходимо

получить не менее log

n единиц информации. Тогда I = log

4 = 2 бита. Каждый вопрос по

поводу включенного светодиода дает количество информации (да/нет) I = log

2 = 1 бит.

Следовательно, необходимо задать два вопроса, например, «номер индикатора больше

двух?» (да/нет).

Пример 5. Определить количество информации, содержащейся в двоичной цифре.

Имеем исходный алфавит {0,1}. Следовательно, h = 2. Длина сообщения L = 1 (одна

двоичная цифра). Тогда I = 1*log

2 = 1 бит. Это аналитическое определение бита.

S На одну двоичную цифру приходится 1 бит информации.

S Определить количество информации, приходящейся на одну восьмеричную цифру.

(Ответ: 3)

S Доказать, что на одну шестнадцатеричную цифру приходится 4 бита информации.

1.6.2. Мера К. Шеннона

Шеннон предложил связать количество информации в сообщении с вероятностью

получения этого сообщения.

;

Вероятность — это количественная характеристика одного из исходов

некоторого опыта, известная до его проведения. Измеряется в пределах от 0 до 1.

S Сумма вероятностей всех исходов опыта равна 1.

Теория Шеннона разработана как теория передачи данных по каналам связи, а

мера Шеннона — как мера количества данных и не отражает семантического смысла.

Формула Шеннона дает оценку информации независимо от ее смысла: