Информационные технологии

Введение

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

Роль и значение информационных революций

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

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

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

Третья (конец XIX в.) обусловлена изобретением электричества, благодаря которому появились телеграф, телефон, радио, позволяющие оперативно передавать и накапливать информацию в любом объеме.

Четвертая (70-е гг. XX в.) связана с изобретением микропроцессорной технологии и появлением персонального компьютера. На микропроцессорах и интегральных схемах создаются компьютеры, компьютерные сети, системы передачи данных (информационные коммуникации). Этот период характеризуют три фундаментальные инновации: переход от механических и электрических средств преобразования информации к электронным; миниатюризация всех узлов, устройств, приборов, машин; создание программно-управляемых устройств и процессов.

Смена поколений ЭВМ

1-е поколение (начало 50-х гг.). Элементная база -- электронные лампы. ЭВМ отличались большими габаритами, большим потреблением энергии, малым быстродействием, низкой надежностью, программированием в кодах. 2-е поколение (с конца 50-х гг.). Элементная база -- полупроводниковые элементы. Улучшились по сравнению с ЭВМ предыдущего поколения все технические характеристики. Для программирования используются алгоритмические языки. 3-е поколение (начало 60-х гг.). Элементная база -- интегральные схемы, многослойный печатный монтаж. Резкое снижение габаритов ЭВМ, повышение их надежности, увеличение производительности. Доступ с удаленных терминалов. 4-е поколение (с середины 70-х гг.). Элементная база -- микропроцессоры, большие интегральные схемы. Улучшились технические характеристики. Массовый выпуск персональных компьютеров. Направления развития: мощные многопроцессорные вы­числительные системы с высокой производительностью, создание дешевых микроЭВМ. 5-е поколение (с середины 80-х гг.). Началась разработка интеллектуальных компьютеров, пока не увенчавшаяся успехом. Внедрение во все сферы компьютерных сетей и их объединение, использование распределенной обработки данных, повсеместное применение компьютерных информационных технологий. Последняя информационная революция выдвигает на первый план новую отрасль -- информационную индустрию, связанную с производством технических средств, методов, технологий для производства новых знаний. Важнейшими составляющими информационной индустрии становятся все виды информационных технологии, особенно телекоммуникации. Современная информационная технология опирается на достижения в области компьютерной техники и средств связи.

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

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

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

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

История развития

Первая машина, способная автоматически выполнять четыре арифметических действия появилась в XVII веке. В 1623 г. В.Шикард изобрел машину, способную не только суммировать и вычитать числа, но и частично перемножать и делить их.

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

В 1671г. немецкий философ и математик Г.Лейбниц создал свою счетную машину, известную как “зубчатое колесо Лейбница”.

В 19 веке английский математик Ч.Бэббидж разработал несколько проектов вычислительных механических устройств, самым известным из них является “аналитическая машина” Бэббиджа. Эта машина представляла собой программируемое автоматическое вычислительное устройство. Программы кодировались и переносились на перфокарты. эту идею Бэббидж позаимствовал у французского изобретателя Ж.Жаккара, который впервые применил ее для контроля ткацких операций. По замыслу Бэббиджа такая машина должна была автоматически выполнять различные вычисления при последовательном вводе набора перфокарт, содержащих пары команд и данных. Иэменяя расположение отверстий на карте и последовательность следования карт можно было менять порядок вычислений.

Меценат проекта - графиня Ада Августа Лавлейс - была программистом этой “аналитической машины”. Именно она убедила Бэббиджа в необходимости использования двоичной системы счисления вместо десятичной. Ею были разработаны новые принципы программирования, предусматривающие повторение одной и той же последовательности команд и выполнение этих команд при определенных условиях (команды условного перехода). Ее именем назван разработанный в 1979 году алгоритмический язык ADA.

Во второй половине 19 века Г.Холлерит разработал машину с перфокарточным вводом, способную автоматически классифицировать и составлять таблицы данных. Наличие-отсутствие отверстия в перфокарте обнаруживалось электрическими контактными щетками, а в счетчиках применялись реле. Впервые эта машина использовалась в 1890г. в Америке при обработке результатов переписи населения. Именно тогда стало ясно, что без создания новых процессов обработки данных невозможно выполнять обработку больших массивов информации. С тех пор машины с перфорированными картами получили широкое распространение в деловой и административной сферах. В 1896г. Холлерит основал фирму, которая явилась предшественницей знаменитой IBM (это название возникло в 1924г.).

