Лекция 1



Лекция 1

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

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

Ключевые слова: информатика, знания, история информатики, система, графика, дерево, письмо, информация, механизмы,централизованное хранилище, технология, автоматизация, компьютер, методология, Личность, процедурное программирование,математика, идеализация, определение, computer, science, предмет информатики, теоретическая информатика, прикладная информатика, техническая информатика, деление, brainware, software, программное обеспечение, hardware, аппаратное обеспечение, мировоззренческая роль информатики, внутренние связи, воспитательная роль информатики, алгоритмический подход, культурная роль информатики, эстетическая роль информатики, симметрия

Лекционный материал

Хотя информатика и считается достаточно молодой наукой (по отношению ко многим другим отраслям знания ), но предпосылки к ее зарождению – достаточно древние.

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

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

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

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

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

Развиваются различные системы, счета и механизации (это, как известно, – предпосылка автоматизации) счета.

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

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

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

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

Совершенствуются различные системы визуализации информации – карты, чертежи, пирамиды, дворцы, акведуки, механизмы и др.Пример. Механизмы штурма крепостей были достаточно сложны, древние водопроводные системы работают и до сих пор.

С появлением папируса повышается информационная емкость, актуализируется новое свойство информации – сжимаемость.

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

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

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

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

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

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

В отраслях науки формируются языковые системы: язык химических формул, язык физических законов, язык генетических связей и др..

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

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

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

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

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

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

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

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

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

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

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

Оба подхода должны быть взаимосвязаны.

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

Абсолютизация второго подхода может привести к излишнему формализму и идеализации.

Дадим теперь рабочее (в данном курсе) определение информатики. Это определение не является ни полным, ни точным, ни формальным (дать такое определение – невозможно), но для вводного курса, как кажется автору, – вполне приемлемое.

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

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

Во многих странах больше используется термин "computer science" (компьютерная наука, наука о компьютерах, точнее, наука о преобразовании информации с помощью компьютеров).

Предмет информатики точно невозможно определить – он сложный, многосторонний, динамичный.

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

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

Практическая, прикладная информатика ( software, "гибкое", программное обеспечение) изучает практические проблемы информационных сред.

Техническая информатика ( hardware, "тяжелое", аппаратное обеспечение) изучает технические проблемы информационных сред.

Пример. Задача построения математической модели прогноза кредитного риска банка – это задача теоретической информатики и экономики (естественно). Построение алгоритма прогноза по этой модели – задача теоретической информатики. Разработка компьютерной программы (комплекса программ) для прогноза риска – задача практической информатики.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 2

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

Аннотация: Рассматриваются основные понятия информатики – алфавит, слово, информация, сообщение, измерение сообщений и информации, виды и свойства информации, меры количества информации (по Хартли и Шеннону), их свойства и значение, вопросы связанные с информационными системами и управлением в системе.

Ключевые слова: информация, сообщение, мера хаоса, алфавит, определение, слово, буква, конечная последовательность,алфавита, Длина слова, словарный запас, информатика, классификация информации, свойства информации, байт, килобайт,мегабайт, гигабайт, петабайт, эксабайт, бит, количество информации, мера информации, мера, состояние системы, неравенство,множества, формула Хартли, вероятность, формула Шеннона, выражение, формула Больцмана, теоретический метод, эмпирико-теоретический метод, опрос, эмпирический метод, мониторинг, экспертные оценки, оценивание, логический метод, проблема планирования, идеализация, информационная система, информационная среда

Лекционный материал

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

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

• абстракция, абстрактная модель рассматриваемой системы (в математике);

• сигналы для управления, приспособления рассматриваемой системы (в кибернетике);

• мера хаоса в рассматриваемой системе (в термодинамике);

• вероятность выбора в рассматриваемой системе (в теории вероятностей);

• мера разнообразия в рассматриваемой системе (в биологии) и др.

Рассмотрим это фундаментальное понятие информатики на основе понятия "алфавит" ("алфавитный", формальный подход). Дадим формальное определение алфавита.

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

Буквой или знаком называется любой элемент x алфавита X, где [pic]. Понятие знака неразрывно связано с тем, что им обозначается ("со смыслом"), они вместе могут рассматриваться как пара элементов (x, y), где x – сам знак, а y – обозначаемое этим знаком.

Пример. Примеры алфавитов: множество из десяти цифр, множество из знаков русского языка, точка и тире в азбуке Морзе и др. Валфавите цифр знак 5 связан с понятием "быть в количестве пяти элементов".

Конечная последовательность букв алфавита называется словом в алфавите (или над алфавитом ).

Длиной |p| некоторого слова p над алфавитом Х называется число составляющих его букв.

Слово (обозначаемое символом [pic] ) имеющее нулевую длину, называется пустым словом: | [pic] | = 0.

Множество различных слов над алфавитом X обозначим через S(X) и назовем словарным запасом (словарем) алфавита (надалфавитом ) X.

В отличие от конечного алфавита, словарный запас может быть и бесконечным.

Слова над некоторым заданным алфавитом и определяют так называемые сообщения.

Пример. Слова над алфавитом кириллицы – "Информатика", "инто", "ииии", "и". Слова над алфавитом десятичных цифр и знаков арифметических операций – "1256", "23+78", "35–6+89", "4". Слова над алфавитом азбуки Морзе – ".", ". . –", "– – –".

В алфавите должен быть определен порядок следования букв (порядок типа "предыдущий элемент – последующий элемент"), то есть любой алфавит имеет упорядоченный вид X = {x1, x2, …, xn} .

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

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

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

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

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

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

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

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

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

Есть и другие типы классификации информации.

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

Основные свойства информации:

• полнота;

• актуальность;

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

• понятность;

• достоверность;

• массовость;

• устойчивость;

• ценность и др.

Информация – содержание сообщения, сообщение – форма информации.

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

Приведем основные соотношения между единицами измерения сообщений:

