Вучебниках информатики в общем виде информацион­ный процесс

Вид материала

Учебник

Содержание Получение новой информации. 1. Неизмеримость информации в быту 2. Вероятностный, или содержательный подход Сообщение, уменьшающее неопределенность знания в 2 раза, несет один бит информации. 3. Алфавитный подход к измерению информации. Переход к более крупным единицам измерения Понятие алгоритма Формализация понятия алгоритма. Определение 2 (Колмогоров). Определение 3 (Марков). Свойства алгоритмов Точность (определенность). Универсальность (массовость). Автоматическое исполнение алгоритма Словесное описание Описание на алгоритмическом языке Описание в графической форме в виде блок-схемы. Основные блоки Алгоритм линейной структуры Алгоритм разветвленной структуры ... Полное содержание

Подобный материал:

• 3. Процесс восприятия и управление впечатлением, 191.28kb.
• Понятие о программах и программировании, 592.28kb.
• Поволжская Государственная Академия Телекоммуникаций и Информатики задания и методические, 262.31kb.
• Общеобразовательный стандарт по информатике является нормативным документом, определяющим, 237.91kb.
• Финансы предприятий, 2102.05kb.
• Исходные технические данные, 34.3kb.
• Тема: Личность в системе современного, 42.1kb.
•     После то­го как я на­пи­сал «Счас­т­лив по соб­с­т­вен­но­му же­ла­нию», как-то, 1995.16kb.
• Компьютерная технология обучения и опережающая подготовка преподавателей, 49.99kb.
• Активизация познавательной деятельности школьников на уроках информатики, 32.08kb.

Примерные ответы на теоретические вопросы билетов по информатике.


Билет № 1

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

С развитием теории информации, кибернетики, информа­тики как науки понятие «информация» (от латинского infor-matio — сведения, разъяснения), наряду с понятиями «веще­ство», «энергия», «пространство» и «время» легло в основу современной научной картины мира. В то же время однознач­ного определения этого понятия пока не существует.

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

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

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

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

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

Получение новой по содержанию информации из исход­ной информации возможно путем как математических вычислений, так и логических рассуждений.

• Структурирование означает изменение формы инфор­мации без изменения ее содержания. Если процесс об­работки информации связан с тем, что ее содержание не изменяется, а изменяется только форма представле­ния, то происходит упорядочивание, систематизация, или структурирование информации.

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

Процесс передачи информации представляет собой со­здание копии информации на расстоянии от исходного мес­та хранения. В процессе передачи информации обязательно участвуют источник и приемник информации. Между ними действует канал связи. В процессе передачи информация может теряться или искажаться — случайно или намерен­но. На устранение этого могут быть направлены методы за­щиты при передаче информации. Передача информации в социальных, биологических и технических системах с точ­ки зрения информатики осуществляется по общей схеме: источник-канал-приемник. Различие в том, что в таких сис­темах понимают под информацией. «В социальных науках под информацией понимают сведения, данные понятия, от­раженные в нашем сознании и изменяющие наши представ­ления о реальном мире. Эту информацию, передающуюся в человеческом обществе и участвующую в формировании об­щественного сознания, называют социальной информацией. Инженеры, биологи, генетики, психологи отождествляют информацию с теми сигналами, импульсами, кодами, кото­рые наблюдают в технических и биологических системах. Содержание принимаемых и обрабатываемых сигналов ин­женера не интересует» [3], а генетиков и биологов может ин­тересовать.

К процессу хранения информации можно отнести: • Размещение (накопление). Информация, полученная в результате поиска, размещается на каком-либо носите­ле информации, происходит ее накопление. Процесс, в результате которого информация оказывается на носи­теле в виде, пригодном для последующего извлечения, называется размещением. Таким образом, мы создаем некоторый информационный ресурс. Основное отли­чие информационных ресурсов от других видов ресур­сов состоит в том, что информация после их использо­вания не исчезает. Поэтому важнейшей задачей является создание таких хранилищ информации, кото­рые совмещали бы процессы защиты, структурирова­ния, поиска, извлечения, передачи в автоматическом режиме для увеличения доступности информации.