Скорость вычислений в механических машинах на основе зубчатого колеса и в электрических машинах, выполненных на реле, была ограничена, поэтому в 30-х гг. начались разработки электронных вычислительных машин (ЭВМ), элементной базой которых стала трехэлектродная вакуумная лампа, изобретенная в 1906 г. Лидом Форестом.

Первая треть 20 века ознаменовалась последовательным развитием и внедрением многих вычислительных устройств. Весьма значительный вклад в эту область внес математик Алан Тьюринг, который в 1937 г. опубликовал работу с описанием универсальной схемы вычислений. Хотя машина Тьюринга была лишь теоретическим построением и никогда серьезно не рассматривалась как экономически приемлемая машина, она привлекла внимание ряда исследователей.

Вторая мировая война дала серьезный толчок к усовершенствованию вычислительных устройств и технологии их производства. В 1944 г. Говард Айкен и группа исследователей из IBM построили электрическую вычислительную машину на релейных логических элементах.

С 1943 г. по 1946 г. в Университете г. Пенсильвания (США) была построена первая полностью электронная цифровая ЭВМ, получившая название ENIAK. Главной цель при разработке этой машины было составление числовых таблиц для вычисления траектории полета снарядов и ракет. Машина весила 30 т., занимала площадь 200 кв.м., содержала 18 тыс. ламп. В ее работе использовалась десятичная система счисления. Команды по программе вводились вручную; после введения программы порядок выполнения мог быть изменен только после выполнения всей программы. Каждая новая программа требовала новой комбинации сигналов, путем установки переключателей и коммуникации разъемов. В результате на создание и выполнение даже самой простой программы требовалось очень много времени.

Сложности в программировании на ENIAK натолкнули Джона фон Неймана (1903-1957), бывшего консультантом проекта, на разработку новых принципов построения архитектуры ЭВМ.

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

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

Эти принципы были реализованы в новой ЭВМ EDVAC. В этой машине применялась двоичная арифметика, основная память была способна хранить 1024 44-разрядых слова. Эта ЭВМ была введена в эксплуатацию в 1951 г.

ЭВМ, созданные в первой половине 20 века, имели две важные особенности, которыми не обладали ранее созданные машины: возможность программирования и способность хранения информации.

Поколения ЭВМ

Историю развития вычислительных машин принято рассматривать по поколениям.

Первое поколение (1946-1960) - это время становления архитектуры машин фон-неймановского типа, построенных на электронных лампах с быстродействием 10-20 тыс. арифметических операций в сек. В Советском Союзе к первому поколению относится первая отечественная вычислительная машина МЭСМ (Малая Электронная Счетная Машина), созданная в 1951 г. в г. Киеве под руководством академика С.А.Лебедева, серийные машины Минск -1, Стрела, БЭСМ (Большая Электронная Счетная Машина), Урал-1, Урал-4 и др.

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

Второе поколение (1960- 1964) - машины, построенные на транзисторах, с быстродействием до сотен тыс. операций в сек. Стала использоваться библиотека стандартных программ, а процесс программирования стал более легким. Первой полупроводниковой машиной была, появившаяся в 1959 г., модель RCA-501. В советском Союзе к этому поколению относятся машины Минск-2, Минск-22, Минск-32, БЭСМ-2, БЭСМ-4, БЭСМ-6, быстродействие которой составляло миллион операций в сек.

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

Вычислительные машины третьего поколения, как правило, образуют серии (семейства) машин, совместимых программно. Такая серия состоит из ЭВМ, производительность и объем памяти которых возрастают от одной машины серии к другой. Но программа, отлаженная на одной из машин серии, может быть сразу запущена на другой машине этой серии (на машинах большей мощности).

Первым таким семейством машин третьего поколения была выпущенная в 1965 г. IBM/360. Она имеет свыше семи моделей.

В Советском Союзе такую серию составляли машины семейства ЕС ЭВМ (Единая Система ЭВМ), совместимых с IBM/360, так как являлись копиями американских ЭВМ.

Четвертое поколение (1970-1980-е) - это машины, построенные на больших интегральных схемах (БИС). Такие схемы содержат до нескольких десятков тысяч элементов на кристалле. ЭВМ этого поколения выполняют десятки и сотни миллионов операций в сек. Появляются микропроцессоры, способные обрабатывать числа длинной в 16 и 32 разряда, статическая память емкостью 256 Кбайт и динамическая память емкостью в 1 Мбайт.