1 бит ( bi nary digi t – двоичное число) = 0 или 1,

1 байт 8 бит,

1 килобайт (1Кб) = 213 бит,

1 мегабайт (1Мб) = 223 бит,

1 гигабайт (1Гб) = 233 бит,

1 терабайт (1Тб) = 243 бит,

1 петабайт (1Пб) = 253 бит,

1 эксабайт (1Эб) = 263 бит.

Пример. Найти неизвестные х и у, если верны соотношения:

128y (К) = 32x ( бит );

2x (М) = 2y ( байт ).

Выравниваем единицы измерения информации:

27y (K) = 27y+13 ( бит );

2x (M) = 2x+20 ( байт ).

Подставляя в уравнения и отбрасывая размерности информации, получаем:

27y+13 = 25x

2x+20=2y

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

[pic]

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

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

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

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

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

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

[pic]

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

[pic]

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

H = log2N ( бит ).

Пример. Чтобы определить состояние системы из четырех возможных состояний, то есть получить некоторую информацию о системе, необходимо задать 2 вопроса. Первый вопрос, например: "Номер состояния больше 2?". Узнав ответ ("да", "нет"), мы увеличиваем суммарную информацию о системе на 1 бит ( I = log22 ). Далее необходим еще один уточняющий вопрос, например, при ответе "да": "Состояние – номер 3?". Итак, количество информации равно 2 битам ( I = log24 ). Если система имеет n различных состояний, то максимальное количество информации равно I = log2n .

Если во множестве X = {x1, x2, ..., xn} искать произвольный элемент, то для его нахождения (по Хартли) необходимо иметь не менее logan (единиц) информации.

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

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

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

Для таких систем используют более подходящую меру К. Шеннона. Мера Шеннона оценивает информацию отвлеченно от ее смысла:

[pic]

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

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

I = log2n .

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

рi = 0, i = 1, 3, 4, …, 10, р2 = 1 ,

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

I = log21 = 0 .

Обозначим величину:

fi = –nlog2pi.

Тогда из формулы К. Шеннона следует, что количество информации I можно понимать как среднеарифметическое величин fi , то есть величину fi можно интерпретировать как информационное содержание символа алфавита с индексом i и величиной piвероятности появления этого символа в любом сообщении ( слове ), передающем информацию.

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

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

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

[pic]

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

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

I+S(log2e)/k=const.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10. Исторический метод – поиск знаний с использованием предыстории, реально существовавшей или же мыслимой.

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

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

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

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

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

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

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

2. Идеализация – получение знаний о целом или его частях путем представления в мышлении целого или частей, не существующих в действительности.

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

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

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

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

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

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

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

4. поиск решения проблемы планирования и просчет различных вариантов, директив планирования, поиск оптимального решения; используемые чаще методы – измерение, сравнение, эксперимент, анализ, синтез, индукция, дедукция, актуализация, макетирование, визуализация, виртуализация и др.

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

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

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

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

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

Лекция 3

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

Аннотация: Рассматриваются основные понятия кодирования и шифрования информации, защиты информации и антивирусной защиты.

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

Лекционный материал

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

Одна из наиболее важных задач (всего общества) – задача кодирования сообщений и шифрования информации.

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

Введем некоторые основные понятия кодирования и шифрования.

Код – правило соответствия набора знаков одного множества Х знакам другого множества Y. Если каждому символу Х прикодировании соответствует отдельный знак Y, то это кодирование. Если для каждого символа из Y однозначно отыщется понекоторому правилу его прообраз в X, то это правило называется декодированием.

Кодирование – процесс преобразования букв (слов) алфавита Х в буквы (слова) алфавита Y.

При представлении сообщений в ЭВМ все символы кодируются байтами.

Пример. Если каждый цвет кодировать двумя битами, то можно закодировать не более 22 = 4 цветов, тремя – 23 = 8 цветов, восемью битами (байтом) – 256 цветов. Для кодирования всех символов на клавиатуре компьютера достаточно байтов.

Сообщение, которое мы хотим передать адресату, назовем открытым сообщением. Оно, естественно, определено над некоторым алфавитом.

Зашифрованное сообщение может быть построено над другим алфавитом. Назовем его закрытым сообщением. Процесс преобразования открытого сообщения в закрытое сообщение и есть шифрование .

Если А – открытое сообщение, В – закрытое сообщение ( шифр ) , f – правило шифрования, то f(A) = B.

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

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

Если k – ключ, то можно записать f(k(A)) = B. Для каждого ключа k, преобразование f(k) должно быть обратимым, то есть f(k(B)) = A. Совокупность преобразования f(k) и соответствия множества k называется шифром.

Имеются две большие группы шифров: шифры перестановки и шифры замены.

Шифр перестановки изменяет только порядок следования символов исходного сообщения. Это такие шифры, преобразования которых приводят к изменению только следования символов открытого исходного сообщения.

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

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

Пример. Один из лучших примеров алгоритма шифрования – принятый в 1977 году Национальным бюро стандартов США алгоритмстандарта шифрования данных DES (Data Encrypted Standard). Исследования алгоритма специалистами показали, что пока нет уязвимых мест, на основе которых можно было бы предложить метод криптоанализа, существенно лучший, чем полный переборключей. В июле 1991 года введен в действие аналогичный отечественный криптоалгоритм (стандарта ГОСТ 28147-89 ), который превосходит DES по надежности.

Криптогpафическая система – семейство Х пpеобpазований откpытых текстов. Члены этого семейства индексиpуются, обозначаются символом k ; паpаметp k является ключом. Множество ключей K – это набоp возможных значений ключа k. Обычно ключ пpедставляет собой последовательный pяд букв алфавита.

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

Кpиптосистемы pазделяются на симметpичные, с откpытым ключом, и системы электронной подписи.

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

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

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

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

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

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

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

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

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

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

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

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