• Коррекцию. Информация в хранилищах нуждается в коррекции по различным причинам, таким как: меха­нические повреждения или изменения свойств носите­ля, устаревание информации, модернизация структу­ры для оптимизации доступа к информации и пр. С этой целью выполняется процесс коррекции информа­ции.

• Доступ. Организация оптимального доступа к различ­ной по ценности информации с использованием проце­дур защиты от несанкционированного доступа может быть отнесена к процессу хранения.


Билет №2

Понятие о кодировании информации. Выбор способа представления информации в соответствии с поставлен­ной задачей. Универсальность дискретного (цифрового) представления информации. Двоичное кодирование.

Информация никогда не появляется в «чистом виде», она всегда как-то представлена, в каком-либо формализованном (закодированном) виде. Одна и та же информация может быть представлена различными способами. От того, как представлена информация, зависит очень многое, от воз­можной интерпретации до возможности ее технической об­работки. Так что в практических задачах важно выбрать тот способ представления информации, который наиболее удо­бен и адекватен решаемой задаче.

В настоящее время достаточно распространен процесс ко­дирования, т. е. преобразование информации из одной зна­ковой формы в другую, удобную для ее обработки, хранения или передачи. Используемый для кодирования конечный набор знаков называют алфавитом. Кодирование осуществ­ляется по принятым правилам. Правило кодирования назы­вается кодом (от французского code — кодекс, свод зако­нов). Длина кода — количество знаков алфавита, используе­мое для кодирования.

Многие годы человечество работало с информацией, преж­де чем был изобретен компьютер. С появлением компьютера стало возможным автоматизировать процессы обработки, передачи и хранения информации. При кодировании инфор­мации для технических устройств удобно использовать ал­фавиты, состоящие всего из двух знаков. Такие алфавиты называют двоичными. Чем меньше знаков в алфавите, тем проще должна быть устроена «машина» для распознавания (дешифровки) информационного сообщения. Однако чем ме­ньше знаков в алфавите, тем большее их количество требу­ется для кодирования, следовательно, тем больше длина кода. Легко рассчитать количество М элементарных сообще­ний, которые можно закодировать, используя код постоян­ной длины п и алфавит из R знаков: М = Rⁿ. Длину кода рассчитывают по формуле п = [log_RM + 1]. Если мы исполь­зуем двоичный алфавит, то М = 2^п.

При конструировании компьютеров был выбран двоичный алфавит {0, 1}, что позволило использовать достаточно про­стые устройства для представления и автоматического распо­знавания программ и данных. Именно простота сделала этот принцип кодирования таким распространенным. Наряду с этим свойством двоичное кодирование обеспечивает удобство физической реализации, универсальность представления лю­бого вида информации, уменьшение избыточности сообще­ния, обеспечение защиты от случайных искажений или не­желательного доступа. Наиболее распространены кодировки компьютерных символов: ASCII, Winl251, КОИ-8.


Билет № 3

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

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

Чтобы измерить что-либо, необходимо ввести единицу из­мерения. Минимальная единица измерения информации — бит. Смысл данной единицы также различен в рамках раз­ных подходов к измерению информации. Выделяют три подхода.

1. Неизмеримость информации в быту Если в сообщении содержалось для вас что-то новое, то оно информативно. Но для другого человека в этом же сооб­щении нет ничего нового, для него оно не информативно. Это происходит оттого, что до получения данного сообщения знания каждого из нас были различны. Фактор субъектив­ного восприятия сообщения делает невозможным количест­венную оценку информации в сообщении, т. е. если рассмат­ривать количество полученной информации с точки зрения новизны для получателя, то измерить её невозможно.

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

Сообщение, уменьшающее неопределенность знания в 2 раза, несет один бит информации.

Например: при подбрасывании монеты может выпасть либо «орел», либо «решка». Это два возможных события. Они равновероятны. Сообщение о том, что произошло одно из двух равновероятных событий (например, выпала «реш­ка»), уменьшает неопределенность нашего знания (перед броском монеты) в два раза.