ЭВМ по своим характеристикам так разнообразны, что их начинаю классифицировать на: сверх большие ЭВМ (B-7700 - фирма Барроуз, Иллиак -IV - Иллинойский университет, Эльбрус - СССР), большие (универсальные), мини-ЭВМ и микро-ЭВМ (ПК).

Пятое поколение (1980- в настоящее время не появились). В 1979 г. японскими специалистами, объединившими свои усилия под эгидой научно-исследовательского центра по обработке информации - JIPDEC, была впервые поставлена задача разработки принципиально новых компьютеров. В 1981 г. JIPDEC опубликовал предварительный отчет, содержащий детальный многостадийный план развертывания научно-исследовательских и опытно-конструкторских работ с целью создания к 1991 г. прототипа ЭВМ нового поколения. Этот отчет лег в основу японской национальной программы создания ЭВМ пятого поколения. Отличительными чертами ЭВМ этого поколения являются:

- новая технология производства, не на кремнии, а на базе других материалов:

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

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

- искусственный интеллект, т.е. автоматизация процессов решения задач, получения выводов, манипулирования знаниями.

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

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

Персональные компьютеры (ПК). История создания и развития персональных компьютеров

Официальная история ПК берет начало с августа 1981 г., когда фирма IBM (International Business Machines Corporation) известила о создании “Персонального компьютера”. К весне 1982 г. этот ПК продавался в больших количествах, причем спрос намного превышал предложение.

С самого начала появления ПК стало ясно, что необходима модель, которую можно носить с собой в небольшом чемодане. Это привело к появлению фирмы Compaq Computer. И первым пополнением семейства ПК стал компьютер, известный под названием Compaq. О его создании было официально объявлено осенью 1982 г., спустя чуть больше года после выпуска оригинального ПК.

Следующей весной, в 1983 г., свой вклад в пополнение семейства ПК внесла фирма IBM. Появилась модель XT, которая добавила к ПК жесткий диск памяти большого объема. Фирма Compaq Computer ответила тем же, создав аналогичную машину в переносном варианте осенью 1983 г. Эта модель была названа Compaq Plus.

Летом 1984 г. появились две высокопроизводительные модели ПК. Одной из них была модель Compaq Desk Pro, первый член семейства ПК, превосходивший исходную модель по производительности вычислений. Вскоре после этого IBM выпустила компьютер AT, скорость вычислений которого намного превышала соответствующие параметры моделей исходных компьютеров и XT, и даже нового Desk Pro. Тактовая частота - 4 МГц.

Для ускорения появления новых моделей фирма IBM пользуется микропроцессорами, которые производит фирма Intel. Машина PC AT была построена на базе процессора Intel 8088. Следующие модели - на базе процессоров 80286, 80386, 80486 и 80586. В названиях этих моделей используются последние три цифры номера процессора.

Классификация

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

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

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

габариты компьютера;

ресурсные возможности компьютера.

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

Класс больших компьютеров

Класс суперкомпьютеров

Класс персональных компьютеров

Класс малых компьютеров

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

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

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

Помимо указанных характеристик, возможности компьютера характеризуются рядом параметров:

разрядность и формы представления чисел;

емкость внешней памяти;

характеристики внешних устройств хранения, обмена и ввода-вывода информации;

пропускная способность устройств связи узлов ЭВМ между собой;

способность ЭВМ одновременно работать с несколькими пользователями и выполнять одновременно несколько программ;

типы операционных систем, используемых в машине;

программная совместимость с другими типами ЭВМ, т.е. способность выполнять программы, написанные для других типов ЭВМ;

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

надежность и пр.

Класс больших компьютеров

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

серверы;

суперкомпьютеры.