Пример. В российских шифрах часто используется 256-битовый ключ, а объем ключевого пространства составляет 2256. Ни на одном реально существующем или возможном в недалеком будущем компьютере нельзя подобрать ключ (полным перебором) за время, меньшее многих сотен лет. Российский криптоалгоритм проектировался с большим запасом надежности, стойкости.

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

Оценка безопасности компьютерных систем базируется на различных классах защиты систем:

• класс систем минимальной защищенности ( класс D);

• класс систем с защитой по усмотрению пользователя ( класс C);

• класс систем с обязательной защитой ( класс B);

• класс систем с гарантированной защитой ( класс A).

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

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

Пример. Многократно разославшая свой код в 2000 году вирусная программа в Интернете могла при открытии приложения к тексту письма с интригующим заголовком ( ILoveYou – ЯТебяЛюблю ) рассылать свой код по всем адресам, зафиксированным в адресной книге данного получателя вируса, что приводило к веерному размножению вируса по Интернету, ибо адресная книга каждого пользователя может содержать десятки и сотни адресов.

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

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

Пример. Одну из самых популярных антивирусных программ AIDSTEST автор (Д. Лозинский) обновляет иногда дважды в неделю. Известная антивирусная программа AVP лаборатории Касперского содержит в своей базе данные о нескольких десятках тысячвирусах, вылечиваемых программой.

Вирусы бывают следующих основных видов:

• загрузочные – заражающие стартовые секторы дисков, где находится самая важная информация о структуре и файлах диска (служебные области диска, так называемые boot–сектора);

• аппаратно-вредные – приводящие к нарушению работы, а то и вовсе к разрушению аппаратуры, например, к резонансному воздействию на винчестер, к "пробою" точки на экране дисплея;

• программные – заражающие исполняемые файлы (например, exe-файлы с непосредственно запускаемыми программами);

• полиморфные – которые претерпевают изменения (мутации) от заражения к заражению, от носителя к носителю;

• стелс-вирусы – маскирующиеся, незаметные (не определяющие себя ни размером, ни прямым действием);

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

• многоцелевые вирусы.

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

Вирусы могут проникать в сеть, например:

• с внешних носителей информации (из копируемых файлов, с дискет);

• через электронную почту (из присоединенных к письму файлов);

• через Интернет (из загружаемых файлов).

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

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

• если используются в системе различные платформы, операционные среды, то антивирусный пакет должен поддерживать все эти платформы;

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

• антивирусный пакет должен обнаруживать – скажем, с помощью различных эвристических процедур – новые неизвестныевирусы и иметь пополняемую и обновляемую регулярно базу данных о вирусах ;

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

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

Лекция 4

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

Аннотация: Рассматриваются основные понятия числовых систем, правила их построения, выполнение действия в них.

Ключевые слова: алфавит, счисление, система, операции, представление, основание, позиционная система счисления,непозиционная система счисления, DCL, запись, конкатенация, перевод, таблица, сложение, единица, обратный код, Дополнение,дополнительный код, вычитание, поле, бесконечное множество, множества, окрестность, подмножество, диапазон, мантисса,целый, нормализация, целое число

Лекционный материал

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

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

Все системы счисления строятся по общему принципу: определяется величина р – основание системы, а любое число хзаписывается в виде комбинации степеней веса р от 0-й до n-й степени следующим образом:

(x)10 = xnpn + xn–1pn–1 + ... + x1p1 + x0p0 .

Наиболее используемые в информатике системы счисления, кроме, естественно, десятичной, – это: 1) двоичная, над алфавитом Х = {0,1} ; 2) восьмеричная, над Х = {0, 1, 2, 3, 4, 5, 6, 7} ; 3) шестнадцатеричная, над Х = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F}, где символы А, В, С, D, Е, F имеют, соответственно, десятичные веса 10, 11, 12, 13, 14, 15.

Пример. 11012 = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = 8 + 4 + 1 = 1310 ,

1578 = 1 x 82 + 5 x 81 + 7 x 80 = 64 + 40 + 7 = 11110 ,

A6F16 = 10 x 256 + 6 x 16 + 15 x 1 = 267110 .

В большинстве систем счисления вес цифры (или символа алфавита) зависит от ее места в записи числа или слова. Такая система счисления называется позиционной ; в противном случае система называется непозиционной.

Пример. Непозиционная система – древняя римская система записи чисел с алфавитом вида Х={I (1), V (5), Х (10), L (50), С (100), D (500), М (1000)}, где в скобках указаны веса символов (не зависящие от позиции символа). Примеры римских чисел (в скобках – обычные десятичные эквиваленты): III (3), IV (4), V (5), VI (6), IX (9), XI (11), DCL (650). Запись числа в этой системе получается двусторонней конкатенацией, причем правая конкатенация ассоциируется с добавлением, а леваяконкатенация – с убавлением (например, IV и VI ). Поразрядное же выполнение арифметических операций не имеет места (например, XIV + IV = XVIII ).

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

Пример. 110,0012 = 1x22 + 1 x 21 + 0 x 20 + 0 x 2-1 + 0 x 2-2 + 1 x 2-3 = 6,12510 ;

A,B16 = A x 160 + B x 16-1 = 10 x 1 + 11 x 0,0625 = 10,687510 .

Процедура перевода десятичных чисел в р-ную систему счисления:

1. перевести отдельно целую часть числа х, для чего последовательно делить сперва целую часть [х]10 , а затем все частные (получаемые при делении) на р до тех пор, пока не получим в очередном частном число меньшее р ; изображение [х]pполучается последовательным приписыванием к последнему частному остатков от деления – от последнего до первого;

2. перевести отдельно дробную часть (мантиссу) числа, то есть {x}10 , для чего последовательно умножать сперва исходную мантиссу, а затем мантиссы получаемых чисел на р до тех пор, пока не получим мантиссу, равную нулю, или нужное количество цифр в {х}p ; изображение {х}p получается приписыванием к целой части первого произведения второй такой же цифры и т.д., до последней цифры целой части;