Математики рассматривают идеальный вариант, что воз­можные события равновероятны. Если даже события нерав­новероятны, то возможен подсчет вероятности выпадения каждого события.

Под неопределенностью знания здесь понимают количе­ство возможных событий, их может быть больше, чем два.

Например, количество оценок, которые может получить студент на экзамене, равно четырем. Сколько информации содержится в сообщении о том, что он получил «4»? Рассуж­дая, с опорой на приведенное выше определение, можем сказать, что если сообщение об одном из двух возможных событий несет 1 бит информации, то выбор одного из четы­рех возможных событий несет 2 бита информации. Можно прийти к такому выводу, пользуясь методом половинного деления. Сколько вопросов необходимо задать, чтобы выяс­нить необходимое, столько битов и содержит сообщение. Во­просы должны быть сформулированы так, чтобы на них можно было ответить «да» или «нет», тогда каждый из них будет уменьшать количество возможных событий в 2 раза.

Очевидна связь количества возможных равновероятных событий и количества информации:



Заполним по формуле таблицу:

Количество битов	0	1	2	3	4	5	6	7	8	9	10
Количество событий	1	2	4	8	16	32	64	128	256	512	1024

Это формула Р. Хартли. Если р = 1/N — вероятность на­ступления каждого из N равновероятных событий, тогда формула Хартли записыватся так:



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

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

Алфавит любого языка включает в себя конечный набор символов. Исходя из вероятностного подхода к определению количества информации, появление символов алфавита в тексте можно рассматривать как различные возможные со­бытия. Количество таких событий (символов) N называют мощностью алфавита. Тогда количество информации i, ко­торое несет каждый из JV символов, согласно вероятностно­му подходу определяется из формулы: N=2ⁱ

Количество символов в тексте из k символов: I=k*i

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

Переход к более крупным единицам измерения

Ограничения на максимальную мощность алфавита не су­ществует, но есть алфавит, который можно считать доста­точным (на современном этапе) для работы с информацией, как для человека, так и для технических устройств. Он включает в себя: латинский алфавит, алфавит языка стра­ны, числа, спецсимволы — всего около 200 знаков. По при­веденной выше таблице можно сделать вывод, что 7 битов информации недостаточно, требуется 8 битов, чтобы закоди­ровать любой символ такого алфавита, 256 = 2⁸. 8 битов об­разуют 1 байт. То есть для кодирования символа компьютер­ного алфавита используется 1 байт. Укрупнение единиц из­мерения информации аналогично применяемому в физике — используют приставки «кило», «мега», «гига». При этом следует помнить, что основание не 10, а 2. 1 кило­байт (Кб) — это 2¹⁰ = 1024 байтов, 1 мегабайт (Мб) = = 2¹⁰ Кб = 2²⁰ байтов и т. д.

Умение оценивать количество информации в сообще­нии поможет определить скорость информационного пото­ка по каналам связи. Максимальную скорость передачи информации по каналу связи называют пропускной спо­собностью канала связи. Самым совершенным средством связи на сегодня являются оптические световоды. Инфор­мация передается в виде световых импульсов, посылае­мых лазерным излучателем. У этих средств связи высокая помехоустойчивость и пропускная способность более 100 Мбит/с.


Билет № 4

Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое исполнение алгоритма. Основные алгоритмические структуры.

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

Исторический обзор. Первым дошедшим до нас алгорит­мом в его интуитивном понимании — конечной последователъности элементарных действий, решающих поставлен­ную задачу, — считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего де­лителя двух чисел (алгоритм Евклида). Вплоть до начала XX века само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм Евклида». Для описания пошагового решения других математических задач использовалось сло­во «метод».

Слово «алгоритм», «algorithm» происходит от имени вы­дающегося ученого IX века Мухаммада ибн Муса ал-Хорез-ми (в переводе с арабского Мухаммад, сын Мусы из Хорез­ма). По латинскому переводу его труда (XII век) Западная Европа познакомилась с десятичной позиционной системой счисления и правилами (algorismi) выполнения в ней ариф­метических действий.

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

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