Сервер-мощный компьютер в вычислительных сетях, который обеспечивает обслуживание подключенных к нему компьютеров и выход в другие сети.В зависимости от назначения определяют такие типы серверов:Сервер приложений обрабатывает запросы от всех станций вычислительной сети и предоставляет им доступ к общим системным ресурсам (базам данных, библиотекам программ, принткрам, факсам и др.).Файл-сервер-для работы с базами данных и использования файлов информации, хранящихся в ней. Архивационный сервер-для резервного копирования информации в крупных многосервисных сетях. Он использует накопители на магнитной ленте(стриммеры) со сменными картриджами емкостью до 5 Гбайт. Обычно выполняет ежедневное автоматическое архивирование информации от подключенных серверов и рабочих станций.Факс-сервер-для организации эффективной многоадресной факсимильной связи, с несколькими факсмодемными платами, со специальной защитой информации от несанкционированного доступа в процессе передачи, с системой хранения электронных факсов.Почтовый сервер-то же, что и факс-сервер, но для организации электронной почты, с электронными почтовыми ящиками.Сервер печати-для эффективного использования системных принтеров. Сервер- телеконференций-компьютер, имеющий программу обслуживания пользователей телеконференциями и новостями, он также может иметь систему автоматической обработки видеоизображений и др.

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

Суперкомпьютеры

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

В суперкомпьютерах используется мультипроцессорный (многопроцессорный) принцип обработки информации.

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

ПК

Персональными называют компьютеры, предназначенные для индивидуального пользования. Персональные компьютеры - небольшие и относительно недорогие ЭВМ, способные аккумулировать и усиливать интеллект своего персонального хозяина. Для них характерны:

1) малые габариты и масса, позволяющие устанавливать их на рабочем столе пользователя;

2) дружественный человеко-машинный интерфейс;

3) ориентация программного обеспечения на массового пользователя и наличие большого числа готовых программных средств для различных видов профессиональной деятельности;

4) возможность использования языков высокого уровня (Бейсик, Паскаль, Пролог, С++ и др.);

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

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

Персональные компьютеры используются сейчас повсеместно. За четверть века, прошедшие с момента создания персонального компьютера, уже сменилось несколько их поколений: 8-битные, 16-битные, 32-битные. Многократно усовершенствовались внешние устройства, все операциональное окружение, включая сети, системы связи, системы программирования, программное обеспечение и т.п. Персональный компьютер занял нишу "персонального усилителя интеллекта" множества людей, стал в ряде случаев ядром автоматизированного рабочего места(в цехе, в банке, в билетной кассе, в школьном классе и т. д.). Их основное назначение - выполнение рутинной работы: поиск информации, составление типовых форм документации, фиксация результатов исследования, подготовка текстов разного рода от простейших документоа до издательской верстки и т. д.

Малые компьютеры

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

Среди малых компьютеров выделяют подкласс портативных компьютеров

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

Ноутбук заменяет настольный персональный компьютер, поэтому он имеет высокое быстродействие; большой, четкий и яркий экран дисплея; малое энергопотребление, т. к. его источником является батарея. Если же портативный компьютер предназначен только для работы в дороге и является лополнением к основному настольному, то он должен иметь хороший модем, более длительное время работы от батареи, значительно меньший вес. Ни в какой другой компьютерной технике не достигается больше компромиссов, чем в ноутбуках!

Современные блокнотные компьютеры производят очень хорошее впечатление. Они снабжены жесткими дисками большой емкости-до 8 Гб, имеют отсеки для подсоединения CD-ROM, приемлемый вес.

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

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

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

Понятие информатики

Информатика - это наука и техника, связанные с машинной обработкой, хранением и передачей информации. Поэтому центральное понятие в информатике - информация. Точное выяснение понятия "информация" существенно необходимо для понимания систем обработки информации. Вообще, понятие "информация" используется нами в разных смыслах. Мы обычно под информацией понимаем высказывания относительно событий, взаимосвязей или состояний реального мира. Н/р "Волга впадает в Каспийское море."

В информатике информацией называется абстрактное содержание какого-либо высказывания, описания, указания (оператора), сообщения. Необходимо отличать информацию, т.е. абстрактное содержание от изображения информации. Н/р математическое понятие "целое число" является абстрактным понятием. Мы изображаем целые числа в виде последовательности цифр из множества {0, 1,... 9}. Можно изобразить целое число римскими цифрами или палочками, насечками. Все это изображения, т.е. внешние формы информации - представления.

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

Для машинной обработки информации существует много форм представления информации от условных знаков (сигналов) и произносимых слов до рисунков или последовательностей символов. Все представления (изображения) информации не будут иметь смысла, если не будет известно о значениях представлений. Н/р древние надписи и рисунки. Это внешняя форма. Однако нам неизвестны значения этих изображений, поэтому нам недоступен их смысл, т.е. абстрактное значение информации. Поэтому важно установить способ для выявления значения представления.

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