3. результат будет иметь вид (х)р = [х]p, {х}p .

Пример. Найти: 12,810 = ?2 . Решение:

1. Переводим целую часть: 1210 =11002;

2. переводим дробную часть: 0,8 x 2 = 1,6; 0,6 x 2 = 1,2; 0,2 x 2 = 0,4; 0,4 x 2 = 0,8; 0,810 = 0,1100110...2 ;

3. результат перевода: 12,810 = 1100,1100110011...2 .

Пример. Найдем 29,2510 = ?8 . Решение имеет вид 1) 2910 = 358 ; 2) 0,2510 = 0,28 ; 3) 29,2510 = 35,28 .

Пример. Найдем 79,2610 = ?16 . Решение: 1) 7910 = 4F16 ; 2) 0,2610 = 0,4016 ; 3) 79,2610 = 4F,416 . При переводедробной части мы ограничились нахождением двух значащих цифр после запятой, ибо перевод точно сделать невозможно.

Для перевода из 2-ной в 8-ную и наоборот, из 2-ной в 16-ную и наоборот, из 8-ной в 16-ную и обратно, используется таблица следующего вида:

|Основание системы |

|10 |2 |8 |16 |

|0 |0 |000 |0000 |

|1 |1 |001 |0001 |

|2 |--- |010 |0010 |

|3 |--- |011 |0011 |

|4 |--- |100 |0100 |

|5 |--- |101 |0101 |

|6 |--- |110 |0110 |

|7 |--- |111 |0111 |

|8 |--- |--- |1000 |

|9 |--- |--- |1001 |

|10 |--- |--- |1010 |

|11 |--- |--- |1011 |

|12 |--- |--- |1100 |

|13 |--- |--- |1101 |

|14 |--- |--- |1110 |

|15 |--- |--- |1111 |

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

Пример. Рассмотрим переводы в смешанных системах.

1. Из 2-ной системы в 8-ную (двоично-восьмеричное изображение):

[pic]

2. из 8-ной системы в 2–ную (восьмерично-двоичное изображение):

[pic]

3. из 2-ной системы в 16-ную (двоично-шестнадцатеричное изображение):

[pic]

4. из 16-ной системы в 2-ную (шестнадцатерично-двоичное изображение):

[pic]

Сложение в двоичной системе счисления осуществляется по правилам

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 210 = 102 (единица идет в старший разряд).

Таблица вычитания в двоичной системе счисления имеет вид

0 – 0 = 0, 1 – 0 = 1, 1 – 1 = 0, 0 – 1 = 10 – 1 = 1 (единицу забираем у старшего разряда).

Таблица умножения в двоичной системе счисления имеет вид

0 x 0 = 0, 0 x 1 = 0, 1 x 0 = 0, 1 x 1 = 1.

Таблица деления в двоичной системе счисления имеет вид

0 : 0 = не определено, 1 : 0 = не определено, 0 : 1 = 0, 1 : 1 = 1.

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

Дополнительный код = обратный код + единица в младшем разряде.

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

Пример. Выполним вычитание напрямую и через сложение (через дополнительный код ):

[pic]

Целые числа в математике и их аналоги в n-разрядных арифметиках тождественны (по количеству) в рамках их представления с этой разрядностью. При этом можно отметить основные отличия представления чисел в поле памяти человека и в поле памяти n-разрядной арифметики:

1. бесконечное и счетное множество целых чисел представляется отрезком [–N; +N], где N – максимальное число, представимое в этой арифметике (многоточие – общее число единиц, равное n ): N = (111 . . . 1)2 ;

2. бесконечное и несчетное множество действительных чисел [pic], располагающееся на числовой оси равномерно и плотно, представляется в n-разрядной арифметике множеством с неравномерной плотностью (сгущение у нуля и сжатость со стороны меньших чисел);

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

С точки зрения обычной арифметики, например, в интервале (–1; 1) имеется бесконечное множество "плотно" расположенных точек, причем в любой окрестности каждой такой точки имеется хотя бы одна точка из этого множества. Такую арифметику называют часто регулярной арифметикой. Машинная же арифметика имеет следующие особенности. Она нерегулярна – точки интервала сгущаются около нуля; кроме того, в этом интервале точка х "изолирована" – если взять любую ее окрестность (х – а; х + а), где а – число, которое не превосходит машинного нуля (наименьшего представимого в машине числа), то в этом интервале нет других точек (отличных от х ). Говоря языком теории вероятности, плотности распределения чисел в регулярной и нерегулярной арифметике – различны, как, впрочем, плотности распределения целых и вещественных чисел в одной и той же арифметике. Множество вещественных чисел в машинной арифметике представляется как подмножество(определяемое разрядностью арифметики) множества рациональных чисел. Есть и другие особенности этих множеств (связанные, например, с выполнением операций), но указанные выше особенности – основные.

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

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

Так как диапазон n-разрядных чисел системы счисления с основанием p находится в пределах [pic], то для представления дробных чисел этот диапазон еще снижается, поскольку часть разрядов необходимо отвести под изображение мантиссы. Таким образом, имеются так называемые "зоны нечувствительности" форм представления чисел в n-разрядных арифметиках.

В 1937 году Конрадом Цузе для увеличения диапазона чисел, представимых в арифметике двоичных чисел, а также для повышения точности этого представления чисел было предложено представление чисел в плавающей, нормализованной форме – число x представляется в виде: [pic], где m – мантисса числа, k – целый порядок числа, [pic].

Пусть даны два числа: [pic] и [pic] ( [pic] ). Тогда можно проверить, что результаты выполнения операций будут равны:

[pic]

Если из n разрядов, отводимых под изображение чисел, m двоичных разрядов отвести под мантиссу, k – под порядок, один разряд – под знак числа и один разряд – под знак порядка (например, 0 – плюс, 1 – минус), то диапазон представимых в форме с плавающей запятой чисел резко увеличивается ( m + k + 2 = n ):