Варианты словесного определения алгоритма, принадле­жащие российским ученым-математикам А. Н. Колмогоро­ву и А. А. Маркову:

Определение 2 (Колмогоров). Алгоритм — это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

Определение 3 (Марков). Алгоритм — это точное пред­писание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

Свойства алгоритмов

• Дискретность. Алгоритм состоит из последовательных команд, только выполнив одну команду, исполнитель может приступить к выполнению следующей. То есть структура алгоритма является дискретной (прерыв­ной).

• Конечность. Алгоритм содержит конечное количество элементарных выполнимых предписаний, т. е. удовлет­воряет требованию конечности записи. Исполнитель алгоритма должен выполнять конечное количество ша­гов при решении задачи, т. е. алгоритм удовлетворяет требованию конечности действий.

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

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

• Универсальность (массовость). Алгоритм должен быть единым для всех допустимых исходных данных. Разра­ботка алгоритма — процесс творческий, но требующий значительных затрат времени и умственных усилий, поэтому желательно, чтобы он обеспечивал решение за­дач данного типа. Это свойство не является обязатель­ным; не менее важными являются алгоритмы уникаль­ные, разработанные для решения одной задачи.

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


Автоматическое исполнение алгоритма

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

Примером исполнителя, автоматически выполняющего различные алгоритмы, является компьютер. Рассмотрим за­пись на жесткий диск компьютера телевизионной передачи с помощью ТВ-тюнера. Указав в расписании время начала и окончания записи, поставив «флажок» возле позиции «Вы­ключить компьютер после записи», пользователь может быть уверен, что передача будет записана и компьютер будет выключен. Всю заданную работу выполнит компьютер по разработанному ранее алгоритму, не внося никаких измене­ний (другая передача, другое время, невыключение компью­тера).

Способы описания алгоритмов

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

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

Описание в графической форме в виде блок-схемы.

В схеме алгоритма каждому типу действий (ввод исходных данных, вычисление, проверка условия, управление цик­лом, вывод результатов, окончание) соответствует своя гео­метрическая фигура — блок. Блоки соединяются линиями со стрелками, указывающими последовательность действий. Форма блоков установлена ГОСТом. Внутри блока записыва­ется содержание соответствующего действия. Совокупность блоков образует блок-схему алгоритма. (В Microsoft Office можно использовать готовые шаблоны блоков.)

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



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

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

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

Алгоритм линейной структуры — алгоритм, в котором предписываемые действия выполняются последовательно: Оператор1 — Оператор2 — ... — Операторе. Такой порядок выполнения действий называется естественным.

Алгоритм разветвленной структуры — алгоритм, в кото­ром предусмотрено разветвление выполняемой последова­тельности действий в зависимости от результата проверки какого-то условия. Условие — это некоторое логическое вы­ражение. Если условие (логическое выражение) принимает значение «истина», то выполняется Оператор 1, в противном случае — значение «ложь» — выполняется Оператор2. Оператор1 и Оператор2 могут представлять собой группу опера­торов, а также могут быть условными операторами. В слу­чае отсутствия Оператора2 получаем конструкцию с непол­ным ветвлением.



Алгоритм циклической структуры (цикл с повторени­ем) — алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий. Эту последовательность действий называют телом цикла.

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

Циклическую структуру реализуют операторы трех типов.

Оператор FOR...DO действует следующим образом. Тело цикла выполняется для каждого значения параметра цикла / от его начального Ml до конечного значения М2 включи­тельно. J, Ml, M2 — чаще всего переменные целого типа. Шаг изменения переменной цикла / равен +1 или -1.

Оператор WHILE...DO действует следующим образом. Каж­дый раз предварительно проверяется значение логического выражения. Пока оно истинно, выполняется тело цикла. Как только оно становится ложным, происходит выход за пределы цикла. Если с самого начала значение логического выражения является ложным, то тело цикла не выполняется ни разу.

Оператор REPEAT...UNTIL действует следующим образом. Тело цикла выполняется, пока значение логического выраже­ния ложно. Тело цикла выполняется как минимум один раз.



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