Многие формы представления информации допускают различное толкование. Н/р "красный". Только в том случае, когда существуют единые, согласованные интерпретации, возможен обмен информацией. Н/р дорожные знаки.

С другой стороны одно и то же абстрактное содержание м.б. представлено различными способами. Н/р числа.

Выявление подходящих систем представления (языков) для определенных классов информации является одной из задач информатики.

Вопрос об отношении информации к реальности, т.е. является ли информация истинной не рассматривается и не решается в информатике, т.к. ответ на него зависит от субъективного восприятия. Итак, мы различаем в связи с информацией:

- ее представление или изображение (внешняя форма)

- ее значение (собственно "абстрактная" информация)

- ее отношение к реальному миру (связь абстрактной информации с

действительностью.

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

- схематизированного представления (изображения) информации: структуры объектов и данных, а также их взаимосвязи;

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

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

В информатике рассматриваются информационные системы вида (A, R, I). Где R - множество представлений с интерпретацией I во множестве A элементов (информаций). Т.о. интерпретации соответствует отображение: I : R -> A (интерпретация I ставит в соответствие данному представлению r некоторое абстрактное информационное содержание I[r].) R также называют системой представления, а A - семантической моделью.

Пример (система представления для натуральных чисел). Пусть N - множество нат. чисел (включая число "нуль"), представляемых числом штрихов, т.е.:

, , , …

где через обозначена пустая последовательность. Интерпретацией I будет отображение десятичного представления в последовательность штрихов.

I : {0, 1, …, 9}+ N

I[0]=, I[1]= , I[2]= , …

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

Часто в какой-нибудь системе представления имеется много различных изображений одной и той же информации. Эти изображения называются эквивалентными. Точнее говоря, в информационной системе (A, R, I) справедливо: два изображения r1, r2R называются семантически эквивалентными, если они несут одинаковую информацию:

I[r1]=I[r2]

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

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

Пусть (A, R, I) - информационная система. Если I сюръективно, т.е. для каждой информации аА существует представление

rR с I[r]=a,

то каждая информация имеет представление. Обычно представляют интерес ИС обладающие этим свойством.

Отображение на множестве представлений при определенных предположениях индуцирует и отображение информации. Пусть f: RR отображение на множестве представлений R. Если для всех x, yR справедливо:

I[x]=I[y] I[f(x)]=I[f(y)]

и I сюръективно, то вследствие интерпретации I:RA однозначным образом устанавливается отображение информации f' : AA по следующему правилу:

f'(a)=b, если для rR справедливо I[r]=a и I[f(r)]=b.

Также справедливо I[f(r)]=f'(I[r]). f' называют абстракцией f.

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

Пример:

1/2^i, 0.(9), 0!, 1

Все эти термы имеют значение "один". Однако они различаются с точки зрения простоты, чтения, интерпретации и понимания.

Простота конкретного изображения информации имеет важное значение. Часто подмножество S (изображений простой внешней формы) изображений R выделяется как множество нормальных форм. Тогда S называют системой нормальных форм(СНФ). Если в такой системе для каждого изображения существует по меньшей мере 1 семантически эквивалентная НФ, то СНФ называется полной.

Пусть SR - СНФ. Если любое множество изображений с одинаковой интерпретацией имеет единственную НФ, т.е. отображение IS - инъективно, то СНФ называется однозначной.

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

Коды Хэмминга

Коды, предложенные Р. Хэммингом, обладают способностью обнаружить и исправить одиночные ошибки.

Предположим, что имеется код, содержащий m информационных разрядов и k контрольных разрядов. Запись на k позиций определяется при проверке на четность каждой из проверяемых k групп информационных символов. Пусть было проведено k проверок. Если результат проверки свидетельствует об отсутствии ошибок, запишем 0, если есть ошибка - 1. Запись полученной последовательности символов образует двоичное число.

Свойство кодов Хэмминга таково, что контрольное число указывает номер позиции, где произошла ошибка. При отсутствии ошибки в коде данная последовательность будет содержать только нули. Полученное число описывает таким образом n=(m+k+1) событий. Следовательно, справедливо неравенство

2k>=(m+k+1)

Определим теперь позиции, которые надлежит проверить в каждой из k проверок. Если в кодовой комбинации ошибок нет, контрольное число содержит только нули. Если в первом разряде контрольного числа стоит 1, это означает, что в результате первой проверки обнаружена ошибка. Первая проверка охватывает позиции 1, 3, 5, 7, 9, ... (в двоичной записи этих чисел младший разряд равен 1). Вторая проверка - 2, 3, 6, 7, 10...

Для контроля будем использовать позиции 1,2,4,8,..., так как в данные позиции встречаются только в одной проверяемой группе символов.

Введем, например, одиночную ошибку в код числа 5 - 0100101(2). Пусть после такой ошибки код стал 0110101. Подсчитываем суммы по модулю групп цифр и выписываем справа налево: 0011. Получилось ненулевое число, равное номеру позици, в которой возникла ошибка (3).

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

Ниже представлен калькулятор для получения кода Хэмминга и его декодирования. Выберите разрядность исходного кода, введите в самое первое поле кодируемое число, нажмите кнопку "Кодировать". Во втором поле будет отображен соответствующий код; поменяйте в нем один разряд и нажмите "Декодировать". Исходное число будет восстановлено с указанием разряда, в котором возникла ошибка.

Формальное понятие алгоритма. Рекурсивные функции. Системы текстовых замен (СТЗ)

Алгоритмами являются способы решения, описанные с помощью предписаний по обработке, которые удовлетворяют определенным требованиям.

Опр. Алгоритм - это способ с точным (т.е. выраженным в точно определенном языке) конечным описанием применения эффективных (т.е. практически выполнимых) элементарных шагов (переработки).

Это интуитивное понятие алгоритма.

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

Независимо от формы описания для алгоритмов важно различать следующие аспекты:

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

специфичный способ, каким решается задача, при этом для алгоритма различают:

а) элементарные шаги обработки, которые имеются в распоряжении;