[pic]

(многоточие соответствует k единицам).

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

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

Пример. Вычислить наибольшее и наименьшее 5-разрядное целое число в системе счисления с основанием 3. Наибольшее целое n-разрядное число, которое возможно записать в системе счисления с основанием р, равно:

[pic]

Наименьшее целое n-разрядное число в этой системе равно

[pic].

Таким образом, в системе счисления с основанием 3 и числом разрядов 5 представим диапазон следующих чисел:

[pic]

Формулам можно придать более компактный вид. Например, для двоичной системы

[pic]

а в восьмеричной системе счисления эти числа

[pic]

К "неудобствам" этой формы представления чисел можно отнести возможность возникновения следующих "особо опасных" ситуаций:

1. если число достаточно мало, например, а = 0.12Е + 00, то оно может быть представлено любым числом из наименьшего интервала включающего а, в частности числом 0.120000001 или 0.199999999 и в этом случае сравнивать на равенство "в лоб" нельзя (вещественные числа в форме с плавающей запятой опасно сравнивать на совпадение);

2. порядок выполнения операций может влиять на результат, например, в 4-разрядной арифметике с фиксированной запятой 20.0000 + 0.0001 = 20.0001, но при этом 0.2000Е + 02 + 0.1000Е – 05 = 0.2000Е + 02 ;

3. может возникнуть так называемая ситуация "переполнения порядка" при сложении (умножении) очень больших чисел или "исчезновения порядка" при сложении (умножении) "очень малых чисел", в частности, 0.6000Е + 39 x0.1200Е + 64 = 0.9999Е + 99 (или же не определено), а также 0.6000Е – 35 x 0.0200Е – 65 = 0.9999Е – 99 (или же не определено), при соответствующим образом определенной разрядности десятичной арифметики;

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

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

Пример. В факториальной системе счисления целые числа записывают линейной комбинацией факториалов, например, [pic]. Эта система (условно) позиционна. Так как 0! = 1! = 1, то два младших разряда n-разрядного числа [pic] в разложении этого числа по факториалам представимы как [pic]! и поэтому веса этих разрядов не зависят от позиции (поэтому при [pic] это число можно считать непозиционным лишь условно). Формула перевода из факториальной системы счисления в десятичную систему:

[pic]

История развития систем счисления достаточно интересна. Приведем лишь некоторые факты. Счет вначале велся с помощью пальцев рук (пятерками и затем – десятками). В некоторых странах сохранился счет с основанием 12 (например, Великобритания – 12 шиллингов) и 20 (например, Франция – "quatre–vingts" или "четыре-двадцать" то есть 80; у древних адыгов счет велся аналогично: "тощIищ", то есть "двадцать-три" – 60) и др. 

Лекция 5

Высказывания и предикаты

Аннотация: Рассматриваются основные понятия и сведения алгебры высказываний и предикатов – высказывания, предикаты, аксиомы, логические выражения и функции, эквивалентные выражения и приведение к эквивалентному выражению, другие сопутствующие понятия и факты логики, а также инфологические задачи.

Ключевые слова: информатика, алгебра, ПО, аксиома, операции, сигнатура, носитель, высказывательная форма, единица, высказывание, истина, ложь, true, переменная, значение, предикат, выражение, логическая функция, аргумент, множества,дизъюнкция, конъюнкция, таблица, функция, операция импликации, отрицание, тавтология, упрощения логического выражения, эквивалентное выражение, логическое выражение, равенство, инфологическая задача, логический вывод, умозаключение, алгебра логики, вывод, доказательство

Лекционный материал

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

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

Операция f называется n-местной, если она связывает n операндов (объектов – участников этой операции).

Совокупность операций алгебры A называется ее сигнатурой, а совокупность элементов алгебры – носителем алгебры.

Утверждение ( высказывательная форма ) – основная единица, неделимая с точки зрения отражения смысла информации (семантики).

Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать ("сразу посмотрев на него"), истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "истина" и "ложь", "true" и "fаlse" или "1" и "0".

Переменная, значениями которой могут быть лишь значения "1" или "0", называется логической переменной или булевой переменной.

Пример. Рассмотрим словосочетания:

1. Москва – столица США.

2. Житель города Москва.

3. 5 – 7 + 8.

4. 5 – 9 + 28 = 4.

5. В пятую неделю зимы было очень холодно.

6. В Антарктиде живут тигры.

Высказывание должно быть однозначно истинным или однозначно ложным, поэтому высказываниями являются только утверждения 1), 4), 6).

Пример. Не является высказыванием и "парадокс лжеца" (Эвбулид, учитель Демосфена, около 350 лет до н.э.): "То, что я сейчас утверждаю, – ложно", ибо если оно истинно – то оно ложно, а если допустить, что оно ложно, то оно истинно. Это неопределенная высказывательная форма. Аналогичный пример принадлежит известному математику, логику Гёделю (1931 г.): "То, что утверждается в этом предложении, не может быть доказано". Если его можно опровергнуть, то его нельзя доказать, а если его нельзя опровергнуть, то его можно доказать. Предложения такого рода не могут быть доказаны или опровергнуты в пределах того языка (той теории, алгебры ), с помощью которой они сформулированы. Известны многие подобные парадоксы.

Рассматривая высказывания, мы не обращаем внимания на их внутреннюю структуру и можем разлагать их на структурные части, равно как и объединять их.

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

1. "Зима – холодное время года".

2. "Пальто – теплая одежда".

3. "Камин – источник тепла".

Истинным будет, например, сложное высказывание: "Зима – холодное время года и зимой носят пальто", а ложным будет, например, высказывание: "Некоторые ходят в пальто, поэтому на улице зима". Придумайте другие примеры.

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

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

Пример. Выражение "х = у" – предикат, "х > 5" – предикат, а "7 > 5" – высказывание. Утверждение "Хорошо" не являетсявысказыванием, утверждение "Оценка студента А по информатике – хорошая" – простое высказывание, утверждение "Вчера была ясная погода, я был вчера на рыбалке" – сложное высказывание, состоящее из двух простых.

Логической (булевой) функцией f(х) называется некоторая функциональная зависимость, в которой аргумент х – логическаяпеременная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}.

Пример. Заданы предикаты вида р = "число х делится нацело на 3" и q = "у – день недели". Найдем множество истинностипредикатов р и q, если [pic], [pic]. Получаем, что [pic], [pic].

Множество логических переменных [pic] с определенными над ним операциями: [pic] – отрицания или инверсии, [pic] – логического сложения или дизъюнкции, [pic] – логического умножения или конъюнкции называется алгебройпредикатов (и высказываний ) , если эти операции удовлетворяют следующим аксиомам:

1. Аксиома двойного отрицания:

[pic]

2. Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции ):

[pic]

3. Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов):

[pic]

4. Аксиомы одинаковых операндов:

[pic]

5. Аксиомы поглощения (множителем — множителя-суммы или слагаемым — слагаемого-произведения):

[pic]

6. Аксиомы распределения операции ( дизъюнкции относительно конъюнкции и наоборот):

[pic]

7. Аксиомы де Моргана (перенесения бинарной операции на операнды):

[pic]

8. Аксиомы нейтральности (взаимноинверсных множителей или слагаемых):

[pic]

9. Аксиома существования единицы ( истина, true, 1) и нуля ( ложь, false, 0), причем,

[pic]

Из этих аксиом следует ряд полезных соотношений, например,

[pic]

Три базовые операции алгебры предикатов определяются таблицей их значений, так как в алгебре предикатов из-за дискретности значений логических функций часто используется табличная форма задания функции. Булеву функцию n переменных можно полностью определить таблицей из 2n строк.

Пример. Составим таблицу истинности функции [pic]

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

[pic]

Пример. Заполним таблицу истинности трехместной логической функции [pic]

Пример. Изобразим графически множество истинности двухместного предиката вида р(х,у) = "модуль числа х равен модулю числа у", если задана область изменения аргументов: [pic]. Имеем соотношение

[pic]

Смысл предикатов р1(х,у) и р2(х,у) очевиден. Множество изображается графиком функции y=|x|, который дан на рис. 5.1:

[pic]

Рис. 5.1. График функции y = |x|

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

1. импликации: [pic] ;

2. эквиваленции: [pic].

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

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

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

Всегда истинные формулы называют тавтологиями.

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

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

Пример. Упростим:

[pic]

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

Пример. Докажем равенство логических выражений: [pic] Используя аксиомы алгебры предикатов, получаем равенства

[pic]

Левая часть равенства приведена к правой части, то есть данное равенство доказано полностью.

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

• правая часть равенства приводится к левой части;

• левая часть равенства приводится к правой части;

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

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

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

Пример. Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. В ходе следствия Браун сказал, что преступники были на синем "Бьюике", Джонс сказал, что это был черный "Крайслер", Смит утверждал, что это был "Форд", но не синий. Каждый указал неправильно либо марку, либо цвет автомобиля. Определим истинный цвет и истинную марку автомобиля. Рассмотрим простые высказывания вида: х = "машина – синяя", у = "машина – Бьюик", z = "машина – черная", u = "машина – Крайслер", v = "машина – Форд". На их основе высказывание Брауна можно записать в виде сложного логического выражения вида [pic], высказывание Джонса – в виде [pic], а высказывание Смита – в виде [pic] Так как в каждом из этих выражений одна из переменных принимает значение "истина", то истинны и дизъюнкции вида: [pic]. По определению конъюнкции, [pic]. Это выражение мы взяли из-за однозначности равенства 1 конъюнкции и неоднозначности (многовариантности) его равенства нулю. Упростим выражение:

[pic]

Мы использовали тот факт, что одновременно не могут быть истинными два высказывания относительно цвета или два высказывания относительно марки машины. Так как конъюнкция истинна только тогда, когда [pic], то заключаем, что автомобиль был черным "Бьюиком".

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

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

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

1. Аксиома исключения третьего : либо имеет место высказывание, либо его отрицание.

2. Аксиома противоречия : высказывания и его отрицание не могут иметь места одновременно.

3. Аксиома двойного отрицания : двукратное отрицание какого-либо утверждения равносильно исходному утверждению.

4. Аксиома тождества : всякое высказывание тождественно самому себе.

Если высказывания x и y связаны друг с другом отношением [pic], то говорят, что высказывание y следует из высказывания x (или y – следствие x ); если множество истинности Х высказывания х содержит множество истинности Y высказывания y, товысказывание x – условие, высказывание y – заключение, а само соотношение [pic] – вывод.

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

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

Лекция 6

Логические вентили, схемы, структуры

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

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

Лекционный материал

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

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

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

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

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

Логическая функция "инверсия", или отрицание, реализуется логической схемой ( вентилем ), называемой инвертор.

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

Аналогично, если предположить, что на входе инвертора будет напряжение в 1 вольт ("истина"), то на выходе инвертора будет сниматься 0 вольт, то есть "ложь" ( схемы на рисунках 6.1 а, б).

[pic]

Рис. 6.1. Принцип работы инвертора

Функцию отрицания можно условно отождествить с электрической схемой соединения в цепи с лампочкой (рис. 6.2), в которой замкнутая цепь соответствует 1 ("истина") или х = 1, а размыкание цепи соответствует 0 ("ложь") или х = 0.

[pic]

Рис. 6.2. Электрический аналог схемы инвертора

Дизъюнкцию [pic] реализует логическое устройство ( вентиль ) называемое дизьюнктор (рис. 6.3 а, б, в):

[pic]

Рис. 6.3a.

[pic]