б) описание выбора отдельных подлежащих выполнению шагов.

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

Массовость.

Дискретность - алгоритм представляется в виде конечной последовательности шагов.

Конечность.

Определенность.

Эффективность.

Пример: алгоритм Евклида.

если а=в то НОД(а, в)=а

если а>в то НОД(а, в)=НОД(а-в, в)

если а<в то НОД(а, в)=НОД(а, в-а)

Формальное понятие алгоритмов тесно связано с понятиями рекурсивных функций, машин Тьюринга, нормальных алгоритмов Маркова (или СТЗ).

Алгоритм называется терминистическим, если он завершается за конечное число шагов. Детерминистическим, если нет свободы в выборе очередного шага алгоритма. Детерминированным, если независимо от последовательности выполняемых шагов, результат определяется однозначно.

Существование или не существование алгоритма может быть установлено, если найти такой математический объект, который будет существовать в точности тогда, когда и алгоритм. Таким математическим объектом может быть рекурсивная функция. Функция определяется однозначно, если известен закон, по которому каждому набору х1, …, хn ставится в соответствие 1 значение функции y. Закон может быть произвольным, в т.ч. это может быть алгоритм вычисления значения функции. В этом случае функцию называют вычислимой, а алгоритм, по которому вычисляется функция, называется алгоритмом, сопутствующим рекурсивной функции. Рекурсивные функции являются частным классом вычислимых функций.

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

Простейшие базовые функции

Функция произвольного количества аргументов тождественно =0. Знак функции n - где n - количество аргументов.Сопутствующий алгоритм: если знак функции n то значение функции 0.Например:

1(3)=0, 3(4, 56, 78)=0;

Тождественная функция. Знак функции n,i . 0<i<=n. n - количество аргументов, i - номер аргумента. Сопутствующий алгоритм: если знак функции n,i то значение функции - значение i-го аргумента, считая слева направо. Например:

3,2(3,22,54)=22;

Функция получения последователя. Функция одного независимого аргумента. Знак функции - . Сопутствующий алгоритм: если знак функции то значение функции - число, следующее за значением аргумента.Например: (5)=6 или 5'=6.

3 приема построения сложных РФ

Оператор подстановки. F(f1, …, fn).Вычисляются значения функций f1, …, fn и используются как аргументы при вычислении