Рис. 6.3b.

[pic]

Рис. 6.3c. Принцип работы дизъюнктора

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

[pic]

Рис. 6.4. Электрический аналог схемы дизъюнктора

Конъюнкцию [pic] реализует логическая схема ( вентиль ), называемая конъюнктором (рис. 6.5 а, б, в):

[pic]

Рис. 6.5a.

[pic]

Рис. 6.5b.

[pic]

Рис. 6.5c. Принцип работы конъюнктора

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

[pic]

Рис. 6.6. Электрический аналог схемы конъюнктора

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

[pic]

Рис. 6.7. а, б, в. Условные обозначения вентилей (вариант)

Пример. Транзисторные схемы, соответствующие логическим схемам [pic] ( инвертор ), [pic] ( дизъюнктор ), [pic] ( конъюнктор ) имеют, например, следующий вид (рис. 6.8 а, б, в):

[pic]

Рис. 6.8a. Инвертор

[pic]

Рис. 6.8b. Дизъюнктор

[pic]

Рис. 6.8c. Конъюнктор

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

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

Пример. В двоичной системе таблицу суммирования цифры x и цифры y и получения цифры z с учетом переноса p в некотором разряде чисел x и y можно изобразить таблицей

Эту таблицу можно интерпретировать как совместно изображаемую таблицу логических функций (предикатов) вида

[pic]

Логический элемент, соответствующий этим функциям, называется одноразрядным сумматором и имеет следующую схему (обозначим ее как [pic] или [pic] – если мы хотим акцентировать именно выбранный, текущий i-й разряд) (рис. 6.9):

[pic]

Рис. 6.9. Схема одноразрядного сумматора

Пример. "Черным ящиком" называется некоторое закрытое устройство (логическая, электрическая или иная схема), содержимое которого неизвестно и может быть определено (идентифицировано) только по отдельным проявлениям входа/выхода ящика (значениям входных и выходных сигналов). В "черном ящике" находится некоторая логическая схема, которая в ответ на некоторую последовательность входных (для ящика) логических констант выдает последовательность логических констант, получаемых после выполнения логической схемы внутри "черного ящика". Определим логическую функцию внутри "черного ящика" (рис. 6.10), если операции выполняются с логическими константами для входных последовательностей (поразрядно). Например, х = 00011101 соответствует последовательности поступающих значений: "ложь", "ложь", "ложь", "истина", "истина", "истина", "ложь", "истина".

[pic]

Рис. 6.10. Схема "черного ящика 1"

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

[pic]

Действительно, в результате "поразрядного" сравнения сигналов (последовательностей значений "истина", "ложь") получаем следующие выражения (последовательности логических констант):

[pic]

Пример. Попробуйте самостоятельно выписать функцию для "черного ящика"? указанного на рис. 6.11:

[pic]

Рис. 6.11. Схема "черного ящика 2"

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

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

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

[pic]

Схема, построенная для этой логической функции, приведена на рис. 6.12.

[pic]

Рис. 6.12. Схема для функции 1

Пример. Определим логическую функцию [pic], реализуемую логической схемой вида (рис. 6.13)

[pic]

Рис. 6.13. Схема для функции 2

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

[pic]

Лекция 7

Базовые алгоритмические структуры

Аннотация: Рассматриваются основные понятия об алгоритме в программах и алгоритмизации решения задач.

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

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

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

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

Алгоритм удовлетворяет следующим основным свойствам:

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

2. Выполнимость в определенной операционной среде (в определенном классе исполнителей).

3. Результативность отдельных команд и всего алгоритма.

4. Применимость алгоритма ко всем возможным входным данным конкретного класса задач.

5. Определенность (детерминированность) команд и всего алгоритма для всех входных данных.

6. Формализованное, конструктивное описание (представление) команд алгоритма.

7. Минимальная полнота системы команд алгоритма.

8. Непротиворечивость любых команд алгоритма на любом наборе входных данных.

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

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

Для записи, исполнения, обмена и хранения алгоритмов существуют различные средства, языки, псевдокоды – блок-схемы, структурограммы (схемы Нэсси-Шнайдермана), Р-схемы, школьный алгоритмический язык (ШАЯ), различные языки программирования.

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

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

Program ;

Uses ; { комментарии, если нужны }

Label ; { комментарии }

Const ; { комментарии }

Type ; { комментарии }

Var ; { комментарии }

{ < условия задачи и применимости алгоритма > }

{ < цель составления и выполнения алгоритма > }

Begin

; { комментарии }

; { комментарии }

; { комментарии }

End.

Пример. Программа вычисления объема v правильного цилиндра с радиусом основания r и высотой h.

Program VСil;

Uses Crt; { подключение библиотеки ввода/вывода на экран "в звуке и цвете" }

Const pi = 3.14;

Var r, h, v: real;

{ для правильного цилиндра с радиусом основания r и высотой h }

{ вычислить и выдать на экран значение его объема v }

Begin

ClrScr; { команда очистки экрана (от данных предыдущей задачи) }

ReadLn (r, h); { ввод входных параметров }

v:=pi*r*r*h; { вычисление объема по формуле для цилиндра }

WriteLn (‘Вычисленный объем цилиндра равен ’, v) { вывод результата }

End.

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

|Обычная запись |Паскаль |

|Квадрат числа х |sqr(x) |

|Корень квадратный из x |sqrt (x) |

|Модуль |х| |abs (x) |

|sin x |sin(x) |

|cos x |cos(x) |

|tg x |tg(x) |

|ctg x |ctg(x) |

|arcsin x |arcsin (x) |

|arccos x |arccos(x) |

|arctg x |arctg(x) |

|Натуральный логарифм ln x |ln(x) |

|Степень числа е = 2, 7... или еx |exp(x) |

|Остаток от деления целого х на целое у |x mod y |

|Частное от деления целого х на целое y |x div y |

|Целая часть числа х (вещественного) |int(x) |

|Случайное число от 0 до х |rnd(x) |

|Длина текста х в символах |length (x) |

Пример. Результаты применения этих функций: sqrt(9) = 3, abs(–5) = 5, sin(0) = 0, cos(0) = 1, ln(1) = 0, exp(1 ) =e, 23 mod 5 = 3, 20 mod 5 = 0, 23 div 5 = 4, 20 div 5 = 4, int(2.7) = 2, int(2) = 2, rnd(0) = 0.231356,length(‘информ’) = 6.

Порядок выполнения операций (старшинство операций – по убыванию) в языке Паскаль:

1. вычисление выражений в скобках;

2. вычисление стандартных функций;

3. умножение и деление (обозначаются "*" и "/");

4. сложение и вычитание (обозначаются "+" и "–").

Пример. Выражение b*c + (d/t*(v/n/m))*sin(x) вычисляется в следующем порядке (слева направо): v/n, (v/n)/m, d/t,(d/t)*(v/n/m), sin(x), b*c, (d/t*(v/n/m))*sin(x), b*c+(d/t*(v/n/m))*sin(x) и эквивалентно математическому выражению: [pic].

Рассмотрим базовые простые команды языка Паскаль.

1. Команда описания (заголовка) алгоритма (программы) :

Program ;,

где  – имя, задаваемое составителем программы (краткое, полное, грамотное отражение сути алгоритма ).

2. Ввод – команда ввода в рассмотрение (в тело алгоритма ) тех или иных входных параметров:

Read ();

или

ReadLn ();.

Первая команда вводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.

3. Вывод – команда вывода на экран тех или иных входных или выходных параметров алгоритма:

Write ();

или

WriteLn ();.

Первая команда выводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.

4. Присваивание – команда изменения текущего значения переменной вида:

:= ;,

где соответствует имени переменной, – корректно записанное выражение. Знак ":=" означает последовательное выполнение двух действий: определение текущего значения и замена текущего значения переменной, имя которой задано , на новое значение, равное значению .

5. Команда начала алгоритма (блока) – команда Begin.

6. Команда завершения алгоритма (блока) – команда End.

7. Команда вставки комментариев в текст алгоритма имеет вид:

.

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

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

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

2. ;

.

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

4. if

5. then

else ;.

Ключевые (служебные) слова Паскаля – if (если), then (то), else (иначе). Ключевые слова нельзя изменять, заменять, так как их эталоны закреплены в переводчике с языка Паскаль (о нем подробнее – ниже).

Пример. Команда вида

if (х>y) { если текущее значение х больше текущего значения y, }

then у := х { то текущее значение у полагаем равным текущему значению х, }

else x:= y; { иначе (при х n }

Begin

ClrScr; { команда очистки экрана (от данных предыдущей задачи) }

ReadLn (n); { ввод входного параметра }

s:=1; { начальное значение суммы до входа в цикл }

i:=1; { количество просуммированных чисел в начале }

while (s0) do { цикл деления числа и получаемых частных (пока делится) }

begin

i:=i+1; { переход к следующему делению }

c:=n mod 2; { находим очередной остаток от деления на 2}

n:=n div 2; { находим очередное частное от целочисленного деления }

write(c) { выдаем новую двоичную цифру }

end;

End.

Лекция 8

Данные их типы, структуры, обработка

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

Ключевые слова: данные, слово, математика, информатика, пробел, значение, метод решения, система линейных алгебраических уравнений, метод Гаусса, область определения, простые типы данных, структурированные типы данных, константы, подразделения,Паскаль, операции, равенство, деление, выражение, char, string, алгоритм, структура данных, массив, вектор, ряд, таблица, служебное слово, размерность, матрица, Произведение, программа, точность, разность

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

Данные – это некоторые сообщения, слова в некотором заданном алфавите.

Пример. Число 123 – данное, представляющее собой слово в алфавите из десяти натуральных цифр; число 12,34 – данное, представляющее собой слово в алфавите из десяти натуральных цифр и десятичной запятой; текст "математика и информатика – нужные дисциплины", – данное в алфавите из символов русского языка и знаков препинания, включая пробел.

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

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

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

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

Задаются типы данных простым перечислением значений типа, например как в простых типах данных, либо объединением (структурированием) ранее определенных каких-то типов – структурированные типы данных.

Пример. Зададим простые типы данных "специальность", "студент", "вуз" следующим перечислением:

специальность = (филолог, историк, математик, медик);

студент = (Петров, Николаев, Семенов, Иванова, Петрова);

вуз = (МГУ, РГУ, КБГУ).

Значением типа "студент" может быть Петров.

Пример. Опишем структурированный тип данных "специальность_студента":

специальность_студента=(специальность, студент).

Значением типа "специальность_студента" может быть пара ( историк, Семенов ).

Для обозначения текущих значений данных используются константы – числовые, текстовые, логические.

Часто (в зависимости от задачи) рассматривают данные, которые имеют не только "линейную" (как приведенные выше), но и иерархическую структуру.

Пример. Структуру "вуз" можно задать иерархической структурой, состоящей, например, из следующих уровней: "Ректорат", "Деканаты и подразделения", "Кафедры", "Отделы", "Преподаватели и сотрудники".

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

Пример. В школьном алгоритмическом языке (ШАЯ), например, целые, вещественные, символьные, текстовые (литерные, стринговые) и логические типы данных описываются ключевыми словами цел, вещ, сим, лит, лог. В языке Паскаль – аналогичными ключевыми словами integer, real, char, string, boolean.

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

Пример. Для целого типа данных назовем операции ":=", "+", "–", "*", "=" (сравнение на равенство), " [pic] ", "", " [pic] ", " [pic] ".. Для вещественного типа данных еще и операция "/" (деление). Для символьного типа данных – только ":=", "=", " [pic] ", "", " [pic] ", " [pic] ". Например, сравнение "а" ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download