F.(y)= ((y))= (y')=y''.

Оператор рекурсии

R. f::= R[f1, f2, x(y)].

f - функция n аргументов, f1 - n-1 аргумента, f2 - n+1 аргумента, причем n-1 аргументов функций совпадают, а 2 следующих аргументов называются дополнительными. Один из них - х - называется главным доп. аргументом(ГДЭ). Он войдет в определяющую функцию. Другой y - вспомогательный доп. аргумент(ВДЭ), использующийся при построении новой функции.

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

f(0)=f1, f(i')=f2(i, f(i)).

Значением искомой функции при нулевом значении ГДЭ считать значение функции f1, а значением новой функции для каждого последующего значения ГДЭ считать значение функции f2 для предыдущего значения ГДЭ и для значения ВДЭ, совпадающего со значением искомой функции на предыдущем шаге.

Например:

PR(x) ::= R[0,2,1(x,y),x(y)]

PR(0) = 0 = 0

PR(1) = 2,1(0,PR(0))= 0

PR(2) = 2,1(1,PR(1)) = 1

Оператор минимизации или построение по первому нулю.

f ::=[f1, (x)] f(x1, …, xn)=(f1(x1, …, xn, y), (y))

с помощью функции f1 n+1 аргументов и дополнительного исчезающего аргумента.

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

Например:

r(x)::=(2,1(x, y), (y)]

r(0)=0

r(i) = 2,1(i, y) - не определено для i<>0.

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

Например:

y=x+1 - совпадает с базовой.

w=x+y - подстановка в (z+1) вместо z функции 3,3 (x, y, z). Получим f*(x, y, z)

Затем воспользуемся следующим:

S(x, y) ::= f1[1,1(x), f*(x, y, z); y(z)]

S(x, 0) =1,1 (x) = x

s(x, 1) = f*(x, 0, S(x, 0)) = s(x, 0) + 1

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

Формальное описание алгоритма через замену текстов

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

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

Пусть V - запас знаков. Пара (v, w) e V* х V* называется заменой над V. Замена часто записывается в виде

v w

Конечное множество R замен будем в дальнейшем называть системой текстовых замен (СТЗ) над V. Элементы этой системы будем называть также правилами текстовых замен (ПТЗ). СТЗ служат для представления алгоритмов. Отдельные шаги этих алгоритмов состоят, таким образом, в применении правил замен.

Замена

s t

называется применением правила v w, если имеются слова a, v, w, z V* такие, что справедливо

s = а ° v ° z, t = а ° w ° z.

Слово s V* называется терминальным (или терминалом} в R, если не существует слова t V* такого, что справедливо следующее: замена

st

является применением какого-либо правила из R. Таким образом, к терминальному слову s нельзя больше применить никакого правила замены.

Через повторное применение ПТЗ, исходя из начально заданного слова t0, возникают вычисления. Если t0, t1, ..., tn принадлежат V* и

ti-->ti+1

есть применение правила г из R для всех i,0<=i<=n, то последовательность (tj) 1<=i<=n называют (конечным) вычислением (последовательностью вычислении) над R для t0. Часто вычисление записывается следующим образом:

t0 t1 … tn

Слово t0 называется также входом для вычисления. Если tn есть терминал, то вычисление называется завершающимся (конечным) с результатом tn. Слово tn называется также выходом для R при входе t0. Бесконечное вычисление (последовательность вычислений) (ti)iN из слов ti V*, для которых ti-->ti+1 есть применение правил замен из R для всех i N, называется незавершающимся (бесконечным) вычислением.

Пример (вычисления по СТЗ)

(1) Для системы текстовых замен Q над множеством символов {L, О}, которая состоит из следующих правил:

LL е, О е, через последовательность

LOLL LO L

задается завершающееся вычисление для входного слова <LOLL> с результатом <L>.

(2) Для СТЗ над {L, О}, состоящей из правил

О OO, О L,

для входа <O> последовательность вычислений

О OO OL LL

является завершающимся вычислением с выходом <LL>, а последовательность

о ->. оо -> ооо ->. оооо ->...

является незавершающимся вычислением.

Система текстовых замен R в силу следующего предписания определяет алгоритм текстовых замен (АТЗ), который использует слова над V в качестве входа и выхода. Для входного слова t V* алгоритм работает следующим образом:

"Если одно из правил множества R применимо к слову t (т. e. существует слово s V*, для которого имеет место: l -» s есть применение правила из R), то примени правило к t и затем примени снова этот же алгоритм к слову s; в противном случае прекрати выполнение алгоритма".

Слово t служит входом для алгоритма; если (после конечного числа шагов) возникает терминальное слово, т. e. слово, к которому неприменимо никакое правило, то это слово является выходом (результатом вычислений). Если такая ситуация никогда не возникает, то алгоритм не завершается. Алгоритмы, определенные таким образом с помощью СТЗ, всегда являются последовательными. При этом выбор применяемого правила является недетермннистическим.

Часто для АТЗ в качестве входов используют только слова совершенно определенной формы (нормальная форма). Определенные знаки не входят в эти слова (а также и в выходные слова) - эти знаки, используются исключительно как вспомогательные знаки в словах, возникающих в процессе вычислений.

Примеры (алгоритмы текстовых замен)

(1) Сложение двух натуральных чисел, представленных в виде количества штрихов

Натуральное число представляется в виде количества штрихов с ограничительными скобками, т. e. число nN представляется словом <| |...|>, причем внутрь скобок входит n штрихов. В этом случае алгоритм состоит из одного единственного правила замены (е обозначает пустое слово):

> + < е

Для входа <|...|> + <|...|> алгоритм дает сумму штрихов.

(2) Умножение двух натуральных чисел (в таком же представлении)

Применяются вспомогательные знаки d, e, m. Алгоритм состоит из следующих правил замен:

|>*< >*<d

d| . |md

dm md

d> >

<>*< <e

e| e

em |e

e> >

Для входного слова <|...|> * <|...|> с п1 штрихами в первом операнде и п2 штрихами во втором операнде алгоритм дает выходное слово <|...1> с п1 * п2 штрихами.

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

Для входа <||> * <|||> возникает показанный на рисунке граф возможных вычислении. Все вычисления заканчиваются получением слова <|||||| >. Этот алгоритм подстановки недетерминистический, но детерминированный, т. е. дает, несмотря на различные вычисления, всегда один и тот же результат.

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

Детерминистические алгоритмы текстовых замен

Часто предпочитают рассматривать детерминистические АТЗ, т. е. алгоритмы, которые для каждого входного слова однозначно задают вычисления и тем самым в случае их завершения порождают вполне определенный результат. Это может быть обеспечено, например, установлением приоритетов применения правил. Такие приоритеты могут быть заданы просто порядком описаний правил.

Примером детерминистических алгоритмов являются так называемые алгоритмы Маркова (по имени русского математика А. А. Маркова). В алгоритмах Маркова правила замен линейно упорядочены (этот порядок определяется последовательностью описания правил). Тогда применение правил устанавливается следующим образом.

Определение (марковская стратегия применения). Если применимо несколько правил, то фактически применяется то из этих правил, которое в описании алгоритма встречается первым. Если правило применимо в нескольких местах обрабатываемого слова, то выбирается самое левое из этих мест.

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

- каждое вычисление по марковской стратегии является также общим вычислением в СТЗ;

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

Пример (алгоритмы Маркова). Пусть задана система текстовых замен R на множестве символов {v, ~, true, false, (, )} для редукции булевских термов, которые построены только из символов данного множества, к нормальной форме. Эта система состоит из следующих правил:

(1) ~ ~ е

(2) ~ true false

(3) ~.false true

(4) (true) true

(5) (false) false

(6) false v e

(7) v false e

(8) true v true true

Алгоритм, определенный данной системой, работает по марковской стратегии корректно для замкнутых булевских термов (т. е. замкнутые булевские термы переводятся в семантически эквивалентные однозначные нормальные формы, состоящие из true и false). Это справедливо лаже для замкнутых термов с неполностью расставленными скобками. Однако в этом случае возможны такие применения, которые не являются эквивалентными преобразованиями. Для терма

-.true v true по марковской стратегии получаются вычисления

-.true v true(правило (2) )

false v true(правило (6) )

true

В общей недетерминистической стратегиидополнительно получают (в смысле постановки задачи корректное) вычисление

- true v true (правило (8) )

- true (правило (2))

false

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

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

Путем сопоставления выходного слова каждому входному слову при конечном вычислении детерминистические алгоритмы вычисляют частичные функции. Функции являются частичными, так как иногда при некоторых исходных данных алгоритмы не завершаются и потому результат вычислений не определен. Это имеет место также и для АТЗ. Явного использования частичных функций можно избежать путем введения особого символа - ("дно"), который символизирует отсутствующий "результат" незавершающегося ("расходящегося") вычисления.

Каждый детерминированный алгоритм R в форме СТЗ на последовательностях символов V* определяет отображение:

fR: V* V* U

вследствие следующих правил. Пусть справедливо:

(1) fR (t) = г,

если слово г есть результат вычислений по R для входного слова t;