Информатика и ИКТ курс лекций
Лекция 1
Введение. История, предмет, структура информатики
Аннотация: Рассматривается история развития информатики и излагается предмет информатики (в узком и широком понимании), основные три ее направления (теоретическая, прикладная и техническая), а также междисциплинарная, мировоззренческая, воспитательная, культурная, эстетическая и методологическая роль информатики в обществе и познании.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Лекционный материал
Хотя информатика и считается достаточно молодой наукой (по отношению ко многим другим отраслям знания ), но предпосылки к ее зарождению – достаточно древние.
При рассмотрении вопроса об истории информатики будем исходить из первых признаков и событий информационного обмена, осознавая, что об информатике как о науке тогда речь не шла.
Пример. Первый предмет для ведения счета обнаружен в Чехии (волчья кость с зарубками) и относится к 30000 г. до н.э.
Наиболее важной и ранней предпосылкой к информационному обмену стала речь, а позже – самые первые знаковые системы(живопись, музыка, графика, танец, обряды и др.).
Затем появилась письменность: вначале она была рисуночной, иероглифической, с использованием носителей различного типа (камень, глина, дерево и т.д.).
Пример. В Древнем Египте около 3000 г. до н.э. появилось иероглифическое письмо на камне, а затем и иератическое (не иероглифическое) письмо на папирусе. Бронзовый век дал нам идеограммы – изображения повторяющихся систем понятий, которые в конце IV века до н.э. превратились в рисуночное, иероглифическое письмо.
Развиваются различные системы, счета и механизации (это, как известно, – предпосылка автоматизации) счета.
Пример. В Древнем Вавилоне около 8000 г. до н.э. использовали различные эталоны меры (каменные шары, конусы, цилиндры и т.д.). Там же около 1800 г. до н.э. начали использовать шестидесятеричную систему счисления. Древние римляне положили в основу счисления иероглифическое обозначение пальцев рук (все символы этой системы счисления можно изобразить с помощью пальцев рук). Счет на основе пальцев использовался достаточно долго и дал нам десятичную систему счисления, применяемую во всем мире.
От рисунков на камне (пиктограмм) осуществляется переход к рисункам на дощечках, глиняных пластинах (клинописи), от клинописи – к слоговому (вавилонскому) письму, от вавилонского письма – к греческому, от греческого и латинского – к основным западным письменным системам, к возникновению пунктуационного письма.
На основе латинской и греческой письменности разрабатываются терминологические системы для различных областей знания – математики, физики, медицины, химии и т.д. Развивается математический (алгебраический) язык – основа формализации различныхзнаний. Распространение математической символики и языка приводит к развитию всего естествознания, так как появился адекватный и удобный аппарат для описания и исследования различных явлений.
Пример. Появляются символы дифференцирования, интегрирования, которые потом берутся "на вооружение" физикой, химией и другими науками.
Совершенствуются различные системы визуализации информации – карты, чертежи, пирамиды, дворцы, акведуки, механизмы и др.Пример. Механизмы штурма крепостей были достаточно сложны, древние водопроводные системы работают и до сих пор.
С появлением папируса повышается информационная емкость, актуализируется новое свойство информации – сжимаемость.
С появлением бумаги появляется эффективный носитель информации – книга, а изобретение печатного станка (Гуттенберга) приводит к тиражированию информации (новое свойство информационного обмена). Появляется достаточно адекватный (на тот период) инструмент массовой информационной коммуникации. Развиваются элементы виртуального мышления (например, в картинах известных художников).
Распространению информации способствует также появление и развитие библиотек, почты, университетов – центров накопленияинформации, знаний, культуры в обществе.
Пример. Появились централизованные хранилища информации, например, в столице Хеттского государства во дворце хранилось около 20 тыс. глиняных клинописных табличек.
Происходит массовое тиражирование информации, рост профессиональных знаний и развитие информационных технологий. Появляются первые признаки параллельной (по пространству и по времени) передачи и использования информации, знаний.
Пример. Изменение информационных свойств накладывает отпечаток и на все производство, на производственные и коммуникационные отношения, например, происходит разделение (по пространству, по времени) труда, появляется необходимость в развитии торговли, мореходства, изучении различных языков.
Дальнейший прогресс и возникновение фотографии, телеграфа, телефона, радио, кинематографа, телевидения, компьютера, компьютерной сети, сотовой связи стимулируют развитие массовых и эффективных информационных систем и технологий.
В отраслях науки формируются языковые системы: язык химических формул, язык физических законов, язык генетических связей и др..
С появлением компьютера стало возможным хранение, автоматизация и использование профессиональных знаний программ: баз данных, баз знаний, экспертных систем и т.д..
Пример. Персональный компьютер впервые становится средством и стимулятором автоформализации знаний и перехода от "кастового" использования ЭВМ (исключительно "кастой программистов") к общему, "пользовательскому" использованию.
Информатика от "бумажной" стадии своего развития переходит к "безбумажной", электронной стадии развития и использования.
В конце двадцатого века возник так называемый информационный кризис, "информационный взрыв", который проявился в резком росте объема научно-технических публикаций. Возникли большие сложности восприятия, переработки информации, выделения нужной информации из общего потока и др. В этих условиях появилась необходимость в едином и доступном мировом информационном пространстве, в развитии методов и технологии информатики, в развитии информатики как методологииактуализации информации, в формировании базовых технологий и систем и пересмотре роли информатики в обществе, науке,технологии.
Мир, общество начали рассматриваться с информационных позиций. Это время лавинообразного увеличения объема информации в обществе, ускорения их применения на практике, повышения требований к актуальности, достоверности, устойчивостиинформации. XXI век можно считать веком "информационного сообщества", единого и доступного мирового информационного пространства (поля), которое будет постоянно улучшать как производительные силы и производственные отношения, так и человеческую личность, общество.
Появление информатики как науки базируется на индустрии сбора, обработки, передачи, использования информации, на продуктах развития математики, физики, управления, техники, лингвистики, военной науки и других наук.
Информатика – фундаментальная научная и образовательная область, которая не может ограничиться рамками инженерных, пользовательских трактовок, рамками процедурного программирования, имея мощный формальный аппарат для глубокого изучения явлений и систем, их практической интерпретации, усиления междисциплинарных связей.
Информатика уже прошла этап "интуитивного (в своих понятиях, определениях, целях) развития", достаточно "теоретизировалась" и превратилась в полноценную фундаментальную естественнонаучную дисциплину, как, скажем, математика или физика.
Пример. В эпоху введения информатики в число образовательных дисциплин использовался больше программистский и пользовательский подход. Информатика, как правило, отождествлялась с процедурным программированием и решением задач на ЭВМ. Преподавалась информатика в школах и вузах – соответственно.
Если информатика рассматривается с узких позиций ее применения, применимости, то она выступает как техническая, технологическая среда общества, как средство обеспечения, например, коммуникационных потребностей общества.
Если информатика рассматривается с позиции передачи знаний, то она выступает как общекультурная среда и средство познания природы и общества.
Оба подхода должны быть взаимосвязаны.
Абсолютизация первого подхода приводит к различным технократическим перекосам, утопиям.
Абсолютизация второго подхода может привести к излишнему формализму и идеализации.
Дадим теперь рабочее (в данном курсе) определение информатики. Это определение не является ни полным, ни точным, ни формальным (дать такое определение – невозможно), но для вводного курса, как кажется автору, – вполне приемлемое.
Информатика – это междисциплинарная, методологическая наука об информационных процессах, о моделях, об алгоритмах и алгоритмизации, о программах и программировании, об исполнителях алгоритмов и различных исполняющих системах об их использовании в обществе, в природе, в познании.
Термин " информатика " (l’informatique) был введен французскими учеными и означает науку обработки информации(первоначально это была информация научно-технического, библиотечного характера) с помощью различных автоматических средств.
Во многих странах больше используется термин "computer science" (компьютерная наука, наука о компьютерах, точнее, наука о преобразовании информации с помощью компьютеров).
Предмет информатики точно невозможно определить – он сложный, многосторонний, динамичный.
Можно отметить три основные ветви информатики: теоретическую, практическую и техническую. Отметим, что делениеинформатики как науки и человеческой деятельности на те или иные части зависит от целей, задач, ресурсов рассматриваемой проблемы и часто оно бывает условным.
Теоретическая информатика ( brainware, "мозговое" обеспечение) изучает теоретические проблемы информационных сред.
Практическая, прикладная информатика ( software, "гибкое", программное обеспечение) изучает практические проблемы информационных сред.
Техническая информатика ( hardware, "тяжелое", аппаратное обеспечение) изучает технические проблемы информационных сред.
Пример. Задача построения математической модели прогноза кредитного риска банка – это задача теоретической информатики и экономики (естественно). Построение алгоритма прогноза по этой модели – задача теоретической информатики. Разработка компьютерной программы (комплекса программ) для прогноза риска – задача практической информатики.
Часто (особенно, в области практической информатики) говорят о предметной информатике, например, о медицинскойинформатике, физической информатике, компьютерной физике и т.д.
Пример. Определим предметы химической, медицинской, физической информатики. Химическая информатика изучает информационные процессы и системы в химических средах, проблемы управления в химических информационных структурах. Медицинская информатика изучает проблемы информационных процессов, а также управления в медицинских информационныхсистемах. Физическая информатика (иногда интерпретируемая как компьютерная физика) изучает проблемы информационных процессов, управления, вопросы самоорганизации, хаоса и порядка в открытых физических системах.
В любую предметную информатику, помимо предметных аспектов самой области, входят социально-правовые, эколого-экономические, гуманитарно-образовательные и философские аспекты.
Предметная область науки " информатика " – информационные системы, модели, языки их описания, технологии их актуализации.
Эти информационные процессы происходят как в живых организмах, так и в технических устройствах, в различных институтах общества, в индивидуальном и общественном сознании.
Информатика, как и математика, является наукой для описания и исследования проблем других наук. Она помогает прокладывать и усиливать междисциплинарные связи, исследовать проблемы различных наук с помощью своих идей, методов, технологий.
Фундаментальность информатике придает не только широкое и глубокое использование математики и других естественных наук, формальных методов и средств, но и общность, и фундаментальность ее результатов, их универсальная методологическая направленность в производстве знаний общества.
Мировоззренческая роль информатики состоит, в частности, в том, что она помогает вникать (особенно, в информационную) суть явлений, происходящих в окружающем нас мире, например, скрытых, не лежащих на поверхности, выявлять, описывать и исследовать как внешние, так и внутренние связи системы.
Воспитательная роль информатики состоит, в частности, в выработке исследовательского, творческого, алгоритмического подхода к делу, настойчивости, терпения и трудолюбия, аккуратности, логичности и строгости суждений, развитии умений выделять главное и игнорировать второстепенное, не влияющее на суть проблемы, ставить и исследовать новые задачи, использовать информационные технологии при решении разнообразных задач и др.
Культурная роль информатики состоит в частности в том, что повышение информационной и компьютерной культуры естественным образом, в соответствии с функциями информатики содействует повышению и профессиональной, и общей культуры (мышления, поведения, выбора). Информатика – это своего рода особая культура и искусство информационно-логического представления знаний.
Эстетическая роль информатики эстетика (наука о прекрасном) состоит, в частности, в сведении разрозненных элементов и связей исследуемой проблемы в целостную композицию, обладающую эстетическими качествами (красота, обаяние, цвет, форма, пропорция, симметрия, гармония, единство частей целого, удовольствие и др.), в сведении целого к ее частям с целью повышения эстетических качеств восприятия (в том числе и виртуального) процесса, явления.
Благодаря информатике развиваются языки наук, происходит их взаимообогащение, следовательно, и сами науки развиваются.
Информатика также обогащается новыми идеями и приложениями вследствие этого процесса, развивает и индустриализирует процесс получения, хранения и использования знаний.
Информатика широко используется как в традиционных, естественнонаучных областях (физика, биология, экономика и др.), так и в гуманитарных – истории, лингвистике, психологии, социологии и др.
Лекция 2
Информация ее представление и измерение
Аннотация: Рассматриваются основные понятия информатики – алфавит, слово, информация, сообщение, измерение сообщений и информации, виды и свойства информации, меры количества информации (по Хартли и Шеннону), их свойства и значение, вопросы связанные с информационными системами и управлением в системе.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Лекционный материал
Понятие информации является наиболее сложным для понимания и обычно во вводных курсах информатики не определяется, принимается как исходное базовое понятие, понимается интуитивно. Часто это понятие отождествляется неправильным образом с понятием "сообщение".
Понятие "информация" имеет различные трактовки в разных предметных областях. Например, информация может пониматься как:
абстракция, абстрактная модель рассматриваемой системы (в математике);
сигналы для управления, приспособления рассматриваемой системы (в кибернетике);
мера хаоса в рассматриваемой системе (в термодинамике);
вероятность выбора в рассматриваемой системе (в теории вероятностей);
мера разнообразия в рассматриваемой системе (в биологии) и др.
Рассмотрим это фундаментальное понятие информатики на основе понятия "алфавит" ("алфавитный", формальный подход). Дадим формальное определение алфавита.
Алфавит – конечное множество различных знаков, символов, для которых определена операция конкатенации (приписывания, присоединения символа к символу или цепочке символов); с ее помощью по определенным правилам соединения символов и слов можно получать слова (цепочки знаков) и словосочетания (цепочки слов ) в этом алфавите (над этим алфавитом ).
Буквой или знаком называется любой элемент x алфавита X, где . Понятие знака неразрывно связано с тем, что им обозначается ("со смыслом"), они вместе могут рассматриваться как пара элементов (x, y), где x – сам знак, а y – обозначаемое этим знаком.
Пример. Примеры алфавитов: множество из десяти цифр, множество из знаков русского языка, точка и тире в азбуке Морзе и др. Валфавите цифр знак 5 связан с понятием "быть в количестве пяти элементов".
Конечная последовательность букв алфавита называется словом в алфавите (или над алфавитом ).
Длиной |p| некоторого слова p над алфавитом Х называется число составляющих его букв.
Слово (обозначаемое символом ) имеющее нулевую длину, называется пустым словом: | | = 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
Отсюда получаем систему двух алгебраических уравнений:
или, решая эту систему, окончательно получаем, x = –76,5, у = –56,5.
Для измерения информации используются различные подходы и методы, например, с использованием меры информации по Р. Хартли и К. Шеннону.
Количество информации – число, адекватно характеризующее разнообразие (структурированность, определенность, выбор состояний и т.д.) в оцениваемой системе. Количество информации часто оценивается в битах, причем такая оценка может выражаться и в долях бит (так как речь идет не об измерении или кодировании сообщений ).
Мера информации – критерий оценки количества информации. Обычно она задана некоторой неотрицательной функцией, определенной на множестве событий и являющейся аддитивной, то есть мера конечного объединения событий (множеств) равна сумме мер каждого события.
Рассмотрим различные меры информации.
Возьмем меру Р. Хартли. Пусть известны N состояний системы S ( N опытов с различными, равновозможными, последовательными состояниями системы). Если каждое состояние системы закодировать двоичными кодами, то длину кода dнеобходимо выбрать так, чтобы число всех различных комбинаций было бы не меньше, чем N:
Логарифмируя это неравенство, можно записать:
Наименьшее решение этого неравенства или мера разнообразия множества состояний системы задается формулой Р. Хартли:
H = log2N ( бит ).
Пример. Чтобы определить состояние системы из четырех возможных состояний, то есть получить некоторую информацию о системе, необходимо задать 2 вопроса. Первый вопрос, например: "Номер состояния больше 2?". Узнав ответ ("да", "нет"), мы увеличиваем суммарную информацию о системе на 1 бит ( I = log22 ). Далее необходим еще один уточняющий вопрос, например, при ответе "да": "Состояние – номер 3?". Итак, количество информации равно 2 битам ( I = log24 ). Если система имеет n различных состояний, то максимальное количество информации равно I = log2n .
Если во множестве X = {x1, x2, ..., xn} искать произвольный элемент, то для его нахождения (по Хартли) необходимо иметь не менее logan (единиц) информации.
Уменьшение Н говорит об уменьшении разнообразия состояний N системы.
Увеличение Н говорит об увеличении разнообразия состояний N системы.
Мера Хартли подходит лишь для идеальных, абстрактных систем, так как в реальных системах состояния системы неодинаково осуществимы (неравновероятны).
Для таких систем используют более подходящую меру К. Шеннона. Мера Шеннона оценивает информацию отвлеченно от ее смысла:
где 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 (эрг/град)
и выражение ( формула Больцмана ) для энтропии или меры хаоса в термодинамической системе:
Сравнивая выражения для I и S, можно заключить, что величину I можно понимать как энтропию из-за нехватки информации в системе (о системе).
Основное функциональное соотношение между энтропией и информацией имеет вид:
I+S(log2e)/k=const.
Из этой формулы следуют важные выводы:
увеличение меры Шеннона свидетельствует об уменьшении энтропии (увеличении порядка) системы;
уменьшение меры Шеннона свидетельствует об увеличении энтропии (увеличении беспорядка) системы.
Положительная сторона формулы Шеннона – ее отвлеченность от смысла информации. Кроме того, в отличие от формулы Хартли, она учитывает различность состояний, что делает ее пригодной для практических вычислений. Основная отрицательная сторонаформулы Шеннона – она не распознает различные состояния системы с одинаковой вероятностью.
Методы получения информации можно разбить на три большие группы.
Эмпирические методы или методы получения эмпирических данных.
Теоретические методы или методы построения различных теорий.
Эмпирико-теоретические методы (смешанные) или методы построения теорий на основе полученных эмпирических данных об объекте, процессе, явлении.
Охарактеризуем кратко эмпирические методы.
Наблюдение – сбор первичной информации об объекте, процессе, явлении.
Сравнение – обнаружение и соотнесение общего и различного.
Измерение – поиск с помощью измерительных приборов эмпирических фактов.
Эксперимент – преобразование, рассмотрение объекта, процесса, явления с целью выявления каких-то новых свойств.
Кроме классических форм их реализации, в последнее время используются опрос, интервью, тестирование и другие.
Охарактеризуем кратко эмпирико-теоретические методы.
Абстрагирование – выделение наиболее важных для исследования свойств, сторон исследуемого объекта, процесса, явления и игнорирование несущественных и второстепенных.
Анализ – разъединение целого на части с целью выявления их связей.
Декомпозиция – разъединение целого на части с сохранением их связей с окружением.
Синтез – соединение частей в целое с целью выявления их взаимосвязей.
Композиция соединение частей целого с сохранением их взаимосвязей с окружением.
Индукция – получение знания о целом по знаниям о частях.
Дедукция – получение знания о частях по знаниям о целом.
Эвристики, использование эвристических процедур – получение знания о целом по знаниям о частях и по наблюдениям, опыту, интуиции, предвидению.
Моделирование (простое моделирование), использование приборов – получение знания о целом или о его частях с помощью модели или приборов.
Исторический метод – поиск знаний с использованием предыстории, реально существовавшей или же мыслимой.
Логический метод – поиск знаний путем воспроизведения частей, связей или элементов в мышлении.
Макетирование – получение информации по макету, представлению частей в упрощенном, но целостном виде.
Актуализация – получение информации с помощью перевода целого или его частей (а следовательно, и целого) из статического состояния в динамическое состояние.
Визуализация – получение информации с помощью наглядного или визуального представления состояний объекта, процесса, явления.
Кроме указанных классических форм реализации теоретико-эмпирических методов часто используются и мониторинг (система наблюдений и анализа состояний), деловые игры и ситуации, экспертные оценки (экспертное оценивание), имитация (подражание) и другие формы.
Охарактеризуем кратко теоретические методы.
Восхождение от абстрактного к конкретному – получение знаний о целом или о его частях на основе знаний об абстрактных проявлениях в сознании, в мышлении.
Идеализация – получение знаний о целом или его частях путем представления в мышлении целого или частей, не существующих в действительности.
Формализация – получение знаний о целом или его частях с помощью языков искусственного происхождения (формальное описание, представление).
Аксиоматизация – получение знаний о целом или его частях с помощью некоторых аксиом (не доказываемых в данной теории утверждений) и правил получения из них (и из ранее полученных утверждений) новых верных утверждений.
Виртуализация – получение знаний о целом или его частях с помощью искусственной среды, ситуации.
Пример. Для построения модели планирования и управления производством в рамках страны, региона или крупной отрасли нужно решить следующие проблемы:
определить структурные связи, уровни управления и принятия решений, ресурсы; при этом чаще используются методы наблюдения, сравнения, измерения, эксперимента, анализа и синтеза, дедукции и индукции, эвристический, исторический илогический методы, макетирование и др.;
определить гипотезы, цели, возможные проблемы планирования; наиболее используемые методы – наблюдение, сравнение, эксперимент, абстрагирование, анализ, синтез, дедукция, индукция, эвристический, исторический, логический и др.;
конструирование эмпирических моделей; наиболее используемые методы – абстрагирование, анализ, синтез, индукция, дедукция, формализация, идеализация и др.;
поиск решения проблемы планирования и просчет различных вариантов, директив планирования, поиск оптимального решения; используемые чаще методы – измерение, сравнение, эксперимент, анализ, синтез, индукция, дедукция, актуализация, макетирование, визуализация, виртуализация и др.
Суть задачи управления системой – отделение ценной информации от "шумов" (бесполезного, иногда даже вредного для системы возмущения информации ) и выделение информации, которая позволяет этой системе существовать и развиваться.
Информационная система – это система, в которой элементы, структура, цель, ресурсы рассматриваются на информационном уровне (хотя, естественно, имеются и другие уровни рассмотрения).
Информационная среда – это среда (система и ее окружение) из взаимодействующих информационных систем, включая иинформацию, актуализируемую в этих системах.
Установление отношений и связей, описание их формальными средствами, языками, разработка соответствующих описаниям моделей, методов, алгоритмов, создание и актуализация технологий, поддерживающих эти модели и методы, и составляет основную задачу информатики как науки, образовательной области, сферы человеческой деятельности.
Информатику можно определить как науку, изучающую неизменные сущности (инварианты) информационных процессов, которые протекают в различных предметных областях, в обществе, в познании, в природе.
Лекция 3
Кодирование и шифрование информации
Аннотация: Рассматриваются основные понятия кодирования и шифрования информации, защиты информации и антивирусной защиты.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Лекционный материал
В современном обществе успех любого вида деятельности сильно зависит от обладания определенными сведениями (информацией) и от отсутствия их (ее) у конкурентов. Чем сильней проявляется указанный эффект, тем больше потенциальные убытки от злоупотреблений в информационной сфере и тем больше потребность в защите информации. Одним словом, возникновение индустрии обработки информации привело к возникновению индустрии средств ее защиты и к актуализации самой проблемы защиты информации, проблемы информационной безопасности.
Одна из наиболее важных задач (всего общества) – задача кодирования сообщений и шифрования информации.
Вопросами защиты и скрытия информации занимается наука к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
Системы счисления и действия в них
Аннотация: Рассматриваются основные понятия числовых систем, правила их построения, выполнение действия в них.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Лекционный материал
Алфавит Х из р символов и правила записи (изображения) и обработки чисел с помощью символов этого алфавита называются системой счисления (нумерацией) с основанием р. Число х в системе с основанием р обозначается как (х)р или хр .
Любая система счисления – это система кодирования числовых величин (количеств), позволяющая выполнять операциикодирования и декодирования, то есть по любой количественной величине однозначно находить его кодовое представление и по любой кодовой записи – восстанавливать соответствующую ей числовую величину.
Все системы счисления строятся по общему принципу: определяется величина р – основание системы, а любое число хзаписывается в виде комбинации степеней веса р от 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 .
Процедура перевода десятичных чисел в р-ную систему счисления:
перевести отдельно целую часть числа х, для чего последовательно делить сперва целую часть [х]10 , а затем все частные (получаемые при делении) на р до тех пор, пока не получим в очередном частном число меньшее р ; изображение [х]pполучается последовательным приписыванием к последнему частному остатков от деления – от последнего до первого;
перевести отдельно дробную часть (мантиссу) числа, то есть {x}10 , для чего последовательно умножать сперва исходную мантиссу, а затем мантиссы получаемых чисел на р до тех пор, пока не получим мантиссу, равную нулю, или нужное количество цифр в {х}p ; изображение {х}p получается приписыванием к целой части первого произведения второй такой же цифры и т.д., до последней цифры целой части;
результат будет иметь вид (х)р = [х]p, {х}p .
Пример. Найти: 12,810 = ?2 . Решение:
Переводим целую часть: 1210 =11002;
переводим дробную часть: 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 ;
результат перевода: 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-ную или из нее – группировать их в четверки битов. Можно добавлять, если нужно, незначащие нули (слева от целой части и справа от мантиссы) или отбрасывать их.
Пример. Рассмотрим переводы в смешанных системах.
Из 2-ной системы в 8-ную (двоично-восьмеричное изображение):
из 8-ной системы в 2–ную (восьмерично-двоичное изображение):
из 2-ной системы в 16-ную (двоично-шестнадцатеричное изображение):
из 16-ной системы в 2-ную (шестнадцатерично-двоичное изображение):
Сложение в двоичной системе счисления осуществляется по правилам
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 ).
Дополнительный код = обратный код + единица в младшем разряде.
Вычитание с помощью дополнительного кода: найти дополнительный код вычитаемого такой же разрядности, как и уменьшаемое, и сложить этот код с уменьшаемым. Результатом вычитания будет полученная сумма без учета старшего разряда (отбрасывается).
Пример. Выполним вычитание напрямую и через сложение (через дополнительный код ):
Целые числа в математике и их аналоги в n-разрядных арифметиках тождественны (по количеству) в рамках их представления с этой разрядностью. При этом можно отметить основные отличия представления чисел в поле памяти человека и в поле памяти n-разрядной арифметики:
бесконечное и счетное множество целых чисел представляется отрезком [–N; +N], где N – максимальное число, представимое в этой арифметике (многоточие – общее число единиц, равное n ): N = (111 . . . 1)2 ;
бесконечное и несчетное множество действительных чисел , располагающееся на числовой оси равномерно и плотно, представляется в n-разрядной арифметике множеством с неравномерной плотностью (сгущение у нуля и сжатость со стороны меньших чисел);
нуль во множестве действительных чисел в любой своей окрестности имеет множество чисел, а нуль в n-разрядной арифметике представлен изолированно.
С точки зрения обычной арифметики, например, в интервале (–1; 1) имеется бесконечное множество "плотно" расположенных точек, причем в любой окрестности каждой такой точки имеется хотя бы одна точка из этого множества. Такую арифметику называют часто регулярной арифметикой. Машинная же арифметика имеет следующие особенности. Она нерегулярна – точки интервала сгущаются около нуля; кроме того, в этом интервале точка х "изолирована" – если взять любую ее окрестность (х – а; х + а), где а – число, которое не превосходит машинного нуля (наименьшего представимого в машине числа), то в этом интервале нет других точек (отличных от х ). Говоря языком теории вероятности, плотности распределения чисел в регулярной и нерегулярной арифметике – различны, как, впрочем, плотности распределения целых и вещественных чисел в одной и той же арифметике. Множество вещественных чисел в машинной арифметике представляется как подмножество(определяемое разрядностью арифметики) множества рациональных чисел. Есть и другие особенности этих множеств (связанные, например, с выполнением операций), но указанные выше особенности – основные.
Различия в представлении чисел в обычной и в машинной (n-разрядной) арифметике ограничивают как "математические" возможности компьютера, так и "компьютерные" возможности математики, использование математических методов, алгоритмов в компьютерах.
Нужно всегда иметь в виду, что точность в теоретической математике – понятие абстрактное, и в практической математике может возникать иллюзия точности там, где ее на самом деле нет, – если нет корректной договоренности о пределах возможных значений неизбежных погрешностей в рамках рассматриваемых вычислительных ресурсов, например, трудоемкости и времени, а также не оговорена стратегия управления этой погрешностью.
Так как диапазон n-разрядных чисел системы счисления с основанием p находится в пределах , то для представления дробных чисел этот диапазон еще снижается, поскольку часть разрядов необходимо отвести под изображение мантиссы. Таким образом, имеются так называемые "зоны нечувствительности" форм представления чисел в n-разрядных арифметиках.
В 1937 году Конрадом Цузе для увеличения диапазона чисел, представимых в арифметике двоичных чисел, а также для повышения точности этого представления чисел было предложено представление чисел в плавающей, нормализованной форме – число x представляется в виде: , где m – мантисса числа, k – целый порядок числа, .
Пусть даны два числа: и ( ). Тогда можно проверить, что результаты выполнения операций будут равны:
Если из n разрядов, отводимых под изображение чисел, m двоичных разрядов отвести под мантиссу, k – под порядок, один разряд – под знак числа и один разряд – под знак порядка (например, 0 – плюс, 1 – минус), то диапазон представимых в форме с плавающей запятой чисел резко увеличивается ( m + k + 2 = n ):
(многоточие соответствует k единицам).
Числа, меньшие нижней границы положительных чисел и большие верхней границы отрицательных чисел, считаются равными нулю, не различаются между собой. Числа, большие верхней границы положительных чисел, полагаются равными положительной бесконечности (меньшие нижней границы отрицательных – отрицательной бесконечности). Сравнение двух разных по величине чисел в арифметике с ограниченной разрядностью может поэтому приводить к неверному результату, как и сравнение двух равных в таких системах чисел с точки зрения математической.
Такое представление очень удобно для хранения в ЭВМ, так как на самом деле необходимо хранить не само число, а его знак, мантиссу, порядок и знак порядка, и все операции с числами сводятся к операциям с этими объектами. Операции же с этими объектами просты: сравнение знаков, увеличение, уменьшение порядка, сложение мантисс, нормализация, то есть в конечном итоге сводятся к достаточно просто реализуемым операциям сдвига, выравнивания, сравнения разрядов.
Пример. Вычислить наибольшее и наименьшее 5-разрядное целое число в системе счисления с основанием 3. Наибольшее целое n-разрядное число, которое возможно записать в системе счисления с основанием р, равно:
Наименьшее целое n-разрядное число в этой системе равно
.
Таким образом, в системе счисления с основанием 3 и числом разрядов 5 представим диапазон следующих чисел:
Формулам можно придать более компактный вид. Например, для двоичной системы
а в восьмеричной системе счисления эти числа
К "неудобствам" этой формы представления чисел можно отнести возможность возникновения следующих "особо опасных" ситуаций:
если число достаточно мало, например, а = 0.12Е + 00, то оно может быть представлено любым числом из наименьшего интервала включающего а, в частности числом 0.120000001 или 0.199999999 и в этом случае сравнивать на равенство "в лоб" нельзя (вещественные числа в форме с плавающей запятой опасно сравнивать на совпадение);
порядок выполнения операций может влиять на результат, например, в 4-разрядной арифметике с фиксированной запятой 20.0000 + 0.0001 = 20.0001, но при этом 0.2000Е + 02 + 0.1000Е – 05 = 0.2000Е + 02 ;
может возникнуть так называемая ситуация "переполнения порядка" при сложении (умножении) очень больших чисел или "исчезновения порядка" при сложении (умножении) "очень малых чисел", в частности, 0.6000Е + 39 x0.1200Е + 64 = 0.9999Е + 99 (или же не определено), а также 0.6000Е – 35 x 0.0200Е – 65 = 0.9999Е – 99 (или же не определено), при соответствующим образом определенной разрядности десятичной арифметики;
при сложении чисел с плавающей запятой (а, в конечном счете, все операции выполняются через сложение) происходит выравнивание порядков для последующего сложения мантисс, а при выравнивании степеней может происходить потеря (усечение) младших разрядов, например, такая ситуация может возникнуть при сложении одного "очень большого числа" с одним "очень малым числом"
Есть много различных способов (часто искусственных) формирования систем чисел.
Пример. В факториальной системе счисления целые числа записывают линейной комбинацией факториалов, например, . Эта система (условно) позиционна. Так как 0! = 1! = 1, то два младших разряда n-разрядного числа в разложении этого числа по факториалам представимы как ! и поэтому веса этих разрядов не зависят от позиции (поэтому при это число можно считать непозиционным лишь условно). Формула перевода из факториальной системы счисления в десятичную систему:
История развития систем счисления достаточно интересна. Приведем лишь некоторые факты. Счет вначале велся с помощью пальцев рук (пятерками и затем – десятками). В некоторых странах сохранился счет с основанием 12 (например, Великобритания – 12 шиллингов) и 20 (например, Франция – "quatre–vingts" или "четыре-двадцать" то есть 80; у древних адыгов счет велся аналогично: "тощIищ", то есть "двадцать-три" – 60) и др.
Лекция 5
Высказывания и предикаты
Аннотация: Рассматриваются основные понятия и сведения алгебры высказываний и предикатов – высказывания, предикаты, аксиомы, логические выражения и функции, эквивалентные выражения и приведение к эквивалентному выражению, другие сопутствующие понятия и факты логики, а также инфологические задачи.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Лекционный материал
Информатика, как было рассмотрено выше, изучает знаковые (алфавитные) системы. Алгебра – наиболее адекватный математический аппарат описания действий в них, поэтому алгебраический аппарат наилучшим образом подходит для описания информационных систем общей природы, отвлеченно от их предметной направленности. Информационные процессы хорошо формализуются с помощью различных алгебраических структур.
Алгеброй A называется некоторая совокупность определенных элементов X, с заданными над ними определенными операциямиf (часто определяемые по сходству с операциями сложения и умножения чисел), которые удовлетворяют определенным свойствам – аксиомам алгебры.
Операция f называется n-местной, если она связывает n операндов (объектов – участников этой операции).
Совокупность операций алгебры A называется ее сигнатурой, а совокупность элементов алгебры – носителем алгебры.
Утверждение ( высказывательная форма ) – основная единица, неделимая с точки зрения отражения смысла информации (семантики).
Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать ("сразу посмотрев на него"), истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "истина" и "ложь", "true" и "fаlse" или "1" и "0".
Переменная, значениями которой могут быть лишь значения "1" или "0", называется логической переменной или булевой переменной.
Пример. Рассмотрим словосочетания:
Москва – столица США.
Житель города Москва.
5 – 7 + 8.
5 – 9 + 28 = 4.
В пятую неделю зимы было очень холодно.
В Антарктиде живут тигры.
Высказывание должно быть однозначно истинным или однозначно ложным, поэтому высказываниями являются только утверждения 1), 4), 6).
Пример. Не является высказыванием и "парадокс лжеца" (Эвбулид, учитель Демосфена, около 350 лет до н.э.): "То, что я сейчас утверждаю, – ложно", ибо если оно истинно – то оно ложно, а если допустить, что оно ложно, то оно истинно. Это неопределенная высказывательная форма. Аналогичный пример принадлежит известному математику, логику Гёделю (1931 г.): "То, что утверждается в этом предложении, не может быть доказано". Если его можно опровергнуть, то его нельзя доказать, а если его нельзя опровергнуть, то его можно доказать. Предложения такого рода не могут быть доказаны или опровергнуты в пределах того языка (той теории, алгебры ), с помощью которой они сформулированы. Известны многие подобные парадоксы.
Рассматривая высказывания, мы не обращаем внимания на их внутреннюю структуру и можем разлагать их на структурные части, равно как и объединять их.
Пример. Построим из ниже заданных простых высказываний составные, сложные высказывания, принимающие значение "истина","ложь":
"Зима – холодное время года".
"Пальто – теплая одежда".
"Камин – источник тепла".
Истинным будет, например, сложное высказывание: "Зима – холодное время года и зимой носят пальто", а ложным будет, например, высказывание: "Некоторые ходят в пальто, поэтому на улице зима". Придумайте другие примеры.
Предикат – высказывательная форма с логическими переменными (множество значений этих переменных вполне определено), имеющая смысл при любых допустимых значениях этих переменных. Количество переменных в записи предиката называется егоместностью.
Простые высказывания или предикаты не зависят от других высказываний или предикатов ("не разбиваемы на более простые"), а сложные – зависят хотя бы от двух простых.
Пример. Выражение "х = у" – предикат, "х > 5" – предикат, а "7 > 5" – высказывание. Утверждение "Хорошо" не являетсявысказыванием, утверждение "Оценка студента А по информатике – хорошая" – простое высказывание, утверждение "Вчера была ясная погода, я был вчера на рыбалке" – сложное высказывание, состоящее из двух простых.
Логической (булевой) функцией f(х) называется некоторая функциональная зависимость, в которой аргумент х – логическаяпеременная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}.
Пример. Заданы предикаты вида р = "число х делится нацело на 3" и q = "у – день недели". Найдем множество истинностипредикатов р и q, если , . Получаем, что , .
Множество логических переменных с определенными над ним операциями: – отрицания или инверсии, – логического сложения или дизъюнкции, – логического умножения или конъюнкции называется алгебройпредикатов (и высказываний ) , если эти операции удовлетворяют следующим аксиомам:
Аксиома двойного отрицания:
Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции ):
Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов):
Аксиомы одинаковых операндов:
Аксиомы поглощения (множителем множителя-суммы или слагаемым слагаемого-произведения):
Аксиомы распределения операции ( дизъюнкции относительно конъюнкции и наоборот):
Аксиомы де Моргана (перенесения бинарной операции на операнды):
Аксиомы нейтральности (взаимноинверсных множителей или слагаемых):
Аксиома существования единицы ( истина, true, 1) и нуля ( ложь, false, 0), причем,
Из этих аксиом следует ряд полезных соотношений, например,
Три базовые операции алгебры предикатов определяются таблицей их значений, так как в алгебре предикатов из-за дискретности значений логических функций часто используется табличная форма задания функции. Булеву функцию n переменных можно полностью определить таблицей из 2n строк.
Пример. Составим таблицу истинности функции
Следовательно, функция тождественно-истинна. Это можно было доказать (проверить) и с помощью аксиом:
Пример. Заполним таблицу истинности трехместной логической функции
Пример. Изобразим графически множество истинности двухместного предиката вида р(х,у) = "модуль числа х равен модулю числа у", если задана область изменения аргументов: . Имеем соотношение
Смысл предикатов р1(х,у) и р2(х,у) очевиден. Множество изображается графиком функции y=|x|, который дан на [ Cкачайте файл, чтобы посмотреть ссылку ]:
Рис. 5.1. График функции y = |x|
Кроме указанных трех базовых операций можно с их помощью ввести еще следующие важные операции алгебры предикатов (можно их назвать небазовыми операциями):
импликации: ;
эквиваленции: .
Операции импликации и эквиваленции, хотя и являются часто используемыми, но не базовые, ибо они определяемы через три введенные выше базовые операции. Нетрудно определить их таблицы истинности (проделайте это самостоятельно с помощью правых частей приведенных равенств).
При выполнении логических операций в компьютере они сводятся к поразрядному сравнению битовых комбинаций. Эти операции достаточно быстро (аппаратно) выполняемы, так как сводятся к выяснению совпадения или несовпадения битов.
В логических формулах определено старшинство операций, например: скобки, отрицание, конъюнкция, дизъюнкция (остальные, небазовые операции пока не учитываем).
Всегда истинные формулы называют тавтологиями.
Логические функции эквивалентны, если совпадают их таблицы истинности, то есть совпадают области определения и значения, а также сами значения функции при одних и тех же наборах переменных из числа всех допустимых значений. Если это совпадение происходит на части множества допустимых значений, то формулы называются эквивалентными лишь на этой части (на этом подмножестве).
Задача упрощения логического выражения состоит в преобразовании его к более простому (по числу переменных, операций или операндов) эквивалентному выражению. Наиболее простой вид получается при сведении функции к постоянной – 1 ( истина ) или 0 ( ложь ).
Пример. Упростим:
Задача доказательства равенства двух логических выражений (функций) состоит в установлении эквивалентности этих функций на некотором множестве значений всех переменных, входящих в данную функцию.
Пример. Докажем равенство логических выражений: Используя аксиомы алгебры предикатов, получаем равенства
Левая часть равенства приведена к правой части, то есть данное равенство доказано полностью.
Такие задачи решаются с помощью аксиом алгебры предикатов одним из следующих способов:
правая часть равенства приводится к левой части;
левая часть равенства приводится к правой части;
обе части равенства приводятся к третьему выражению.
Логические функции позволяют эффективно решать так называемые инфологические (информационно-логические) задачи, доказывать утверждения.
Информационно-логическая (инфологическая) задача – это задача, в которой необходимо установить некоторые информационные или логические связи и сделать необходимые причинно-следственные логические выводы. Эти задачи возникают в различных областях и часто являются плохо формализованными и структурированными. Их нужно хорошо формализовать и структурировать. Насколько хорошо будет возможно это сделать – настолько хорошо и полно будет решена рассматриваемая проблема или задача. Рассмотрим пример информационно-логической задачи (например, решаемой следователем, знакомым с алгеброй предикатов ).
Пример. Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. В ходе следствия Браун сказал, что преступники были на синем "Бьюике", Джонс сказал, что это был черный "Крайслер", Смит утверждал, что это был "Форд", но не синий. Каждый указал неправильно либо марку, либо цвет автомобиля. Определим истинный цвет и истинную марку автомобиля. Рассмотрим простые высказывания вида: х = "машина – синяя", у = "машина – Бьюик", z = "машина – черная", u = "машина – Крайслер", v = "машина – Форд". На их основе высказывание Брауна можно записать в виде сложного логического выражения вида , высказывание Джонса – в виде , а высказывание Смита – в виде Так как в каждом из этих выражений одна из переменных принимает значение "истина", то истинны и дизъюнкции вида: . По определению конъюнкции, . Это выражение мы взяли из-за однозначности равенства 1 конъюнкции и неоднозначности (многовариантности) его равенства нулю. Упростим выражение:
Мы использовали тот факт, что одновременно не могут быть истинными два высказывания относительно цвета или два высказывания относительно марки машины. Так как конъюнкция истинна только тогда, когда , то заключаем, что автомобиль был черным "Бьюиком".
Законы алгебры высказываний и предикатов сходны с правилами, по которым человек делает умозаключения, доказывает, мыслит.
Пример. Операции конъюнкции, дизъюнкции, отрицания алгебры высказываний – аналоги союзов "и", "или", приставки "не", используемых (возможно, интуитивно) при выражении мысли человеком.
Чтобы переложить на ЭВМ работы мыслительного характера, эти правила необходимо строго сформулировать, формализовать. Это позволяет осуществить алгебра логики. Приведем некоторые аксиомы логики – науки, изучающей методы доказательства и опровержения утверждений.
Аксиома исключения третьего : либо имеет место высказывание, либо его отрицание.
Аксиома противоречия : высказывания и его отрицание не могут иметь места одновременно.
Аксиома двойного отрицания : двукратное отрицание какого-либо утверждения равносильно исходному утверждению.
Аксиома тождества : всякое высказывание тождественно самому себе.
Если высказывания x и y связаны друг с другом отношением , то говорят, что высказывание y следует из высказывания x (или y – следствие x ); если множество истинности Х высказывания х содержит множество истинности Y высказывания y, товысказывание x – условие, высказывание y – заключение, а само соотношение – вывод.
Доказательство формальных математических утверждений (теорем) – последовательность корректных выводов, ведущих от условия к заключению. Алгебра логики помогает доказывать теоремы (дает общие подходы и методы доказательства).
Общий подход к доказательству теорем методом от противного, обратных и противоположных теорем можно формализовать с помощью алгебры логики.
Лекция 6
Логические вентили, схемы, структуры
Аннотация: Рассматриваются основные теоретические (математические, логические) понятия и сведения, касающиеся базовых логических элементов и структур – логических вентилей, логических (переключательных) схем, логической базы аппаратуры ЭВМ и их оптимальной структуры, оптимизации их структур.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Лекционный материал
Любой, самый примитивный компьютер – сложнейшее техническое устройство. Но даже такое сложное устройство, как и все в природе и в технике, состоит из простейших элементов. Любой компьютер, точнее, любой его электронный логический блок состоит из десятков и сотен тысяч так называемых вентилей (логических устройств, базовых логических схем ), объединяемых по правилам и законам (аксиомам) алгебры вентилей в схемы, модули.
Логический вентиль (далее – просто вентиль) – это своего рода атом, из которого состоят электронные узлы ЭВМ. Он работает по принципу крана (отсюда и название), открывая или закрывая путь сигналам.
Логические схемы предназначены для реализации различных функций алгебры логики и реализуются с помощью трех базовых логических элементов ( вентилей, логических схем или так называемых переключательных схем ). Они воспроизводят функции полупроводниковых схем.
Работу вентильных, логических схем мы, как и принято, будем рассматривать в двоичной системе и на математическом, логическом уровне, не затрагивая технические аспекты (аспекты микроэлектроники, системотехники, хотя они и очень важны в технической информатике).
Логические функции отрицания, дизъюнкции и конъюнкции реализуют, соответственно, логические схемы, называемыеинвертором, дизъюнктором и конъюнктором.
Логическая функция "инверсия", или отрицание, реализуется логической схемой ( вентилем ), называемой инвертор.
Принцип его работы можно условно описать следующим образом: если, например, "0" или "ложь" отождествить с тем, что на вход этого устройства скачкообразно поступило напряжение в 0 вольт, то на выходе получается 1 или "истина", которую можно также отождествить с тем, что на выходе снимается напряжение в 1 вольт.
Аналогично, если предположить, что на входе инвертора будет напряжение в 1 вольт ("истина"), то на выходе инвертора будет сниматься 0 вольт, то есть "ложь" ( схемы на [ Cкачайте файл, чтобы посмотреть ссылку ].
Рис. 6.1. Принцип работы инвертора
Функцию отрицания можно условно отождествить с электрической схемой соединения в цепи с лампочкой ([ Cкачайте файл, чтобы посмотреть ссылку ]), в которой замкнутая цепь соответствует 1 ("истина") или х = 1, а размыкание цепи соответствует 0 ("ложь") или х = 0.
Рис. 6.2. Электрический аналог схемы инвертора
Дизъюнкцию реализует логическое устройство ( вентиль ) называемое дизьюнктор (рис. [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]):
Рис. 6.3a.
Рис. 6.3b.
Рис. 6.3c. Принцип работы дизъюнктора
Дизъюнктор условно изображается схематически электрической цепью вида ([ Cкачайте файл, чтобы посмотреть ссылку ])
Рис. 6.4. Электрический аналог схемы дизъюнктора
Конъюнкцию реализует логическая схема ( вентиль ), называемая конъюнктором (рис. [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]):
Рис. 6.5a.
Рис. 6.5b.
Рис. 6.5c. Принцип работы конъюнктора
Конъюнктор можно условно изобразить схематически электрической цепью вида ([ Cкачайте файл, чтобы посмотреть ссылку ])
Рис. 6.6. Электрический аналог схемы конъюнктора
Схематически инвертор, дизъюнктор и конъюнктор на логических схемах различных устройств можно изображать условно следующим образом ([ Cкачайте файл, чтобы посмотреть ссылку ]). Есть и другие общепринятые формы условных обозначений.
Рис. 6.7. а, б, в. Условные обозначения вентилей (вариант)
Пример. Транзисторные схемы, соответствующие логическим схемам ( инвертор ), ( дизъюнктор ), ( конъюнктор ) имеют, например, следующий вид (рис. [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]):
Рис. 6.8a. Инвертор
Рис. 6.8b. Дизъюнктор
Рис. 6.8c. Конъюнктор
Из указанных простейших базовых логических элементов собирают, конструируют сложные логические схемы ЭВМ, например, сумматоры,шифраторы, дешифраторы и др. Большие (БИС) и сверхбольшие (СБИС) интегральные схемы содержат в своем составе (на кристалле кремния площадью в несколько квадратных сантиметров) десятки тысяч вентилей. Это возможно еще и потому, что базовый набор логических схем (инвертор, конъюнктор, дизъюнктор ) является функционально полным (любую логическую функцию можно представить через эти базовыевентили ), представление логических констант в них одинаково (одинаковы электрические сигналы, представляющие 1 и 0) и различные схемы можно "соединять" и "вкладывать" друг в друга (осуществлять композицию и суперпозицию схем).
Таким способом конструируются более сложные узлы ЭВМ – ячейки памяти, регистры, шифраторы, дешифраторы, а также сложнейшиеинтегральные схемы.
Пример. В двоичной системе таблицу суммирования цифры x и цифры y и получения цифры z с учетом переноса p в некотором разряде чисел x и y можно изобразить таблицей
Эту таблицу можно интерпретировать как совместно изображаемую таблицу логических функций (предикатов) вида
Логический элемент, соответствующий этим функциям, называется одноразрядным сумматором и имеет следующую схему (обозначим ее как или – если мы хотим акцентировать именно выбранный, текущий i-й разряд) ([ Cкачайте файл, чтобы посмотреть ссылку ]:
Рис. 6.9. Схема одноразрядного сумматора
Пример. "Черным ящиком" называется некоторое закрытое устройство (логическая, электрическая или иная схема), содержимое которого неизвестно и может быть определено (идентифицировано) только по отдельным проявлениям входа/выхода ящика (значениям входных и выходных сигналов). В "черном ящике" находится некоторая логическая схема, которая в ответ на некоторую последовательность входных (для ящика) логических констант выдает последовательность логических констант, получаемых после выполнения логической схемы внутри "черного ящика". Определим логическую функцию внутри "черного ящика" ([ Cкачайте файл, чтобы посмотреть ссылку ]), если операции выполняются с логическими константами для входных последовательностей (поразрядно). Например, х = 00011101 соответствует последовательности поступающих значений: "ложь", "ложь", "ложь", "истина", "истина", "истина", "ложь", "истина".
Рис. 6.10. Схема "черного ящика 1"
Из анализа входных значений (входных сигналов) х, у и поразрядного сравнения логических констант в этих сообщениях с константами в значении z – результате выполнения функции в "черном ящике", видно, что подходит, например, функция вида
Действительно, в результате "поразрядного" сравнения сигналов (последовательностей значений "истина", "ложь") получаем следующие выражения (последовательности логических констант):
Пример. Попробуйте самостоятельно выписать функцию для "черного ящика"? указанного на [ Cкачайте файл, чтобы посмотреть ссылку ]:
Рис. 6.11. Схема "черного ящика 2"
Важной задачей (технической информатики) является минимизация числа вентилей для реализации той или иной схемы (устройства), что необходимо для более рационального, эффективного воплощения этих схем, для большей производительности и меньшей стоимости ЭВМ.
Эту задачу решают с помощью методов теоретической информатики (методов булевой алгебры).
Пример. Построим схему для логической функции
Схема, построенная для этой логической функции, приведена на [ Cкачайте файл, чтобы посмотреть ссылку ].
Рис. 6.12. Схема для функции 1
Пример. Определим логическую функцию , реализуемую логической схемой вида ([ Cкачайте файл, чтобы посмотреть ссылку ])
Рис. 6.13. Схема для функции 2
Искомая логическая функция, если выписать ее последовательно, заполняя "верх" каждой стрелки, будет иметь следующий вид:
Лекция 7
Базовые алгоритмические структуры
Аннотация: Рассматриваются основные понятия об алгоритме в программах и алгоритмизации решения задач.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
" Алгоритм " является базовым основополагающим понятием информатики, а алгоритмизация (программирование) – основным разделом курса информатики (ядром курса). Понятие алгоритма, как и понятие информации, точно определить невозможно. Поэтому встречаются самые разнообразные определения – от "наивно-интуитивных" (" алгоритм – это план решения задачи") до "строго формализованных" (нормальные алгоритмы Маркова).
В качестве рабочего определения алгоритма возьмем следующее определение.
Алгоритм – это упорядоченная совокупность точных (формализованных) и полных команд исполнителю алгоритма (человек, ЭВМ), задающих порядок и содержание действий, которые он должен выполнить для нахождения решения любой задачи из рассматриваемого класса задач.
Алгоритм удовлетворяет следующим основным свойствам:
Конечность (дискретность) команд и выполняемых по ним действий алгоритма.
Выполнимость в определенной операционной среде (в определенном классе исполнителей).
Результативность отдельных команд и всего алгоритма.
Применимость алгоритма ко всем возможным входным данным конкретного класса задач.
Определенность (детерминированность) команд и всего алгоритма для всех входных данных.
Формализованное, конструктивное описание (представление) команд алгоритма.
Минимальная полнота системы команд алгоритма.
Непротиворечивость любых команд алгоритма на любом наборе входных данных.
Любой алгоритм ориентирован на некоторый общий метод решения класса задач и представляет собой формализованную запись метода, процедуры.
Алгоритм, записанный на некотором алгоритмическом, формальном языке, состоит из заголовка алгоритма (описания параметров, спецификаций класса задач) и тела алгоритма (последовательности команд исполнителя, преобразующих входные параметры в выходные).
Для записи, исполнения, обмена и хранения алгоритмов существуют различные средства, языки, псевдокоды – блок-схемы, структурограммы (схемы Нэсси-Шнайдермана), Р-схемы, школьный алгоритмический язык (ШАЯ), различные языки программирования.
В качестве языка описания алгоритмов нами используется далее язык программирования Паскаль, так как он наиболее подходит для целей обучения и часто (обоснованно) используется в обучении.
На алгоритмическом языке Паскаль любой алгоритм простой (не модульной, не составной) структуры имеет следующий стандартный вид:
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.
Порядок выполнения операций (старшинство операций – по убыванию) в языке Паскаль:
вычисление выражений в скобках;
вычисление стандартных функций;
умножение и деление (обозначаются "*" и "/");
сложение и вычитание (обозначаются "+" и "–").
Пример. Выражение 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) и эквивалентно математическому выражению: .
Рассмотрим базовые простые команды языка Паскаль.
Команда описания (заголовка) алгоритма (программы) :
Program <имя алгоритма>;,
где <имя алгоритма> – имя, задаваемое составителем программы (краткое, полное, грамотное отражение сути алгоритма ).
Ввод – команда ввода в рассмотрение (в тело алгоритма ) тех или иных входных параметров:
Read (<список вводимых параметров>);
или
ReadLn (<список вводимых параметров>);.
Первая команда вводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.
Вывод – команда вывода на экран тех или иных входных или выходных параметров алгоритма:
Write (<список выводимых параметров>);
или
WriteLn (<список выводимых параметров>);.
Первая команда выводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.
Присваивание – команда изменения текущего значения переменной вида:
<идентификатор> := <выражение>;,
где <идентификатор> соответствует имени переменной, <выражение> – корректно записанное выражение. Знак ":=" означает последовательное выполнение двух действий: определение текущего значения <выражения> и замена текущего значения переменной, имя которой задано <идентификатором>, на новое значение, равное значению <выражения>.
Команда начала алгоритма (блока) – команда Begin.
Команда завершения алгоритма (блока) – команда End.
Команда вставки комментариев в текст алгоритма имеет вид:
<комментируемое в программе> <текст комментария>.
Комментировать можно любой объект в программе. Обычно комментируют переменную, структуру данных, команду, группу команд.
Различают три базовые алгоритмические структуры: следование, ветвление, повторение.
Структура следование состоит из двух команд с указанной очередностью их выполнения и имеет вид:
<команда – предшественник>;
<команда – преемник>.
Структура типа ветвления в полной форме состоит из некоторого условия, проверяемого на истинность при выполнении структуры, команды, выполняемой при выполнении проверяемого условия, и команды, выполняемой при невыполнении условия. Структура имеет вид
if <условие>
then <команда, выполняемая при выполнении условия>
else <команда, выполняемая при невыполнении условия>;.
Ключевые (служебные) слова Паскаля – if (если), then (то), else (иначе). Ключевые слова нельзя изменять, заменять, так как их эталоны закреплены в переводчике с языка Паскаль (о нем подробнее – ниже).
Пример. Команда вида
if (х>y) { если текущее значение х больше текущего значения y, }
then у := х { то текущее значение у полагаем равным текущему значению х, }
else x:= y; { иначе (при х <= y) текущее значение x заменяем на текущее значение y }.
Структура типа ветвления в неполной форме – частный случай ветвления в полной форме, в которой, при невыполнении условия, управление просто передается следующей команде и больше никаких действий команда ветвления не осуществляет. Эта структура имеет вид
if <условие>
then <команда, выполняемая при исполнении условия>; .
Структура повторения (цикл) служит для компактной записи одного и того же набора команд, повторяемых для различных значений параметров команд.
Структура повторения типа "пока ( while )" записывается в виде:
while <условие продолжения повторения> do
<повторяемая команда>;
или
while <условие продолжения повторения> do
begin
<повторяемая команда номер 1>;
<повторяемая команда номер 2>;
. . .
<повторяемая команда номер N>
end;.
Ключевые слова Паскаля – while (пока), do (выполнять), begin (начало), end (конец).
Телом цикла называется последовательность повторяемых команд, которая может быть и пустой (редко встречаемый случай).
Часть команды цикла " while <условие продолжения повторения>" – заголовок цикла.
Данный цикл выполняется по правилу: если условие повторения для текущих его параметров не выполнено, то повторение команд (тела) цикла на этом завершается; если же оно выполнено, то выполняется тело цикла и опять проверяется условие повторения команд тела цикла.
Пример. Пусть необходимо находить сумму всех нечетных элементов натурального ряда чисел до тех пор, пока эта сумма не превысит значение n. Слагаемое, при котором эта сумма превысит n – включать в сумму.
"Забудем" временно чисто математическое решение этой задачи – с использованием суммы арифметической прогрессии с шагом 2.Алгоритм программа) имеет вид
Program Summa;
Uses Crt; { подключение библиотеки ввода/вывода на экран "в звуке и цвете"}
Var i, n, s: real;
{ для ряда чисел 1, 3, 5, , }
{ найти и выдать сумму s всех первых чисел ряда, для которых впервые s > n }
Begin
ClrScr; { команда очистки экрана (от данных предыдущей задачи) }
ReadLn (n); { ввод входного параметра }
s:=1; { начальное значение суммы до входа в цикл }
i:=1; { количество просуммированных чисел в начале }
while (s<=n) do { заголовок цикла (проверка условия выхода из цикла) }
begin
i:=i+2; { находим новое слагаемое }
s:=s+i { добавили к предыдущему значению суммы новое слагаемое }
end;
WriteLn ('Вычисленная сумма равна ', s); { вывод результата }
End.
Вторая форма повторения – цикл типа "до" ( for ), которая имеет вид
for <переменная> := <начальное значение переменной> to <конечное ее значение> do
<команда>;
или
for <переменная> := <начальное значение переменной> to <конечное ее значение> do
begin
<повторяемая команда номер 1>;
<повторяемая команда номер 2>;
. . .
<повторяемая команда номер N>
end;.
Здесь <переменная> – имя, идентификатор пересчитываемой переменной.
Ключевые слова Паскаля – for (для), to (к).
Этот цикл выполняется по правилу: для начального значения переменной выполняются команды тела цикла по порядку и затем проверяется, превысило ли текущее значение переменной ее заданного конечного значения; если превысило – цикл заканчивается, иначе значение переменной увеличивается на единицу и снова повторяется тело цикла и т.д.
Пример. Необходимо вычислить среднюю стоимость единицы всех n видов товаров (единица измерения – одна и та же, например, тонна), если стоимость единицы каждого товара увеличивается на 10, а наименьшая стоимость единицы товара равна 2. Если "забыть" временно лучшее, "чисто математическое" решение этой задачи, то алгоритм будет иметь вид
Program ST;
Uses Crt { подключение библиотеки ввода/вывода на экран "в звуке и цвете"}
Var i, n, s, x: integer;
{ стоимость единицы товара дается рядом n чисел вида: 2, 12, 22, 32, }
{ найти и выдать среднюю стоимость s всех n товаров s }
Begin
ClrScr { команда очистки экрана (от данных предыдущей задачи) }
ReadLn (n); { ввод входного параметра }
s:=0; { начальное значение суммы до входа в цикл }
x:=2; { начальное значение стоимости товара – стоимость первого товара }
for i:=1 to n do { заголовок цикла (проверка условия выхода из цикла) }
begin
s:=s+x; { находим новую сумму товаров }
x:=x+10 { находим стоимость следующего товара }
end;
WriteLn ('Вычисленная средняя стоимость товаров равна ', s/n : 5:5); { вывод результата }
End.
Рассмотрим примеры алгоритмизации (программирования) задач на языке Паскаль.
Пример. Составим алгоритм вычисления факториала заданного натурального числа n, то есть произведения n! = 1 * 2 * 3 * ... * (n – 1) * n c использованием рекуррентной формулы n! = (n – 1)! * n. Опишем метод решения. Для этого заметим цепочку справедливых равенств:
1! = 1, 2! = 1 * 2 = 1! * 2, 3! = 1 * 2 * 3 = 2! * 3, ..., m! =1 * 2 * 3 * ... * (m – 1) * m = (m – 1)! * m.
Следовательно, для вычисления факториала m! необходимо факториал (m – 1)! домножить на m, где m = 1, 2, ..., n. Программа на Паскале имеет вид
Program Factorial;
Uses Crt;
Var n, f, i: integer;
{ дано натуральное число n }
{ найти и выдать произведение всех натуральных чисел до n включительно }
Begin
ClrScr;
WriteLn('Введите число n : '); { приглашение к вводу входного параметра }
ReadLn(n); { ввод входного параметра }
f:=1; { начальному значению f присваивается 1, то есть 1!=1 }
for i:=1 to n do { цикл умножения текущего произведения f на текущее i }
f:=f*i; { предыдущее значение факториала умножаем на текущее значение i }
WriteLn('Полученный результат f : ',f); { вывод результата }
End.
Пример. Составим алгоритм перевода заданного десятичного натурального числа n в двоичную систему. Метод решения определяется процедурой перевода – последовательными делениями числа n на 2 и последующим сбором остатков от деления. Если последовательно выдавались с равные 1,0,1,0,0,1, то двоичное изображение c равно 100101. Алгоритм имеет вид
Program S10-S2;
Uses Crt;
Var n, a, i, c: integer;
{ дано десятичное натуральное число }
{ выдать последовательно цифры его двоичного изображения }
Begin
ClrScr;
WriteLn('Введите переводимое число : '); { приглашение к вводу входного параметра }
ReadLn(n); { ввод входного параметра }
WriteLn('Полученное двоичное число от конца :'); { выдача "шапки" к результату }
i:=0; { начинаем с младшего, нулевого разряда }
while (n>0) do { цикл деления числа и получаемых частных (пока делится) }
begin
i:=i+1; { переход к следующему делению }
c:=n mod 2; { находим очередной остаток от деления на 2}
n:=n div 2; { находим очередное частное от целочисленного деления }
write(c) { выдаем новую двоичную цифру }
end;
End.
Лекция 8
Данные их типы, структуры, обработка
Аннотация: Рассматриваются основные понятия о данных к алгоритмам, их базовые типы и структуры, вопросы их использования в алгоритмизации задач.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Любая актуализация информации опирается на какие-то данные, любые данные могут быть каким-то образом актуализированы.
Данные – это некоторые сообщения, слова в некотором заданном алфавите.
Пример. Число 123 – данное, представляющее собой слово в алфавите из десяти натуральных цифр; число 12,34 – данное, представляющее собой слово в алфавите из десяти натуральных цифр и десятичной запятой; текст "математика и информатика – нужные дисциплины", – данное в алфавите из символов русского языка и знаков препинания, включая пробел.
Текущее (то есть рассматриваемое в данный момент времени) состояние данных называют текущим значением данных или простозначением.
До разработки алгоритма (программы) необходимо выбрать оптимальную для реализации задачи структуру данных. Неудачный выбор данных и их описания может не только усложнить решаемую задачу и сделать ее плохо понимаемой, но и привести к неверным результатам. На структуру данных влияет и выбранный метод решения.
Пример. При решении системы линейных алгебраических уравнений можно воспользоваться методом Крамера (с помощью определителей) или методом Гаусса (с помощью последовательных исключений неизвестных). Метод Крамера потребует при реализации примерно в 3 раза больше операций, чем метод Гаусса, и поэтому им никогда не пользуются при расчетах на ЭВМ.
Тип данных характеризует область определения значений данных.
Задаются типы данных простым перечислением значений типа, например как в простых типах данных, либо объединением (структурированием) ранее определенных каких-то типов – структурированные типы данных.
Пример. Зададим простые типы данных "специальность", "студент", "вуз" следующим перечислением:
специальность = (филолог, историк, математик, медик);
студент = (Петров, Николаев, Семенов, Иванова, Петрова);
вуз = (МГУ, РГУ, КБГУ).
Значением типа "студент" может быть Петров.
Пример. Опишем структурированный тип данных "специальность_студента":
специальность_студента=(специальность, студент).
Значением типа "специальность_студента" может быть пара ( историк, Семенов ).
Для обозначения текущих значений данных используются константы – числовые, текстовые, логические.
Часто (в зависимости от задачи) рассматривают данные, которые имеют не только "линейную" (как приведенные выше), но и иерархическую структуру.
Пример. Структуру "вуз" можно задать иерархической структурой, состоящей, например, из следующих уровней: "Ректорат", "Деканаты и подразделения", "Кафедры", "Отделы", "Преподаватели и сотрудники".
В алгоритмических языках есть стандартные типы, например, целые, вещественные, символьные, текстовые и логические типы. Они в этих языках не уточняются (не определяются, описываются явно) и имеют соответствующие описания с помощью служебных слов.
Пример. В школьном алгоритмическом языке (ШАЯ), например, целые, вещественные, символьные, текстовые (литерные, стринговые) и логические типы данных описываются ключевыми словами цел, вещ, сим, лит, лог. В языке Паскаль – аналогичными ключевыми словами integer, real, char, string, boolean.
Каждый тип данных допускает использование определенных операций со значениями типа ("с типом").
Пример. Для целого типа данных назовем операции ":=", "+", "–", "*", "=" (сравнение на равенство), " ", "<", ">", " ", " ".. Для вещественного типа данных еще и операция "/" (деление). Для символьного типа данных – только ":=", "=", " ", "<", ">", " ", " ". Например, сравнение "а"<"b" означает, что символ "а" предшествует символу "b" то есть код буквы "a" меньше кода буквы "b" (коды символов приводятся, например, в таблице ASCII – Аmerican Standard Code for Information Interchange, американский стандарт кодирования для обмена данными ). Для текстового (литерного) типа данных можно использовать еще и операцию конкатенации (присоединения справа) текстов "+". Например, "аб"+"ба" даст новый текст "абба". Для данных логического типа определены логические операции и отношения сравнения. Например, на Паскале для логических переменных a, b, cможно записать корректное выражение: a and b or (c not a).
Для описания переменных, значениями которых могут быть лишь символы, тексты, используются соответствующие ключевые слова: на ШАЯ – сим, лит, на Паскале – char, string.
Текстовые (символьные) константы обычно заключают в апострофы.
Пример. Составим алгоритм подсчета числа несовпадающих символов (на одинаковых позициях текстов) в двух заданных текстах aи b. Метод решения: "вырезаем" и сравниваем символы на одинаковых позициях в текстах на совпадение.
Program EquSimb;
Uses Crt;
Var i, k, j: integer;
a, b: string;
Begin
ClrScr;
WriteLn('Введите строку a = '); { приглашение к вводу входного параметра}
ReadLn(a); { ввод первого входного параметра }
WriteLn('Введите строку b='); { приглашение к вводу второго параметра }
ReadLn(b); { ввод второго входного параметра }
k:=abs(length(a)–length(b)); { вычисление разницы длин текстов }
if (length(a)
then j:=length(a) { то проверять нужно до длины a, }
else j:=length(b); { иначе – до длины b }
for i:=1 to j do { цикл проверки на совпадение символов }
if (a[i]<>b[i]) { если символы тестов на одинаковых позициях не равны, }
then k:=k+1; { то увеличиваем счетчик количества таких символов }
WriteLn('k = ',k); { вывод результата }
End.
Наиболее часто используемая структура данных – массив.
Одномерный массив (вектор, ряд, линейная таблица) – это совокупность значений некоторого простого типа (целого, вещественного, символьного, текстового или логического типа), перенумерованных в каком-то порядке и имеющих общее имя. Для выделения конкретного элемента массива необходимо указать его порядковый номер в этом ряду.
Пример. Последовательность чисел 89, –65, 9, 0, –1.7 может образовывать одномерный вещественный массив размерности 5, например, с именем x вида: x[1] = 89, x[2] = –65, x[3] = 9, x[4] = 0, x[5] = –1.7.
Значение порядкового номера элемента массива называется индексом элемента.
Пример. Можно ссылаться на элемент х[4], элемент х[i], элемент x[4+j] массива х. При текущих значениях переменных i = 2 и j = 1 эти индексы определяют, соответственно, 4-й, 2-й и 5-й элементы массива.
Для обозначения (нового типа объектов) массивов в алгоритмических языках обычно вводится специальное служебное слово.
Пример. В ШАЯ – это слово "таб", после которого приводится имя массива и в квадратных скобках его размерность, например, для одномерного массива – в виде [m:n], где m – номер первого элемента массива (часто 1), n – номер последнего элемента (шаг перебора элементов равен 1). На Паскале имеется соответствующее слово array. Вышеуказанная последовательность из пяти чисел описывается на ШАЯ в виде: вещ таб x[1:7], а на Паскале (в рамках рассматриваемого нами его ядра) необходимо указывать предельную величину размерности:
x: array [1..100] of real;.
Двумерный массив ( матрица, прямоугольная таблица) – совокупность одномерных векторов, рассматриваемых либо "горизонтально" (векторов-строк), либо "вертикально" (векторов-столбцов) и имеющих одинаковую размерность, одинаковый тип и общее имя.
Матрицы, как и векторы, должны быть в алгоритме описаны служебным словом (например, таб или array ), но в отличие от вектора, матрица имеет описание двух индексов, разделяемых запятыми: первый определяет начальное и конечное значениеномеров строк, а второй – столбцов.
Пример. Если матрица x описана в виде
x: array [1..5, 1..3] of real; ,
то определяется таблица из 5 строк (от 1-й до 5-й строки) и 3 столбцов (от 1-го до 3-го столбца) вида:
(столбец 1)
(столбец 2)
(столбец 3)
x11
x12
х13
(строка 1)
x21
x22
х23
(строка 2)
х31
х32
х33
(строка 3)
х41
x42
х43
(строка 4)
х51
x52
х53
(строка 5)
Для актуализации элемента двумерного массива нужны два его индекса – номер строки и номер столбца, на пересечении которых стоит этот элемент.
Пример. Элемент х[3,2] – элемент на пересечении 3-й строки и 2-го столбца массива х.
Рассмотрим ряд задач, решаемых с помощью массивов.
Пример. Составим алгоритм (программу) нахождения суммы и произведения всех элементов одномерного массива. Метод решения: начиная с нулевого значения суммы, добавляем поочередно новый элемент ряда и находим значение искомой суммы; начиная с начального, единичного произведения, находим искомое произведение, умножая текущее значение произведения на очередной элемент ряда. Алгоритм (программа) имеет вид
Program SPM1;
Uses Crt;
Var x: array [1..100] of real;
n, i: integer;
s, р: real;
Begin
ClrScr;
WriteLn('Введите размерность массива :'); { приглашение к вводу входного параметра }
ReadLn(n); { ввод входного параметра }
WriteLn('Введите элементы массива:'); { приглашение к вводу массива }
for i:=1 to n do { цикл ввода элементов массива }
begin
write('x[',i,']='); { приглашение к вводу текущего элемента массива}
readln(x[i]) { ввод текущего элемента массива }
end;
s:=0; { начальное значение суммы – нуль }
p:=1; { начальное значение произведение – единица [u1]}
for i:=1 to n do { цикл вычисления суммы и произведения }
begin
s:=s+x[i]; { добавление к сумме очередного слагаемого }
p:=p*x[i] { домножение произведения на очередной множитель }
end;
WriteLn('Полученная сумма равна ', s: 3:3); { вывод полученной суммы }
WriteLn('Полученное произведение равно ', p: 3:3); { вывод полученного произведения }
End.
Пример. Составим алгоритм вычисления суммы бесконечного ряда чисел а[1], а[2], а[3], ... с точностью е, при условии, что точность всегда достигается для номера члена ряда не более 1000000 (это "неестественное" ограничение нужно для того, чтобы в Паскале было проще объявить размерность массива а ). Метод решения: сравниваем две суммы – одна сумма была получена на предыдущем шаге суммирования, а вторая – добавлением к ней очередного слагаемого (то есть их разность и равна очередному добавленному элементу ряда ); процесс суммирования продолжается до тех пор, пока разность по модулю не станет меньше точности суммирования. Алгоритм (программа) имеет вид
Program SumND;
Uses Crt;
Var a: array [1..1000000] of real;
i: integer;
e, p, s: real;
begin
ClrScr;
WriteLn('Введите точность :'); { приглашение к вводу входного параметра }
ReadLn(e); { ввод входного параметра }
i:=1; { начальный номер члена ряда }
WriteLn(введите первые два элемента :’); { приглашение к вводу входных параметров }
ReadLn(a[1], a[2]); { ввод входных параметров }
р:=а[1]; { запоминаем начальную сумму – сумму одного элемента }
s:=р+a[2]; { запоминаем начальную следующую сумму – сумму двух элементов }
while (abs(s–p)>e) do { цикл суммирования, пока слагаемые влияют на сумму }
begin
i:=i+1; { переход к следующему элементу }
p:=s; { "старую" сумму заменяем "новой", полученной добавлением еще одного }
s:=s+а[i]; { вычисляем "новую" сумму }
WriteLn(введите a[, i, ]=’); { приглашение к вводу очередного элемента ряда }
ReadLn(a[i]); { ввод очередного элемента ряда }
end;
WriteLn('Полученная сумма равна ', s: 3:3); { вывод результата }
End.
Пример. Составим алгоритм вычисления значения полинома Pn(x) = а0хn + а1хn–1 + ... + аn для заданного значения x.Метод решения – метод (схема) Горнера. Опишем его. Заметим, что:
1) при n = 0, P0(x) = a0 ;
2) при n = 1, P1(x) = a0x + a1 = P0(x) x + a1 ;
3) при n = 2, P2(х) = a0x2 + a1x + a2 = (a0x + a1)x + a2 = P1(x)x + a2 ;
. . .
n) Pn(x) = a0xn + a1xn–1 + ... + an–1x + an = (a0xn–1 + a1xn–2 + ... + an–1)x + an = Pn–1(x)x + an .
Таким образом, всегда верно рекуррентное соотношение Горнера:
Текущее Р := Предыдущее Р*x + Текущий коэффициент полинома.
Эту схему реализуем в алгоритме (программе) вида:
Program Gorner;
Uses Crt;
Var a: array [0..100] of real;
n, i: integer;
p, x: real;
Begin
ClrScr;
WriteLn('Введите порядок полинома :'); { приглашение к вводу входного параметра }
ReadLn(n); { ввод первого входного параметра }
WriteLn('Введите число x :'); { приглашение к вводу второго входного параметра }
ReadLn(x); { ввод второго входного параметра }
for i:=0 to n do { цикл схемы Горнера }
begin
WriteLn('a[',i,']='); { приглашение к вводу очередного коэффициента полинома}
ReadLn(a[i]); { ввод очередного коэффициента полинома }
end;
p:=a[0]; { начальное (для n=0) значение полинома – см. схему Горнера}
for i:=1 to n do { цикл накапливания значения полинома по схеме Горнера}
p:=p*x+a[i]; { находим полином текущей степени i используя предыдущий }
WriteLn('Полученнoe значение p = ', p:3:3); { вывод результата }
End.
Пример. Составим алгоритм вычисления суммы и произведения всех элементов a[i,j], i = 1, 2, ..., n ; j = 1, 2, ..., mзаданной матрицы. Метод решения: построчно проходя все элементы массива, добавляем к предыдущему значению суммы новый элемент матрицы и умножаем предыдущее значение произведения на этот же элемент. Алгоритм (программа) имеет вид
Program SPM2;
Uses Crt;
Var a: array [1..100,1..100] of real;
n, m, i, j: integer;
s, p: real;
Begin
ClrScr;
WriteLn('Введите количество строк:'); { приглашение к вводу входного параметра }
ReadLn(n); { ввод первого входного параметра }
WriteLn('Введите количество столбцов:'); { приглашение к вводу второго параметра }
ReadLn(m); { ввод второго входного параметра }
for i:=1 to n do { цикл ввода – перебора строк }
for j:=1 to m do { цикл перебора элементов текущей строки }
begin
WriteLn('a[',i,',',j,']='); { приглашение к вводу очередного элемента массива }
ReadLn(a[i,j]); { ввод очередного элемента массива }
end;
s:=0; { начальное значение суммы – нуль }
p:=1; { начальное значение произведения – единица }
for i:=1 to n do { цикл перебора строк для суммирования }
for j:=1 to m do { цикл перебора элементов строки (столбцов) для суммирования }
begin
s:=s+a[i,j]; { добавление очередного элемента к текущему значению суммы}
p:=p*a[i,j]; { умножение текущего значения произведения на новый элемент }
end;
WriteLn('Сумма равно : ', s:3:3); { вывод первого результата }
WriteLn('Произведение равно : ', p:3:3); { вывод второго результата }
End.
Лекция 9
Методы разработки и анализа алгоритмов
Аннотация: Рассматриваются основные понятия о методах проектирования (нисходящем, восходящем, модульном, структурном) и разработки алгоритмов (программ), тестирование и верификация алгоритма, трассировка алгоритма.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Нисходящим проектированием алгоритмов, проектированием алгоритмов "сверху вниз" или методом последовательной (пошаговой)нисходящей разработки алгоритмов называется такой метод составления алгоритмов, когда исходная задача (алгоритм) разбивается на ряд вспомогательных подзадач (подалгоритмов), формулируемых и решаемых в терминах более простых и элементарных операций (процедур). Последние, в свою очередь, вновь разбиваются на более простые и элементарные, и так до тех пор, пока не дойдём до команд исполнителя. В терминах этих команд можно представить и выполнить полученные на последнем шаге разбиений подалгоритмы (команд системы команд исполнителя).
Восходящий метод, наоборот, опираясь на неко
·торый, заранее определяемый корректный набор подалгоритмов, строит функционально завершенные подзадачи более общего назначения, от них переходит к более общим, и так далее, до тех пор, пока не дойдем до уровня, на котором можно записать решение поставленной задачи. Этот метод известен как метод проектирования"снизу вверх".
Структурные принципы алгоритмизации ( структурные методы алгоритмизации) – это принципы формирования алгоритмов из базовых структурных алгоритмических единиц (следование, ветвление, повторение), используя их последовательное соединение или вложение друг в друга с соблюдением определённых правил, гарантирующих читабельность и исполняемость алгоритма сверху вниз и последовательно.
Структурированный алгоритм – это алгоритм, представленный как следования и вложения базовых алгоритмических структур. У структурированного алгоритма статическое состояние (до актуализации алгоритма) и динамическое состояние (после актуализации) имеют одинаковую логическую структуру, которая прослеживается сверху вниз ("как читается, так и исполняется"). При структурированной разработке алгоритмов правильность алгоритма можно проследить на каждом этапе его построения и выполнения.
Теорема (о структурировании). Любой алгоритм может быть эквивалентно представлен структурированным алгоритмом, состоящим из базовых алгоритмических структур.
Одним из широко используемых методов проектирования и разработки алгоритмов (программ) является модульный метод(модульная технология).
Модуль – это некоторый алгоритм или некоторый его блок, имеющий конкретное наименование, по которому его можно выделить и актуализировать. Иногда модуль называется вспомогательным алгоритмом, хотя все алгоритмы носят вспомогательный характер. Это название имеет смысл, когда рассматривается динамическое состояние алгоритма; в этом случае можно назвать вспомогательным любой алгоритм, используемый данным в качестве блока (составной части) тела этого динамического алгоритма. Используют и другое название модуля – подалгоритм. В программировании используются синонимы – процедура, подпрограмма.
Свойства модулей:
функциональная целостность и завершенность (каждый модуль реализует одну функцию, но реализует хорошо и полностью);
автономность и независимость от других модулей (независимость работы модуля-преемника от работы модуля-предшественника; при этом их связь осуществляется только на уровне передачи/приема параметров и управления);
эволюционируемость (развиваемость);
открытость для пользователей и разработчиков (для модернизации и использования);
корректность и надежность;
ссылка на тело модуля происходит только по имени модуля, то есть вызов и актуализация модуля возможны только через его заголовок.
Свойства (преимущества) модульного проектирования алгоритмов:
возможность разработки алгоритма большого объема (алгоритмического комплекса) различными исполнителями;
возможность создания и ведения библиотеки наиболее часто используемых алгоритмов (подалгоритмов);
облегчение тестирования алгоритмов и обоснования их правильности ;
упрощение проектирования и модификации алгоритмов ;
уменьшение сложности разработки ( проектирования ) алгоритмов (или комплексов алгоритмов);
наблюдаемость вычислительного процесса при реализации алгоритмов.
Тестирование алгоритма – это проверка правильности или неправильности работы алгоритма на специально заданных тестах или тестовых примерах – задачах с известными входными данными и результатами (иногда достаточны их приближения). Тестовый набор должен быть минимальным и полным, то есть обеспечивающим проверку каждого отдельного типа наборов входных данных, особенно исключительных случаев.
Пример. Для задачи решения квадратного уравнения ax2 + bx + c = 0 такими исключительными случаями, например, будут: 1)a = b = c = 0; 2) a = 0, b, c – отличны от нуля; 3) D = b2 – 4ac < 0 и др.
Тестирование алгоритма не может дать полной (100%-ой) гарантии правильности алгоритма для всех возможных наборов входных данных, особенно для достаточно сложных алгоритмов.
Полную гарантию правильности алгоритма может дать описание работы и результатов алгоритма с помощью системы аксиом и правил вывода или верификация алгоритма.
Пример. Составим алгоритм нахождения числа всех различных двоичных сообщений (двоичных последовательностей) длины nбитов, используя при этом не более одной операции умножения, и докажем правильность этого алгоритма. Вначале найдем число всех таких сообщений. Число двоичных сообщений длины 1 равно 2 = 21 (это "0" и "1"), длины 2 равно 4 = 22 ("00", "01", "10", "11"). Отправляясь от этих частных фактов, методом математической индукции докажем, что число различных сообщений длины n равно 2n . Этот индуктивный вывод докажет правильность алгоритма.
Пусть это наше утверждение верно для n = k. Тогда для n = k + 1 получаем, что добавление каждого бита (0 или 1) к любому из 2k сообщений длины k приведет к увеличению числа сообщений в 2 раза, то есть их число будет равно 2 x 2k = 2k+1 , что и доказывает наше индуктивное предположение.
Составим теперь алгоритм вычисления числа x = 2n с использованием операции умножения только один раз.
Прологарифмируем последнее равенство. Получим ln(x) = ln(2n) = n ln(2) .
Используя равенство exp(ln(x)) = x, получим, что exp(ln(x)) = x = exp(n ln(2)).
Остается теперь записать простейший алгоритм вычисления числа x.
Program Power;
Uses Crt;
Var x: real;
n: integer;
Begin
ClrScr;
WriteLn('Введите длину в битах n ='); { приглашение к вводу входного параметра }
ReadLn(n); { ввод входного параметра }
x:=exp(n*ln(2)); { вычисление степени }
WriteLn('количество сообщений равно: ', int(x+0.5)); { вывод х с округлением }
End.
Для несложных алгоритмов грамотный подбор тестов и полное тестирование может дать полную картину работоспособности (неработоспособности).
Трассировка – это метод пошаговой фиксации динамического состояния алгоритма на некотором тесте. Часто осуществляется с помощью трассировочных таблиц, в которых каждая строка соответствует определённому состоянию алгоритма, а столбец – определённому состоянию параметров алгоритма (входных, выходных и промежуточных). Трассировка облегчает отладку и понимание алгоритма.
Процесс поиска и исправления (явных или неявных) ошибок в алгоритме называется отладкой алгоритма.
Некоторые (скрытые, труднообнаруживаемые) ошибки в сложных программных комплексах могут выявиться только в процессе их эксплуатации, на последнем этапе поиска и исправления ошибок – этапе сопровождения. На этом этапе также уточняют и улучшают документацию, обучают персонал использованию алгоритма (программы).
Пример. Определим функцию фрагмента алгоритма вида на тесте n=2; x[1]=4; x[2]=9:
k:=1;
s:=x[1];
for i:=1 to n
if (s
then begin
s:=x[i]
k:=i
end;
writeln (k);
Если выписать трассировочную таблицу вида
i
S
x[i]
K
s
i<=n
1
4
4
1
Нет
Да
2
4
9
2
Да
Да
3
Нет
то функция алгоритма становится более понятной – эта функция состоит в нахождении индекса максимального элемента ряда.
В заключение данного раздела приведем общую структуру алгоритмического обеспечения. Критерии, по которым алгоритмы могут быть классифицированы, бывают разными, поэтому предлагаемая ниже схема отражает основные элементы структуры и в некоторых случаях является условной, в том смысле, что блоки приведенной на [ Cкачайте файл, чтобы посмотреть ссылку ] структуры могут "перекрываться".
Рис. 9.1. Структура алгоритмического обеспечения
Основные формы использования алгоритмов – автономное, библиотечное, пакетное.
Автономный алгоритм определяется решаемой задачей, структурой используемых данных, структурой логических связей частей (модулей) алгоритма и языком псевдокодов, на котором представлен, описан алгоритм.
Библиотека алгоритмов определяется множеством задач, решаемых с помощью библиотеки, множеством алгоритмов для решения типовых задач некоторой предметной области и структурой используемых данных.
Пакет алгоритмов, как и библиотека, определяется множеством задач, решаемых с помощью пакета, множеством алгоритмов для решения типовых задач или их составных частей из некоторой предметной области, структурой используемых данных и обменов данными между задачами (модулями), специальным языком, на котором формулируется задание (последовательность этапов решаемой задачи, последовательность задач задания).
Лекция 9
Исполнители алгоритмов – человек и автомат
Аннотация: Рассматриваются основные понятия о базовых исполнителях алгоритмов – человеке и конечном автомате, об их управляющих и исполняющих подсистемах, структурах.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Исполнителем называется некоторая биологическая, техническая или смешанная структура, способная исполнять (покомандно или программно) некоторый класс алгоритмов в некоторой операционной среде (некотором множестве допустимых "инструментов" и "команд").
Наиболее используемые типы исполнителя алгоритмов – человек или автомат (компьютер).
Человек как исполнитель алгоритмов – совокупность исполняющих подсистем (мышечная, двигательная, зрительная, обонятельная и др.) и управляющей подсистемы (нервная, нейронная).
Нервная система передает информацию, получаемую от нервных окончаний кожи, глаз, ушей и других органов, к нервным центрам для ее последующей интеграции, обработки и выработке адекватной реакции. Нервная система – совокупность взаимодействующих нервных клеток или нейронов. У человека их – громадное количество.
Пример. По различным оценкам физиологов, в коре переднего мозга человека – около 50 млрд нейронов. Нейроны, хотя и работают медленно (около сотни инструкций в секунду), но могут за счет более эффективного взаимодействия друг с другом и организации сложнейших нейроструктурных связей (кластеров) решать сложные мыслительные задачи, принимать решения.
Пример. Такая плохо структурируемая, но "простая" для человека задача, как "одеться по погоде", решается быстро с помощью обработки зрительной, слуховой информации и согласованной "нейронной" оценки ситуации, хотя она и плохо формализуемая. Компьютеру эту задачу решать будет намного сложнее. С другой стороны, вычислительные ресурсы человека ограничены посравнению с возможностями компьютера, который во много раз лучше (быстрее, точнее) решает хорошо формализуемые и хорошо структурируемые задачи.
Нейроны служат для передачи информации за счет нервных импульсов, которая расшифровывается в соответствующих областях коры головного мозга.
В непосредственную ( сенсорную ) память человека поступает информация от различных сенсоров: зрительных, слуховых, обонятельных и т.д. Затем эта информация переводится в оперативную память ( память сознания ). Далее она пересылается вдолговременную память с привлечением подсознания ("укладывается на полочки" с соответствующими названиями "Формы поведения", "Объекты и образы", "Правила и процедуры обнаружения и идентификации объектов", "Правила выборки и организации информации", "Жизненный опыт", "Бытовые навыки и умения", "Профессиональные навыки и умения" и др.).
Пример. Увиденный человеком конкретный компьютер ассоциируется с абстрактным понятием "Компьютер" (из долговременной памяти) – например со сведениями об этом устройстве – информационными кодами, которые определяют объект (связь, понятие). Коды связываются между собой, создавая образ конкретного компьютера.
В живом организме передача, хранение или обработка информации происходит с помощью биохимических реакций и сообщений – сигнальных молекулярных систем и их превращений за счет химических реакций катализа и разностей концентрации химических веществ. Разность потенциалов действий (электрические сигналы) проводят нервные волокна, с помощью центральной нервной системы. При этом используется и генная информация, которая передается от ДНК к РНК, от РНК – к белку, определяя новую белковую структуру, ее функции.
Второй важный тип исполнителей – конечные автоматы, автоматические (то есть функционирующие определенный промежуток времени без участия человека ) устройства, вход, выход и состояния которых можно описать конечными последовательностями сообщений (слов над конечными алфавитами).
Любой конечный автомат реализует некий непустой класс алгоритмов и состоит из совокупности управляющего автомата, который определяет порядок выполнения действий, и операционного автомата, реализующего сами действия, выполняемые автоматом.
Пример. Пример конечного автомата – автомат для продажи газированной воды. Его функционирование можно изобразить графом ([ Cкачайте файл, чтобы посмотреть ссылку ]), если ввести следующие множества и события:
– входное множество,
Y = {В, С, О} – выходное множество,
S = {s0 , s1 , s2 , s3} – множество состояний,
1 – входной сигнал "опустить 1 руб.",
3 – входной сигнал "опустить 3 руб.",
Г – входной сигнал "опустить гнутую монету",
– входной сигнал "монета не опущена",
В – выходной сигнал "выдача воды газированной без сиропа",
С – выходной сигнал "выдача газированной воды с сиропом",
О – выходной сигнал "отказ выдать воду",
s0 – первое состояние – "начальное состояние",
s1 – второе состояние – "обработка 1 руб.",
s2 – третье состояние – "обработка 3 руб.",
s3 – четвертое состояние – "состояние неисправности".
Рис. 10.1. Граф автомата для продажи газированной воды
Функционирование конечного автомата происходит в дискретные моменты времени t = 0, 1, 2, ..., T. Изменение состоянияавтомата , то есть переход из текущего состояния в новое состояние , может быть осуществлено либо до выдачи выходного сигнала , либо – после выдачи этого сигнала. В связи с этим, выделяют два типа конечных автоматов – автоматы Мили и автоматы Мура, которые различаются законами функционирования автоматов.
Законы функционирования автомата Мили:
Законы функционирования автомата Мура:
Функция выходов f автомата Мура явно не зависит от входного сигнала и полностью определяется только самим внутренним состоянием автомата, которое, в свою очередь, определяется входным сигналом.
Пример. Пример конкретного автомата Мура приведен выше ( автомат для газировки). Приведем абстрактный пример автомата Мили: Х = {х1, х2} , У = {у1, у2, у3} , S = {s0, s1, s2, s3, s4, s5} , функции перехода и выхода f зададим таблицами соответствий:
– функция перехода
s(t – 1)
S1
s1
s2
s3
s3
s4
s5
x(t)
Х1
х2
x1
x2
x1
x2
х2
x1
s(t)
S2
s3
s4
s2
s4
s3
s5
s5
13 QUOTE 1415функция выхода
s(t – 1)
S1
s1
s2
s2
s3
s3
s4
s5
x(t)
X1
x2
x1
x2
x1
х2
х2
х1
y(t)
У2
у3
y1
y1
y3
у2
у3
y2
Компьютер можно рассматривать как совокупность взаимодействующих конечных автоматов. Рассмотрим такую структуру подробнее.
Память компьютера – последовательность ячеек памяти, то есть физических устройств, куда можно записывать или считывать последовательность битов, каждый из которых хранится в нужном разряде.
Пример. Запишем числа 1310, в формате целых чисел в восьмиразрядную ячейку памяти запишется в виде (старший бит будет содержать бит знака числа, например, 1 – если число отрицательно и 0 – если число положительно). Учитывая, что 1310 = 11012, получаем представление вида:
Аналогичным образом представляются в памяти компьютера и вещественные числа: либо по частям (целая часть – отдельно, дробная – отдельно), либо в специальной, так называемой нормализованной форме, для которой хранится отдельно дробная часть (мантисса) и порядок – степень двойки, домножением на которую можно записать данное число.
Пример. Если десятичное число равно 5,25, то есть в двоичной форме – 101,01, то оно записывается в нормализованной форме: 0,10101 с порядком, равным в двоичном виде 101.
Команды, как и числа, размещаются (в битовом изображении) в специальных электронных устройствах – так называемых регистрах.
Регистр – электронное устройство, как и ячейка памяти, запоминающее и хранящее (временно) последовательность битов определенной длины. Регистры реализуются более дорогими и чувствительными физическими устройствами и поэтому, посравнению с основной памятью компьютера, регистровая память или так называемая кэш-память – невелика.
Пример. Для компьютера с памятью 512 мегабайт основной памяти может быть характерна регистровая память в 64 килобайта.
Каждой команде ставится в соответствие операция, производится расшифровка кода этой операции, затем извлекаются операндыили числа, над которыми необходимо выполнить операцию. Далее выполняется операция с этими операндами, и результатоперации помещается в соответствующую ячейку памяти.
Кроме оперативной памяти, компьютер имеет внешнюю память (ВЗУ) с большой емкостью, но с большим временем записи или считывания информации. Внешняя память реализуется с помощью внешних носителей информации: магнитных или оптических дисков.
Джон фон Нейман предложил ряд принципов, которые легли в основу фон Неймановской или классической архитектуры компьютера:
память состоит из однородных ячеек памяти с адресами;
программа состоит из последовательных команд;
хранение программы и обрабатываемых ею данных – одинаковое, в битовом виде;
команды выполняются последовательно, данные извлекаются в соответствии с командами;
процессор – один и имеет централизованное управление и доступ к памяти.
Структура ЭВМ фон Неймановской архитектуры приведена на [ Cкачайте файл, чтобы посмотреть ссылку ].
Рис. 10.2. Структура ЭВМ фон Неймановской архитектуры
Арифметико-логическое устройство (АЛУ) выполняет арифметические, логические операции.
Пример. Команды АЛУ – просты: "сравнить два числа", "переслать число", "взять дизъюнкцию" и др.
Устройство управления (УУ) организует работу ЭВМ, в частности это устройство извлекает очередную команду из памяти, расшифровывает команду, выбирает из памяти операнды к расшифрованной команде и передает их АЛУ для выполнения расшифрованной операции, а после выполнения пересылает результат для хранения в память. При этом УУ реагирует на нормальный или аварийный ход выполнения операции.
Совокупность АЛУ и УУ, информационно-управляющих линий называется процессором компьютера (его структура приведена на[ Cкачайте файл, чтобы посмотреть ссылку ]; жирная линия – информационное взаимодействие, другая – управляющее).
Рис. 10.3. Структура процессора
Обмен информацией с компьютером осуществляется устройствами ввода и устройствами вывода.
Пример. Устройствами ввода являются, например, клавиатура, мышь. Устройствами вывода дисплей, принтер, плоттер.
Распространенный тип компьютера – персональный компьютер. Персональный компьютер отвечает требованиям малой стоимости, малых размеров, малого энергопотребления, высокой надежности, высокого уровня интеграции компонентов, адаптируемости к разнообразным применениям и др.
Ядро персонального компьютера – системная (материнская плата), на которой размещаются: микропроцессор, микропроцессорная память, интерфейсная система микропроцессора для сопряжения и связи с другими устройствами, генератортактовых импульсов, контроллеры устройств (схем), интегрированных в материнскую плату, микросхемы ОЗУ и ПЗУ и др.
Другими важными устройствами персонального компьютера являются:
дисковод гибких магнитных дисков; дисковод жестких магнитных дисков;
CD-ROM (устройство только для чтения компакт-дисков) или CD-RW (чтение и перезапись);
монитор (дисплей);
видеокарта (видеоадаптер) для обеспечения связи системного блока и монитора;
клавиатура;
принтер;
сканер;
плоттер (графопостроитель);
дигитайзер (кодирующий планшет);
манипулятор-мышь или манимулятор-трекбол;
звуковая карта (адаптер);
звуковые колонки;
модем и другие устройства.
Классификацию компьютеров проводят по быстродействию, технологии использования и др. Дадим обобщенную и поэтому нечеткую и перекрывающуюся классификацию.
Суперкомпьютеры – наиболее мощные компьютеры в мире, используемые для решения очень сложных и очень больших задач (исследования космоса, ядерной физики, геологии и др.).
Компьютеры универсального назначения, используемые для решения сложных и больших задач.
Персональные компьютеры, используемые в индивидуальном порядке для решения как несложных и небольших, так и сложных, больших задач.
Пример. Супервычислительный центр может быть создан для решения государственных проблем, например обороны, изучения космоса, прогноза погоды, макроэкономического прогнозирования и др. В этом центре могут использоваться как персональные компьютеры на рабочих местах сотрудников, так и компьютеры общего, универсального назначения для решения менее сложных, например вспомогательных проблем.
При работе на компьютере необходимо следовать определенным и простым санитарно-гигиеническим правилам, так как компьютеримеет вредно влияющие на здоровье человека факторы: излучения (инфракрасное, рентгеновское, электромагнитное); вибрация и шум; электростатические поля; ультразвук строчной частоты монитора и др.
Необходимо соблюдать простые санитарно-гигиенические и эргономические правила работы на компьютере, в компьютерном зале:
работа с компьютером не более 4-х часов подряд с 10-минутными перерывами после каждого часа интенсивной работы или после 2-х часов менее интенсивной работы;
расстояние от глаз до поверхности экрана – не менее 0,6 м;
перемещаемость клавиатуры относительно экрана в пределах 0,5-1,0 м;
преимущественно желтый, зеленый, серый или светло-голубой фон дисплея;
температура воздуха в помещении – 15-25 градусов по Цельсию;
относительная влажность помещения – 45-75%;
наличие свободной площади рабочего стола не менее 0,3x1,0 м;
размер экрана по диагонали – не меньше 17 дюймов;
разрешение экрана – не менее 800x600;
частота обновления кадра – не менее 70 Гц;
размер зерна экрана (расстояние между точками на экране) – не более 0,26;
частота кадров (мерцание экрана) – не менее 75 Гц;
стандарты безопасности, например MPR-II.
Минимальный объем знаний, который необходим для решения профессиональных задач и приобщения к знаниям, накопленным с помощью компьютера и различных информационных систем и сетей, а также для решения различных бытовых задач с помощью компьютера, называют компьютерной грамотностью.
Лекция 11
Программное и техническое обеспечение
Аннотация: Рассматриваются основные понятия о вычислительной системе – совокупности программного и технического обеспечения, их структура.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Любой компьютер состоит из технического обеспечения (hardware) и функционирует, решает задачи с помощью программного обеспечения (software).
Структура программного обеспечения достаточно сложна и неоднозначна (в том смысле, что все программы не могут быть отнесены к тому или иному классу этой структуры однозначно, односложно). Эта структура несколько условная и производит классификацию программного обеспечения нестрого и только по назначению программ, хотя есть и другие критерии эффективности программного обеспечения (дружественность пользователю, тип использования и т.д.).
Приведем эту структуру.
Базовое программное обеспечение (ПО).
Системное ПО - программы обеспечения взаимодействия пользователя и компьютера.
Операционные системы ( ОС ) - программы ОС ( отладчики, загрузчики и т.д.).
Программы обеспечения связи с устройствами (драйверы), тестирования их.
Инструментальное ПО (программы для массовой разработки других программ).
Трансляторы с языков программирования.
Интерфейсные системы – программы обеспечения дружественного интерфейса.
Проблемно-ориентированные инструментальные системы (САПР, АСУ, АРМ и др.).
Прикладное ПО - программы обеспечения решения прикладных задач пользователя.
Автономные программы (программы, не связываемые с другими из прикладного ПО).
Библиотеки программ (программы, организованные по принципу библиотек книг).
Пакеты прикладных программ, ППП (проблемно-ориентированные прикладные системы).
Интегрированные пакеты прикладных программ - системы, состоящие из связываемых ППП.
Специальное (уникальное) ПО - программы, используемые для решения уникальных проблем).
Структура технического обеспечения приведена ниже и также является условной и классифицирует техническое обеспечение толькопо назначению.
Приведем эту структуру (некоторые блоки могут интегрироваться в другие, например, видеопамять – в блок микропроцессора).
Базовое техническое обеспечение (ТО).
Микропроцессор.
Постоянная ("вшитая") память – ПЗУ.
Оперативная ("адресуемая пользователем") память – ОЗУ.
Регистровая память (аппаратная кэш-память).
Видеопамять (часто интегрируется в блоке микропроцессора).
Блок питания (энергетический блок).
Периферийное ТО (программы обеспечения решения прикладных задач пользователя).
Устройства ввода (клавиатура, мышь, трекбол, сканер, дигитайзер, джойстик и др.).
Устройства вывода (дисплей, принтер, плоттер и др.).
Устройства (накопители) внешней памяти (дискета, СD, оптический накопитель и др.).
Устройства согласования других устройств и сетевые [u3](модем и др.).
Специализированное ТО (устройства, используемые для решения уникальных проблем).
Охарактеризуем программное обеспечение (ПО) компьютера (компьютерной системы, сети).
Наиболее сложный и важный элемент ПО – это ОС.
ОС – совокупность программ, которые обеспечивают нормальную работу всех основных устройств компьютера, всех программ и данных, используемых на компьютере при решении задач.
ОС состоит из двух основных частей – управляющие программы и обрабатывающие программы и включает в себя следующие основные программы:
диспетчер – управляющая программа для координации работы различных устройств ЭВМ, планирования использования и распределения машинного времени, аппаратуры между программами, пересылка программ из ВЗУ в ОЗУ и наоборот, распределение данных в памяти, ввод программ в выделенные участки ОЗУ, управление выполнением задачи, принятие решений в аварийных ситуациях, обнаружение и классификация ошибок и др.;
супервизор – управляющая программа для контроля координации используемых ресурсов и последовательности действий процессора;
отладчик – обрабатывающая программа для отладки программы;
редактор связей – программа для формирования непосредственно выполняемой в памяти программы на машинном языке.
Основными функциями ОС являются:
выполнение очередного по приоритету задания и отслеживание очередности;
управление распределением данных в памяти и извлечением их из памяти;
управление устройствами, их актуализация по мере необходимости (по требованиям программ);
восстановление работоспособности при сбоях;
управление работой арифметико-логического командного устройства процессора.
Данные, привлекаемые при решении задач, ОС с помощью специальных программ отображает на реальные физические структуры, носители данных. [u4]Для этих целей используется так называемая файловая система обмена данными между программами пользователя и ОС.
Файл – именованный структурированный набор однотипных последовательностей данных, обычно хранимый на внешнем носителе и копируемый для работы с ним по мере надобности в ОЗУ. Файловая система должна обеспечивать выполнение основных операций над файлами: создание, модификация (в том числе расширение и сжатие), уничтожение, чтение (запись), перемещение файла.Файловая система ведет справочник файлов, где регистрируются файлы активные, используемые в данном задании в данный момент.
ОС бывают различного типа:
однозадачные, используемые для решения в каждый момент времени только одной задачи;
многозадачные мультипрограммной обработки, загружающие в ОЗУ последовательность (пакет) независимых задач, а затем решающие эти задачи по очереди, выделяя каждой из них ресурсы компьютера (память, процессор, внешнее устройство) на некоторый промежуток времени, например, на 0,1 с (за такой небольшой промежуток времени компьютер с быстродействием 1 млн операций в секунду и очередностью в 10 программ, в каждой программе произведет около 100000 операций);
реального времени, которые обрабатывают порции данных по мере их поступления от источника информации, например от летящей ракеты и др.
Пример. ОС Linux – многопользовательская сетевая ОС с оконным графическим интерфейсом для персональных компьютеров и рабочих станций. Это открытая система ( Open Code System ) – исходные тексты распространяются с лицензией на свободноекопирование, модификацию и установку для неограниченного числа пользователей. Разработана система Линусом Торвалдсом (Linus Torvalds) из университета Хельсинки и модифицируется всеми пользователями и др. Основные возможности ОС Linux:
возможность бесплатного и легального получения и использования исходных кодов ОС ;
высокое быстродействие, надежность, устойчивость, защищенность от вирусов;
эффективная поддержка многопользовательского режима, многозадачности, интерактивности;
интегрируемость компьютера с ОС Linux в различные сети и Интернет;
возможность выполнения загрузочных файлов ОС Unix, DOS и Windows ;
богатый набор инструментальных средств для разработки прикладных программ;
богатая, полная и открытая документация и исходные тексты всех компонент;
использование компьютера на полную мощность, "превращение" его в аналог сервера;
защита памяти процесса, экономная загрузка и динамически изменяемая память;
поддержка национальных алфавитов и соглашений, расширяемость и др.
Программное базовое обеспечение системы Linux:
системы программирования ( C++, Pascal, Perl, ADA, Modula, Prolog, Java, Python и другие);
динамические библиотеки программ;
сетевое обеспечение на базе протоколов TCP/IP ;
поддержка электронной мультимедийной почты;
поддержка основных типов СУБД;
графическая сетевая оконная система;
издательская система TEX , текстовый процессор LyX , основанный на TEX ;
многие другие сотни программ и пакетов.
Пример. Программы обеспечения связей процессора с устройствами бывают различного типа и назначения – драйверы дисплея, клавиатуры, мыши, принтера и т.д. Еще больше различных программ для тестирования (диагностики неисправностей) устройств компьютера – программы тестирования памяти, принтера, дисплея и т.д.
Инструментальная система – это программная система (лучше говорить о программной среде, куда включаем и пользователя, так как именно пользователь, его знания, умения, навыки делают эту систему менее или более эффективной) для ускоренной и малоресурсной разработки каких-то других программ (или обработки данных), как системных или прикладных, так и новых инструментальных.
Пример. Рассмотрим инструментальную среду – графический редактор, который позволяет визуализировать графические объекты двумя основными способами: векторно или растрово. Векторный подход динамически постепенно формирует на экране (который рассматривается как некоторое координатное пространство) объект по его представлению, составленному из графических примитивов. Растровый подход формирует на экране весь объект целиком на основе его макета (шаблона, графических примитивов в видеопамяти), состоящего из отдельных кластеров пикселей в некоторой пиксельной двухмерной матрице (аналоге листа для рисования с декартовой системой координат). В этой матрице записывается информация о яркости и цвете кластера изображения (на один пиксель иногда 1-2 байта и более), а сама матрица может иметь размерность 1024x1024 пикселей и более. Сформированное в пиксельной матрице изображение хранится в видеопамяти дисплея и выводится на экран в режиме кадровой регенерации. Изображение в цвете (рисование в цвете) – это манипуляция пикселями этой матрицы. Графические 3D -редакторы изображений позволяют не только конструировать 3D -объекты, но и перемещать их по задаваемой траектории, то есть осуществлять анимацию. Одной из мощных графических сред является пакет 3D -Studio Max фирмы Autodesk. Кроме этого пакета, широко используются графические пакеты:
GRAFLotus Freelance – для работы с деловой и компьютерной графикой;
Splash и Fanta – для работы в области дизайна и компьютерных фильмов;
AutoCAD – для автоматизации проектно-конструкторских работ;
CorelDraw, PaintBrush, AdobeIllustrator – для разнообразных приложений.
Трансляторы подробно рассматриваются нами ниже.
Рассмотрим интерфейсные системы обеспечения дружественного интерфейса между пользователями и программами.
Пример. Наиболее ранняя интерфейсная система – Norton Commander (Нортон Коммандер, автор – Питер Нортон). Системы, подобные Norton Commander (NC), называются операционными оболочками и их можно отнести к инструментальным средам (инструментарий более удобного, комфортного интерфейса с ОС, с файловой системой, минуя утомительный командный язык ОС ). Такая система позволяет визуально и удобно выполнять копирование, создание, удаление, переименование, перемещение, просмотр и поиск файлов и т.д. NC использует управляющие и функциональные клавиши, которым соответствуют определенные операции и отклики системы:
Esc – отмена выполняемой функции;
Enter – выполнение функции;
Т ab – смена текущей (активной) панели на другую (ранее пассивную);
PgUp (PgDn) – переход на страницу вперед (назад);
Home (End) – установка на начало (конец) каталога;
, , , – клавиши перемещения курсора влево, вверх, вправо, вниз;
Ctrl-S (одновременное нажатие клавиш Ctrl и S ) на символ влево;
Ctr-D (Ctr-A,Сtrl-F) – на символ вправо (на слово влево, на слово вправо);
F1 – клавиша помощи, подсказки по активному состоянию (клавиша help);
F2 – запись на диск активного файла ;
F3 – просмотр содержимого активного файла ;
F4 – редактирование активного файла ;
F5 – копирование активного файла в активный каталог на другой панели;
F6 – переименование (перенос) активного файла ;
F7 – создание нового каталога (подкаталога);
F8 – удаление активного файла ;
F9 – активизация команд панели (системного меню) NC ;
F10 – выход из NC.
Более развитым отечественным аналогом NC для Windows -систем является, например, оболочка FAR -менеджер ([ Cкачайте файл, чтобы посмотреть ссылку ]).
[ Cкачайте файл, чтобы посмотреть ссылку ]
Рис. 11.1. Интерфейс FAR-менеджера
Проблемно-ориентированные инструментальные системы служат для решения достаточно широкого класса задач некоторой профессиональной, проблемной ориентации: САПР – системы автоматизации проектирования, АСУ – автоматизированные системы управления, АРМ – автоматизированные рабочие места, СУБД – система, обеспечивающая интерфейс программ пользователя и данных из базы данных, ЭС – экспертные системы, системы накопления, хранения и актуализации опыта, знаний, умений, навыков (экспертных суждений) экспертов и др.
Автономные программы – это те программы, которые в громадном количестве ежедневно разрабатываются и используются для различных прикладных целей (обучения, вычисления, моделирования и т.д.).
Библиотеки программ – совокупность программ для решения задач определенной направленности (например, решения систем алгебраических уравнений), с описанием, каталогом, инструкциями и размещенные на внешних носителях таким образом, чтобы иметь возможность легко подключаться к решаемой задаче (к выполняемой программе) по ходу ее решения.
Пакет прикладных программ (ППП) состоит из следующих обязательных частей:
описание, представление класса задач, решаемых с помощью ППП ;
комплекс программ, обеспечивающих построение прикладных программ ППП (технологической цепочки);
комплекс прикладных программ, обеспечивающих решение задач из предметной области ППП ;
входной язык (язык запросов) ППП ;
база данных для хранения данных, передача их модулям ППП ;
монитор (управляющая программа) ППП, обеспечивающая ввод задания (запроса), его расшифровку и построение технологической цепочки из модулей ППП для поиска ответа.
Пример. Простым и универсальным студенческим пакетом статистического анализа данных является пакет SPSS. Интерфейспользователя с SPSS для Windows реализуется с помощью простых меню и диалоговых окон, то есть SPSS свободна от использования специально изучаемого командного языка пакета. Имеется редактор Data Editor для визуального контроля вводимых данных, функционально аналогичный редакторам табличных процессоров, например, Excel. По столбцам отображаются варьируемые переменные, а по строкам – наборы их вариации, причем с каждой из переменных можно ознакомиться путем вызова ее имени. Ввод данных – аналогичен вводу данных табличного типа (например, в Excel ). В диалоговых окнах можно определять (вводить или вычислять) сложные выражения, используемые далее в расчетах. Есть возможность применения различных законов случайного распределения. Более мощным (но и более сложным в изучении и использовании) является математический пакетMathCAD.
Функциональная система интегрированного пакета программ состоит не из модулей (как в ППП), а из ППП.
Пример. Наиболее распространенный интегрированный пакет прикладных программ – MS Office (пакет автоматизации работы в офисе). В его ядро входят следующие пакеты: Word – текстовый редактор, Excel – электронная таблица, Access – СУБД, PowerPoint – система презентации и др.
Специальное (или уникальное) ПО разрабатывается для решения очень важных, уникальных проблем.
Пример. К такому классу ПО можно отнести программную систему управления кораблем "Буран".
Лекция 12
Формальные языки и грамматики
Аннотация: Рассматриваются основные сведения о формальных и естественных языках, грамматиках, типах грамматик, грамматическом анализе, переводе с языков, типах трансляторов.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ]
Математический язык как форма выражения научного знания использовался еще в древности при решении практических задач.
Большую роль в развитии математики как языка – метаязыка наук – сыграла математическая логика, аксиоматизировавшая ряд теории, изучившая их логику, внутреннюю структуру.
Развитие информатики, особенно таких ее разделов, как теория формальных языков, грамматик, структур, алгоритмических языкови методов трансляции баз данных и знаний и других приводит к развитию, углублению, формализации и структурированию предметов наук.
В свою очередь, появилась возможность моделирования языковых структур, формализации, структурирования ряда языков общения, анализа и построения различного рода текстов и словарей, в том числе – их автоматического построения.
Язык, определенный с помощью алфавита (над алфавитом) X = {x1, x2, ... , xn} , – это некоторая устная, звуковая, письменная или иная форма выражения слов над X, включая синтаксис – правила образования структур из слов и словосочетаний, семантику – правила проверки правильности, смысловой однозначности и совместимости синтаксических конструкций языка, состоящих из лексем. Для устных языков (общения) нужна и фонетика – правила произношения составных частей предложения, то есть фонем.
Язык как коммуникативный аппарат должен иметь определяющие конструкции слов над данным алфавитом, грамматические правила образования предложений из слов и соотнесения этих предложений тем явлениям и процессам, которые они описывают, или синтаксическим и семантическим правилам.
Пример. В частности, семантика изучает связи вида:
"знак, структура знаков значение объект";
синтаксис – связи вида:
"знак, структура знаков объект".
Основные функции любого языка – отображение, передача, сжатие, хранение, актуализация информации с помощью сообщений на этом языке.
Пример. Запишем более кратко, сжато, точно (формализованно) факт "целое число x делится на целое число y без остатка". На математическом языке это будет иметь вид "Число x кратно числу y ". Факт, что числа x, y – целые, уже можно специально, как выше, не оговаривать, так как математическое понятие кратности это уже предполагает (аксиома). Запишем еще более кратко и формализованно на алгоритмическом языке Паскаль: " x mod y = 0 ". Здесь уже условие кратности область изменения аргументов не нужно оговаривать – они декларированы в языке Паскаль (в описаниях типов и операции mod ).
Языки бывают естественного происхождения (например языки общения) и искусственного происхождения или формальные языки, разрабатываемые для общения человека с автоматом (компьютером) либо для описания и получения знаний.
Пусть X – некоторый алфавит, X = {x1, x2, ... , xn} , а S(X) – множество слов над алфавитом X, тогда S(X) – бесконечное и счетное множество.
Формальный язык L(X) – произвольное подмножество S(X).
Формальный язык использует естественный язык как лексическую форму оформления входящих в него абстрактных объектов, какметаязык или язык для описания синтаксиса другого языка. Описываемый метаязыком язык в этом случае называется объектнымязыком (по отношению к метаязыку ).
Формальная грамматика G состоит из совокупностей: T = {t1, t2, ... , tk} – множество терминальных символов языкаили множество основных понятий языка ; N = {n1, n2, ..., nm} – множество нетерминальных символов языка или вспомогательных понятий, обозначений конкретных классов слов, например, глаголов или предлогов, причем во множестве Nсодержится n0 – начальный символ из N ; P = {p1, p2, ..., pq} – система подстановок (продукции) слов вида в слова или замен всех слов s1(x) в рассматриваемой системе соотношений на слова вида s2(x) .
Язык (множество слов S(X) ) задается грамматикой G(S) – структурой правил, которые позволяют порождать все слова и только их.
Грамматический анализ – процесс редукции к нетерминальному символу или слову.
Множество – словарь грамматики G. Правила вывода – это непустое множество правил вида , где , а " " – отношение вида "левое (можно) заменить на правое".
Слово выводимо из слова с помощью правила , если , . Последовательность называется выводом gиз f, если fi+1 выводимо из fi для всех . Признаком завершения процесса (последовательности) вывода является отсутствие слова, выводимого из g.
Пример. Опишем элементы естественного, например, русского языка в терминах формальных грамматик. Алфавит языка X = {А, а, Б, б, ... , Я, я, ., ,, :, ;, ., !, ?, ", ", (, )}, T={<корни>, <приставки> и т.д.}, N = {предложение, подлежащее, сказуемое, глагол, местоимение и т.д.}, n0 = "предложение" . Например, пусть
Т = {арбуз, банан, красный, греет, загорает, бок},
N = {сказуемое, подлежащее, определение, дополнение, группа подлежащего, группа сказуемого},
n0 = {предложение} ,
P = {p1: предложение (группа подлежащего), (группа сказуемого ),
p2: группа подлежащего (определение)(подлежащее) ,
p3: группа сказуемого (сказуемое) (дополнение) ,
p4: определение "красный" ,
p5: подлежащее "арбуз" ,
p6: подлежащее "банан" ,
p7: сказуемое "греет" ,
p8: дополнение "банан" ,
p9: дополнение "бок"} .
Тогда справедливы следующие выводы:
предложение (группа подлежащего)(группа сказуемого)
(определение) (подлежащее) (группа сказуемого)
(определение) (подлежащее) (сказуемое) (дополнение)
"красный" (подлежащее) (сказуемое )(дополнение)
"красный арбуз" (сказуемое) (дополнение)
"красный арбуз греет" (дополнение)
"красный арбуз греет бок".
Таким образом, мы по формальным правилам построили предложение естественного языка.
Различают четыре основных типа формальных грамматик.
Грамматика типа 0 (G–0) – грамматика, в которой нет ограничений на правила вывода (то есть в правиле вывода , f иg – любые).
Грамматика типа 1 (G–1) – грамматика, в которой содержатся правила вида , где n– нетерминальный символ , f1 , f2 , w – цепочки из словаря W.
Грамматика типа 2 (G–2) – грамматика, в которой допустимы лишь правила вида .
Грамматика типа 3 (G–3) имеет правила вида , либо , где .
Грамматики типа G–0 называются свободными, типа G–1 – контекстно-зависимыми, типа G–2 – контекстно-свободными, типа G–3 – регулярными или автоматными.
Выражение, записанное на метаязыке с помощью конечного (счетного) числа операций и операндов, называется регулярным выражением.
В формальных грамматиках рассматриваются три основные проблемы:
проблема вхождения – построить алгоритм, который для каждого задаваемого слова выясняет, принадлежит ли оно языку, допускаемому данной грамматикой ;
проблема анализа – построить алгоритм, который для каждого слова, допускаемого данной грамматикой, строит вывод этого слова;
проблема оценки сложности алгоритма вывода (вычислений).
Если первые две задачи – более "грамматического" характера, то третья задача – более "алгоритмического" характера.
С появлением компьютеров повысились требования к точности и структурированности алгоритма. Для этих целей разрабатываются алгоритмические языки. Это формальный язык, формализованный язык, так как он включает в себя и математическую символику, например, числа, знаки операций, переменные, выражения и др.
Алгоритмический язык – средство записи алгоритмов для исполнения, изучения логики алгоритма. Основное отличие алгоритмического языка от языка программирования (хотя их часто отождествляют) состоит в том, что последний предназначен для записи и исполнения алгоритмов в виде, понятном и исполнимом ЭВМ.
Основные атрибуты языка алгоритмического (программирования):
константы – постоянные величины (числовые, символьные, логические);
символы – знаки, имеющие различные коды при переводе;
идентификаторы – имена, именования различных объектов алгоритма;
переменные – для именования изменяемых величин, параметров;
метки – именования различных частей, участков алгоритмов;
процедуры – функционально завершенные именованные части алгоритма;
описания – соглашения о типе, характере, структуре используемых данных и стандартизации представления (описания) данных;
комментарии – пояснения к различным участкам алгоритма;
операторы – команды преобразования используемых, получаемых данных или изменения порядка их выполнения;
выражения – записи, образуемые из постоянных, переменных и знаков операций и являющиеся источниками значений; сюда отнесем и функции стандартные (встроенные), с которыми можно оперировать, как и с переменными, в соответствии с их атрибутами.
Любые математические выражения записываются на алгоритмических языках по правилам не только математики, но и этого языка.
Пример. На алгоритмическом языке Паскаль математическое выражение
будет записано в виде y = exp(x*ln(2)) + 3*sin(x – 4/5)*ln(x + sqrt(x + 5)).
Пример. Выражению Паскаля w = sqrt(sqr(b + c) + 2/a*x/c) соответствует математическое выражение вида .
Вычисление значений выражений на алгоритмическом языке происходит в соответствии с принятым в языке старшинством операций.
Пример. Найдем b = ln(ехр(5)) + min(max(3,2),6) + mod(15,4)*int(1.99). Результат равен: b = 5 + min(3,6) + 3*1 = 5 + 3 + 3 = 11.
Первые ЭВМ поставлялись без программного обеспечения, и программисту приходилось описывать в программе все необходимое для ее работы. Разработка первых алгоритмических языков (например ForTran) упростила программирование, увеличила число людей, решающих на компьютере свои задачи без привлечения программистов, положила начало двум основным направлениям в программировании: прикладному и системному программированию, а затем и третьему – инструментальному программированию.
Прикладной программист (обычно на языках программирования высокого уровня) разрабатывает программы решения конкретных естественнонаучных задач.
Системный программист (обычно на языках программирования низкого уровня) разрабатывает программы автоматизации процесса написания и отладки прикладных программ, распределения ресурсов между прикладными программами, управления процессом прохождения таких прикладных программ на ЭВМ, например разрабатывает ОС.
Язык считается тем более высокого уровня, чем более он близок к языку естественному, и считается тем более низкого уровня, чем он ближе к языкам, реализуемым аппаратно, машинным.
Охарактеризуем эти уровни алгоритмических языков:
языки запросов (непроцедурные языки ) предназначены для осуществления диалога с некоторым пакетом прикладных программ, это языки имитационного моделирования, в частности язык SLAM и др.;
языки высокого уровня (проблемно-ориентированные языки ) предназначены для решения определенного, но достаточно широкого класса задач, например, вычислительного характера или обработки текстов (символов) это, к примеру, языкиFORTRAN, BASIC, LISP и др.;
ассемблеры (семейство языков ), предназначены для укрупнения и символической (мнемонической) записи машинных команд;
языки микроопераций ( языки разработки микропрограмм) собственно говоря, это и есть языки машинных операций.
Языки по типу их использования и сферам применения можно делить условно на следующие типы (это – не полная их классификация):
языки процедурные;
языки непроцедурные;
языки функционального программирования;
языки моделирования;
языки аналитических преобразований;
языки эвристические;
языки описания, представления объектных языков или метаязыки.
Возможно и такое деление языков (отражающее характер их использования):
метаязыки, языки описания других языков;
языки описания, формулирования задач;
языки описания технологии, сценариев решения задач;
языки описания, разработки программ решения задач (или кодирования алгоритмов, часто вычислительного характера);
языки описания, представления знаний (фреймовые языки);
языки описания, представления данных;
языки описания, формулировки решений задач.
В мире разработано несколько тысяч языков различного назначения.
Пример. Отметим следующие языки, которые оказали наибольшее влияние и преемственность в развитии языков программирования:
ФОРТРАН, язык научно-технических расчетов, разработан в 1955 году фирмой IBM;
АЛГОЛ, язык вычислительного характера, разработан в 1960 году Международным комитетом ученых;
БЕЙСИК, простой язык для начинающих, разработан в 1965 году в Дортмунде;
ПАСКАЛЬ, разработан в качестве языка учебного и исследовательского характера в 1969 году в Цюрихе Н. Виртом;
СИ, разработан лабораторией BELL (США, 1972 г.) в качестве языка поддержки и программирования ОС UNIX;
ПРОЛОГ, язык логического программирования, разработан Колмероэ в 1971-1973 годах;
ПИТОН (ПАЙТОН), разработан в начале 1990-х годов Гвидо ван Россумом и является простым объектно-ориентированнымязыком, расширяемым, совершенствуемым пользователями;
JAVA – язык, ориентированный на сеть Интернет и серверы WWW; рассмотрим этот язык подробнее ниже;
HTML, предложен Тимом Бернерсом-Ли в 1989 году в качестве поддержки WWW-документов.
ЭВМ может исполнять программы, написанные на ее машинном языке, в машинных кодах. Для перевода с других языков на машинный язык составляется специальная программа, называемая транслятором. Алгоритм (программа на языке программирования) преобразуется в корректную последовательность команд и данных, загружаемых в память ЭВМ и выполняемых в ней аппаратно. Чем выше уровень используемого при составлении программы исходного языка, тем больше работ по трансляции программы.Транслятор переводит программу с исходного языка программирования на машинный язык загрузки ее в память и исполнения.
Существует два основных режима трансляции: компиляция и интерпретация. При интерпретации перевод на язык машины и выполнение каждой команды исходной программы осуществляется последовательно, покомандно, а полученная машиннаяпрограмма пригодна только для одноразового решения задачи; данные вводятся при этом по мере трансляции. При компиляции до выполнения программы осуществляется полный перевод всей программы на машинный язык ЭВМ, затем полученная программаредактируется и загружается со всеми необходимыми для выполнения транслированной программы программами ОС в память ЭВМ и получается так называемый загрузочный модуль. Загрузочный модуль пригоден для многократного использования без повторнойтрансляции.
Пример. Язык Бейсик имеет трансляторы различного типа. Например, в среде TurboBasic (TBasic) – транслятор-интерпретатор, а в среде QuickBasic (QBasic) – транслятор-компилятор. Программа для TBasic интерпретируется по циклу: "ввод команды – перевод команды на внутренний машинный язык – ввод данных для данной команды – исполнение". Программа для QBasic компилируется по циклу: "перевод всех команд программы на внутренний язык – исправление ошибок в программе – ввод данных для программы –исполнение всей программы".
Лекция 13
Введение в моделирование объектов процессов и явлений
Аннотация: Рассматриваются основные понятия моделирования (особенно, математического и компьютерного), типы и свойства моделей, жизненный цикл моделирования.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Модель и моделирование – это универсальные понятия, атрибуты одного из наиболее мощных методов познания в любой профессиональной области, познания объекта, процесса, явления (через модели и моделирование ).
Модели и моделирование объединяют специалистов различных областей, работающих над решением межпредметных проблем, независимо от того, где эта модель и результаты моделирования будут применены.
Модель – это некоторое представление или описание оригинала (объекта, процесса, явления), которое при определенных предложениях, гипотезах о поведении оригинала позволяет замещать оригинал для его лучшего изучения, исследования, описания его свойств.
Пример. Рассматривая физическое тело, брошенное с высоты h и падающее свободно в течение t времени, можно записать соотношение: h = gt2/2 . Это физико-математическая модель системы (математическая модель физической системы) пути при свободном падении тела. При построении этой модели приняты следующие гипотезы: 1) падение происходит в вакууме (то есть коэффициент сопротивления воздуха равен нулю); 2) ветра нет; 3) масса тела неизменна; 4) тело движется с одинаковым постоянным ускорением g в любой точке.
Слово "модель" (лат. modelium) означает "мера", "способ", "сходство с какой-то вещью".
Проблема моделирования состоит из трех взаимосвязанных задач: построение новой (адаптация известной) модели ; исследование модели (разработка метода исследования или адаптация, применение известного); использование (на практике или теоретически) модели.
Схема построения модели М системы S с входными сигналами X и выходными сигналами Y изображена на [ Cкачайте файл, чтобы посмотреть ссылку ].
[ Cкачайте файл, чтобы посмотреть ссылку ]
Рис. 13.1. Схема построения модели
Если на вход М поступают сигналы из X и на выходе появляются сигналы из Y, то задан закон, правило f функционированиямодели, системы.
Классификацию моделей проводят по различным критериям.
Модель – статическая, если среди параметров описания модели нет (явно) временного параметра.
Модель – динамическая, если среди параметров модели явно выделен временной параметр.
Модель – дискретная, если описывает поведение оригинала лишь дискретно, например в дискретные моменты времени (длядинамической модели ).
Модель – непрерывная, если описывает поведение оригинала на всем промежутке времени.
Модель – детерминированная, если для каждой допустимой совокупности входных параметров она позволяет определять однозначно набор выходных параметров; в противном случае – модель недетерминированная, стохастическая (вероятностная) .
Модель – функциональная, если представима системой функциональных соотношений (например, уравнений).
Модель – теоретико-множественная, если представима некоторыми множествами и отношениями их и их элементов.
Модель – логическая, если представима предикатами, логическими функциями и отношениями.
Модель – информационно-логическая, если она представима информацией о составных элементах, подмоделях, а также логическими отношениями между ними.
Модель – игровая, если она описывает, реализует некоторую игровую ситуацию между элементами (объектами и субъектами игры).
Модель – алгоритмическая, если она описана некоторым алгоритмом или комплексом алгоритмов, определяющим ее функционирование, развитие. Введение такого, на первый взгляд, непривычного типа моделей (действительно, кажется, что любаямодель может быть представлена алгоритмом ее исследования), на наш взгляд, вполне обосновано, так как не все модели могут быть исследованы или реализованы алгоритмически.
Модель – графовая, если она представима графом (отношениями вершин и соединяющих их ребер) или графами и отношениями между ними.
Модель – иерархическая (древовидная), если она представима иерахической структурой (деревом).
Модель – языковая, лингвистическая, если она представлена некоторым лингвистическим объектом, формализованной языковой системой или структурой. Иногда такие модели называют вербальными, синтаксическими и т.п.
Модель – визуальная, если она позволяет визуализировать отношения и связи моделируемой системы, особенно в динамике.
Модель – натурная, если она есть материальная копия оригинала.
Модель – геометрическая, если она представима геометрическими образами и отношениями между ними.
Модель – имитационная, если она построена для испытания или изучения, проигрывания возможных путей развития и поведения объекта путем варьирования некоторых или всех параметров модели.
Есть и другие типы моделей.
Пример. Модель F = am – статическая модель движения тела по наклонной плоскости. Динамическая модель типа закона Ньютона: F(t) = a(t)m(t) или, еще более точно и лучше, F(t)=s''(t)m(t). Если рассматривать только t = 0.1, 0.2, , 1 (с), то модель St = gt2/2 или числовая последовательность S0 = 0, S1 = 0.01g/2, S2 = 0.04g, , S10 = g/2 может служить дискретной моделью движения свободно падающего тела. Модель S = gt2/2, 0 < t < 10 непрерывна на промежутке времени (0;10).
Пусть модель экономической системы производства товаров двух видов 1 и 2, соответственно, в количестве x1 и x2 единиц и стоимостью каждой единицы товара a1 и a2 на предприятии описана в виде соотношения a1x1 + a2x2 = S , где S – общаястоимость произведенной предприятием всей продукции (вида 1 и 2). Можно ее использовать в качестве имитационной модели, определяя общую стоимость S в зависимости от тех или иных значений объемов производимых товаров. Приведенные выше физические модели – детерминированные.
Если в модели S= gt2/2, 0 < t < 10 мы учтем случайный параметр – порыв ветра с силой p при падении тела, например, просто так: S(p) = g(p)t2/2, 0 < t < 10 , то мы получим стохастическую модель (уже не свободного!) падения. Это – такжефункциональная модель.
Для множества X = {Николай, Петр, Николаев, Петров, Елена, Екатерина, Михаил, Татьяна} опишем отношения Y: "Николай – супруг Елены", "Екатерина – супруга Петра", "Татьяна – дочь Николая и Елены", "Михаил – сын Петра и Екатерины". Тогда множества X и Y могут служить теоретико-множественной моделью двух семей.
Совокупность двух логических функций вида: может служить логической модельюодноразрядного сумматора компьютера.
Пусть игрок 1 – добросовестный налоговый инспектор, а игрок 2 – недобросовестный налогоплательщик. Идет "игра" по уклонению от налогов (с одной стороны) и по выявлению сокрытия уплаты налогов (с другой стороны). Игроки выбирают натуральные числаi и j ( ), которые можно отождествить, соответственно, со штрафом игрока 2 за неуплату налогов при обнаружении факта неуплаты игроком 1 и с временной выгодой игрока 2 от сокрытия налогов. Каждый элемент этой матрицы A определяется по правилу aij = |i – j| . Модель игры описывается этой матрицей и стратегией уклонения и поимки.
Алгоритмической моделью вычисления суммы бесконечного убывающего ряда чисел может служить алгоритм вычисления конечнойсуммы ряда до некоторой заданной степени точности.
Правила правописания – языковая, структурная модель. Глобус – натурная географическая модель земного шара. Макет дома является натурной геометрической моделью строящегося дома. Вписанный в окружность многоугольник дает визуальнуюгеометрическую модель окружности на экране компьютера.
Тип модели зависит от связей и отношений его подсистем и элементов, окружения, а не от его физической природы.
Пример. Математические описания ( модели ) динамики эпидемии инфекционной болезни, радиоактивного распада, усвоения второго иностранного языка, выпуска изделий производственного предприятия и т.д. являются одинаковыми с точки зрения их описания, хотя процессы различны.
Основные свойства любой модели:
целенаправленность;
конечность;
упрощенность;
приблизительность;
адекватность;
информативность;
полнота;
замкнутость и др.
Жизненный цикл моделируемой системы:
сбор информации;
проектирование;
построение;
исследование;
оценка;
модификация.
Наука моделирования состоит в разделении процесса моделирования (системы, модели ) на этапы (подсистемы, подмодели), детальном изучении каждого этапа, взаимоотношений, связей, отношений между ними и затем эффективного описания их с максимально возможной степенью формализации и адекватности.
Приведем примеры применения математического, компьютерного моделирования в различных областях:
энергетика: управление ядерными реакторами, моделирование термоядерных процессов, прогнозирование энергетических процессов, управление энергоресурсами и т.д.;
экономика: моделирование, прогнозирование экономических и социально-экономических процессов, межбанковские расчеты, автоматизация работ и т.д.;
космонавтика: расчет траекторий и управления полетом космических аппаратов, моделирование конструкций летательных аппаратов, обработка спутниковой информации и т.д.;
медицина: моделирование, прогнозирование эпидемий, инфекционных процессов, управление процессом лечения, диагностика болезней и выработка оптимальных стратегий лечения и т.д.;
производство: управление техническими и технологическими процессами и системами, ресурсами (запасами), планирование, прогнозирование оптимальных процессов производства и т.д.;
экология: моделирование загрязнения экологических систем, прогноз причинно-следственных связей в экологической системе, откликов системы на те или иные воздействия экологических факторов и т.д.;
образование: моделирование междисциплинарных связей и систем, стратегий и тактик обучения и т.д.;
военное дело: моделирование и прогнозирование военных конфликтов, боевых ситуаций, управления войсками, обеспечение армий и т.д.;
политика: моделирование и прогнозирование политических ситуаций, поведения коалиций различного характера и т.д.;
социология, общественные науки: моделирование и прогнозирование поведения социологических групп и процессов, общественного поведения и влияния, принятие решений и т.д.;
СМИ: моделирование и прогнозирование эффекта от воздействия тех или иных сообщений на группы людей, социальные слои и др.;
туризм: моделирование и прогнозирование потока туристов, развития инфраструктуры туризма и др.;
проектирование: моделирование, проектирование различных систем, разработка оптимальных проектов, автоматизация управления процессом проектирования и т.д.
Современное моделирование сложных процессов и явлений невозможно без компьютера, без компьютерного моделирования.
Компьютерное моделирование – основа представления (актуализации) знаний как в компьютере, так и с помощью компьютера и с использованием любой информации, которую можно актуализировать с помощью ЭВМ.
Разновидность компьютерного моделирования – вычислительный эксперимент, осуществляемый экспериментатором над исследуемой системой или процессом с помощью орудия эксперимента – компьютера, компьютерной технологии. Вычислительный эксперимент позволяет находить новые закономерности, проверять гипотезы, визуализировать события и т.д.
Компьютерное моделирование от начала и до завершения проходит следующие этапы.
Постановка задачи.
Предмодельный анализ.
Анализ задачи.
Исследование модели.
Программирование, проектирование программы.
Тестирование и отладка.
Оценка моделирования.
Документирование.
Сопровождение.
Использование (применение) модели.
Пример. Рассмотрим популяцию рыб, из которой в текущий момент времени изымается некоторое количество особей (идет лов рыбы). Динамика такой системы определяется моделью вида: xi + 1 = xi + аxi – kxi, х0 = c , где k – коэффициент вылова (скорость изъятия особей). Стоимость одной пойманной рыбы равна b руб. Цель моделирования прогноз прибыли при заданной квоте вылова. Для этой модели можно проводить имитационные вычислительные эксперименты и далее модифицировать модель, например следующим образом.
Эксперимент 1. Для заданных параметров a, c изменяя параметр k, определить его наибольшее значение, при котором популяция не вымирает.
Эксперимент 2. Для заданных параметров c, k изменяя параметр a, определить его наибольшее значение, при котором популяция вымирает.
Модификация 1. Учитываем естественную гибель популяции (за счет нехватки пищи, например) с коэффициентом смертности, равным, b: xi + 1 = xi + аxi – (k + b)xi, х0 = c .
Модификация 2. Учитываем зависимость коэффициента k от x (например, k = dx ): .
Лекция 14
Введение в информационные технологии
Аннотация: Обзор и классификация новых информационных технологий, тенденции развития этих технологий.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ]
Процесс получения (актуализации) и хранения в компактном виде (структур данных) называется в информатике информационной технологией.
Новая информационная технология – информационная технология на базе новых, компьютерных средств получения, хранения, актуализации информации (знаний).
В узком понимании, новая информационная технология – использование вычислительной техники и систем связи для создания, сбора, передачи, хранения, обработки информации или часть информационного бизнеса.
Взглянем на новые информационные технологии, ограничиваясь их содержательным простым обзором, с учетом того, что две важные информационные технологии – математическое и компьютерное, имитационное моделирование уже были нами рассмотрены выше. Отметим лишь, что математическое моделирование – "старая" информационная технология, в отличие от компьютерного моделирования, являющегося новой технологией.
Технология баз данных (БД) и систем управления БД ( СУБД ). БД – достаточно большие наборы структурированных данных некоторой предметной области, представленные на машинных носителях и имеющие общую и удобную структуру, единые организационно-методические, программно-технические и языковые средства обеспечения использования данных различными программами пользователей. В последнее время распространяется технология удаленных БД. Она базируется на коллективном доступе пользователей к информационным ресурсам, сосредоточенным на едином компьютере ( хост-компьютере ), в диалоговом режиме по сетям передачи данных. Информационные услуги – широкие, благодаря наличию разнообразных средств поиска, обработки и выдачи информации. Особенность данной технологии – предоставление пользователю только информационных услуг, а не непосредственно информационных продуктов, в результате чего он получает (оплачивает) только действительно нужную информацию.
СУБД – программная система, обеспечивающая общение (интерфейс) программ пользователя и данных из БД. Это общение происходит на специальном непроцедурном языке логического представления данных и структур данных, сами данные описываются средствами также специального языка представления данных, программы пользователя при этом могут быть написаны на языке программирования. СУБД должна иметь средства, которые позволяют сформулировать запрос к БД (поиск, сортировка и т.д.) на языке, близком естественному и понятному пользователю, но в то же время формальному, реализованному на ЭВМ. Такие языки называются языками запросов к базам данных и относятся к языкам непроцедурного типа.
Пример. База данных ГИБДД всех владельцев автотранспорта, из которой по запросам сотрудников ГИБДД можно оперативно извлечь, скажем, данные о владельце машины по номеру ее госрегистрации.
Технологии хранилищ данных и интеллектуального анализа данных. Хранилище данных – очень большая специализировнная БДи программная система, предназначенная для извлечения, коррекции (чистка, правка) и загрузки данных из источников в БД с многомерной структурой, включая средства упрощения доступа, анализа с целью принятия решения. Интеллектуальный анализ данных ( Data Mining ) – автоматический поиск скрытых ("не лежащих на поверхности") в больших базах данныхвзаимоотношений и связей с помощью математического и инфологического анализа, выделения законов (трендов), классификации и распознавания и т.д. Специальные модели и алгоритмы анализа извлекают из больших баз данных или из других хранилищ данных, например, электронных таблиц) знания, позволяющие агрегировать, интегрировать и детализировать эти данные, и самое главное – принимать на их основе решения. Это, по сути, идентификация скрытых в них зависимостей.
Пример. Хранилища данных собирают и централизуют текущую информацию о состоянии дел корпорации, о ее услугах, клиентах, поставщиках и предоставляют аналитические и отчетные инструменты. С помощью анализа финансовых отчетов фирм можно их разбить на классы по их финансовой устойчивости, по вероятности их банкротства, что поможет банку-кредитору осуществлять политику их кредитования более эффективно. Интеллектуальный анализ данных в геоинформационных системах может помочь обнаружить и визуализировать участки земной коры с залежами нефти, газа, сейсмоопасные. В бизнесе такой анализ может осуществляться для оценки надежности клиентов, выявления мошенничества, интерактивного маркетинга, анализа трендов и др. то есть для Business Intellegence.
Технология баз знаний (БЗ) и экспертных систем (ЭС). БЗ – накопление, структурирование и хранение с помощью ЭВМ знаний, сведений из различных областей таким организованным способом, что можно иметь доступ к этим знаниям, расширять эти знания, получать, выводить новые знания и т.д.
Пример. БЗ по хирургическим операциям брюшной полости, из которой молодой и неопытный хирург в экстренной хирургической ситуации может извлечь необходимую информацию об операции; сама же БЗ разработана на основе знаний высокопрофессиональных и опытных хирургов.
ЭС – накопление опыта, знаний, умений экспертов, их структурирование и хранение, актуализация с помощью ЭВМ с целью получения экспертных суждений по различным проблемам данной области.
Пример. Примером ЭС "Хирург" может быть экспертная система, построенная на основе приведенного выше примера БЗ.
Технология электронной почты и телекоммуникационного доступа к удаленной от пользователя информации, носителю информации, собеседнику – человеку или компьютеру. Электронная почта – система передачи сообщений с помощью компьютера отправителя и приема их с помощью компьютера получателя. При этом сообщение отправителя преобразуется из цифровых кодов (например с помощью модема) в коды электромагнитных колебаний, передаваемые по телефонным каналам, а ЭВМ адресата производит обратное преобразование. Развитие сетей связи – виртуальные локальные вычислительные сети, объединяющие пользователей не по территориальному принципу, а по профессиональным интересам. Телеконференция – обмен сообщениями (докладами) между участниками (подписчиками) конференции, объявленной на электронной доске объявлений в сети Интернет. С помощью телеконференций можно проводить консалтинг, обучение, совещание, автоматизацию офиса и др. Базовая система проведения видеоконференций обычно включает: мощную рабочую мультимедийную станцию; видеокамеру и специальную плату для сжатия видеоинформации; микрофон и видеомагнитофон; средства сопряжения с используемой для проведения конференции сетью.
Пример. Рассмотрим медицинские видеоконференции (яркий социально-экономический пример использованиятелеконференции ). В крупных больницах и клиниках сейчас имеется современное медицинское оборудование – томографы, эхокардиографы и др., а также достаточно высококвалифицированный медицинский персонал, с помощью которых в режиме видеодиалога (конференции), врачи из региональных (вплоть до районных) медицинских учреждений могут обсудить результаты диагностики больного, диагноза, методов и стратегий лечения. Проблема "приближения" этих средств и кадров особенно актуальна для нашей страны с ее большой территорией. Экономическая и социально-медицинская выгода от таких видеоконференций в 6-10 раз выше, чем от классической технологии проведения консультаций с выездом в клинику (иногда это и невозможно).
Технология (использования) автоматизированных систем (АС) и автоматизированных рабочих мест (АРМ). АС – это человеко-машинная система для выполнения ежедневных, часто рутинно производимых на рабочем месте действий, с целью уменьшения времени, ошибок и обеспечения оперативной связи с другими сотрудниками; интеллектуальные системы имеют также и способность к перестройке технологической цепочки, имеют способность к обучению.
АРМ – предметно-ориентированная инструментальная АС, предназначенная для автоматизации профессиональных работ (сидящего за данным рабочим столом сотрудника). Можно их определить как автоматизированные системы локального характера, соответствующие некоторому функциональному назначению.
Пользовательский интерфейс с АРМ часто организуется с помощью понятия рабочего стола на экране. Экран делится на три части (три объекта). Первая (обычно верхняя) часть – строка меню, с ее помощью осуществляется доступ к другим объектам. Вторая часть (обычно нижняя) называется строкой состояния, с ее помощью быстро вызываются часто используемые объекты или отображается важная текущая информация. Третья часть (основная, средняя часть экрана) называется рабочей поверхностью (поверхностью стола), с ее помощью отображаются все объекты, вызываемые из меню или из строки состояния. Такая форма организации диалога человека и машины наиболее удобна, и многие программы используют ее. Программные средства АРМ – часть инструментального программного обеспечения.
Пример. АРМ секретаря-референта должен включать редактор текстов, электронную таблицу, переводчики, органайзер и др. АРМ студента-экономиста должен включать электронные учебники по изучаемым дисциплинам, обучающие программы и среды, электронные справочники и энциклопедии, переводчики, органайзер и др. АРМ администратора базы данных должен включатьСУБД, электронный журнал администратора и др. АРМ управляющего должен включать средства описания управленческой деятельности в виде сетевого графика, систему контроля исполнения, систему согласования документов, систему электронной подписи, систему ведения совещания и др. АРМ банковского служащего и банковские системы – наиболее развиваемые системы. Они включают программное и техническое обеспечение как специального назначения (например, для банковских расчетов и операции с банкоматами), так и для обеспечения безопасности таких систем.
Технологии компьютерного (компьютеризированного) офиса коллективной работы в офисе. Компьютерный офис – это офис, в котором имеется высокий уровень компьютеризации, внедрения АРМ, систем делопроизводства – так, что вся профессиональная деятельность офиса может быть успешно автоматизирована.
Пример. Компьютерный офис – это, например, офис, в котором работа осуществляется с использованием локальных сетей связи и интегрированной программной среды Microsoft Office, которая включает в себя все, в частности ведение делопроизводства, контроль исполнения и др. Стандартное ядро Microsoft Office включает: редактор текстов Microsoft Word (функции редактора – набор, именование и сохранение текста, модификацию, переименование и перемещение текста или его отдельных фрагментов, вставку различных формул, графиков, таблиц, диаграмм и др.); электронную таблицу Excel (функции – обработка, хранение и модификация в произвольных таблицах чисел, строк, столбцов, формул, по которым динамически модифицируются числа, строки и столбцы); систему для презентаций (презентационный пакет) PowerPoint (функции – создание и проецирование на большом экране электронных презентаций, слайд-шоу, ярких пленок для проектора, раздаточных печатных материалов); систему управления базами данных Access ( СУБД, доступная любому пользователю и позволяющая быстро и эффективно организовывать, анализировать, перемещать, вести поиск и т.д. для больших массивов информации, без дублирования информации в них), например, по шаблонам создания базы данных: Адресная книга – создает базу данных типа адресной книги,Библиотека – создает базу данных типа библиотеки, Контакты – создает базу данных типа контактных связей и др.
В состав Microsoft Office-2000 входят и будут входить в ее дальнейших модификациях возможности одновременного показа презентаций по локальной сети, использование возможностей системы распознавания речи, визуальные среды разработки различных офисных приложений (например, заполнения платежных поручений), сайты рабочих групп, системы визуализации данных, система сканирования и ввода данных и др.
Технология "Рабочая группа" – технология совместной работы нескольких связанных между собой общими информационными ресурсами компьютеров ( "рабочей группы" ), объединенных для решения какой-либо общей задачи.
Пример. Примеры рабочих групп: "Дирекция", "Бухгалтерия", "Канцелярия". Компьютерная сеть организации может объединять несколько рабочих групп. У каждого компьютера рабочей группы имеется идентификатор, имя в группе, например, по ФИО человека, на нем работающего. В рабочей группе "Бухгалтерия" может существовать компьютер (рабочее место) "Главбух" или "Иванов Сергей Николаевич".
Рабочая группа может быть и временной – для работы над конкретным проектом в пределах определенного промежутка времени.
Пример. Можно организовать рабочую группу "Презентация фирмы", состоящую из компьютеров сотрудников фирмы, которые подготавливают презентацию своей фирмы, или "Годовой отчет" – для создания годового финансового отчета фирмы. Все эти люди могут работать в разных отделах, но они составляют временную рабочую группу, чтобы было легко обмениваться информацией общего доступа при работе.
Обмен информацией может происходить и между рабочими группами. Для этого не нужно физически перемещать компьютеры: чтобы сформировать рабочую группу, достаточно присвоить всем компьютерам, входящим в состав группы, ее имя.
Пример. Операционная система Windows for Workgroups позволяет выделение компьютеров в рабочие группы при ее инсталляции. Изменять состав и структуру рабочей группы затем можно из "Панели управления", запустив прикладную программу Network (сеть). При этом все компьютеры одной сети, независимо от их объединения в рабочие группы, имеют доступ к общим принтерам и общим файлам, а такие приложения, как Mail ( Электронная почта Schedule (Ежедневник), работают только в пределах одной рабочей группы. Передача почты через Mail возможна только в пределах одной рабочей группы. Как правило, в небольших фирмах имеется одна рабочая группа.
Технология "Клиент-сервер" – это технология взаимодействия компьютеров в сети, в которой каждый из компьютеров имеет свое рабочее назначение. Один, более мощный, компьютер (сервер) в сети владеет и распоряжается информационными и аппаратными ресурсами (процессор, файловая система, почтовая служба, база данных и др.), другой, менее мощный ("клиент"), имеет доступ к этим ресурсам лишь через сервер.
Пример. Сейчас говорят уже о принципиально иной концепции взаимодействия между элементами сети peer–to–peer (P2P), позволяющей отдельным компьютерам работать друг с другом напрямую.
Технологии использования интегрированных пакетов прикладных программ (ППП) – технологии на базе ППП для решения различных классов однотипных и часто встречающихся задач из различного типа предметных областей. Современные ПППимеют диалоговую, интерактивную обратную связь с пользователем в процессе постановки задачи, решения и анализа результатов. Используют при решении задач обычно используемый в предметной области интерфейс.
Пример. В качестве примера интегрированного ППП приведем пакет MathCAD, предназначенный как для сложных математических вычислений, так и для несложных (в режиме инженерного калькулятора).
Технологии машинной графики и визуализации – технологии, базирующиеся на системах рисования и черчения различных графических объектов и образов с помощью ЭВМ и устройств рисования (например, плоттеров), а также их визуального, наглядного представления. Особо следует отметить средства анимации – "оживления" изображений на экране, компьютерных мультфильмов.
Пример. Примером средств машинной графики может служить программный комплекс изображения пространственных объектов и их динамической актуализации – пакет 3D-Studio. Пакет 3D-Studio позволяет не только создавать трехмерные сцены, но и использовать эти сцены при реализации компьютерных анимационных ситуаций (мультипликаций) с использованием различных графических файлов разных форматов, что дает возможность применять при разработке мультфильмов известные графические пакеты: С orelDraw, PhotoPaint и др. 3D-Studio имеет модульную структуру, состоящую из пяти модулей, за каждым из которых закреплены конкретного типа задачи, решаемые в строгой последовательности. Первый модуль ( 2D-Shaper ) является основным инструментом создания и редактирования плоских фигур, а также снабжения других модулей особыми геометрическими структурами, формами и траекториями. Для преобразования плоских фигур в трехмерные каркасные объекты имеется модуль3D-Lofter, в который включены мощные средства генерации сложных пространственных форм и структур. Подготовленные двумерные планы моделей отображаются ("выдавливаются") в третье измерение по специально заданным траекториям. Модуль3D-Lofter снабжен средствами деформации, например, по осям, что позволяет создавать трехмерные объекты более сложных форм. Можно построить 3D-фигуру по трем проекциям на координатные плоскости.
Гипертекстовые технологии. Гипертекст, hypertext – сверхтекстовая, надтекстовая. Эта технология на базе средств обработки больших, глубоко вложенных, структурированных, связанных семантически и понятийно текстов, информации, которые организованы в виде фрагментов (текста), относящихся к одной и той же системе объектов, что расположены в вершинах некоторой сети и обычно выделяются цветом; они позволяют при машинной реализации быстро, нажатием нескольких клавиш, вызывать и помещать в нужное место просматриваемого или организуемого нового текста нужные фрагменты гипертекста, "привязанные" к выделенным по цвету ключевым словам или словосочетаниям. Гипертекстовая технология позволяет определять, выбирать вариант актуализации информации гипертекста в зависимости от информационных потребностей пользователя и его возможностей, уровня подготовки. При работе с гипертекстовой системой пользователь имеет возможность просматривать документы (страницы текста) в том порядке, в котором ему это больше нравится, а не последовательно, как принято при чтении книг. Достигается это путем создания специального механизма связи различных страниц текста при помощи гипертекстовых ссылок.
Пример. Примерами гипертекстов могут быть электронные журналы.
Средства и системы мультимедиа (multimedia) и гипермедиа (hypermedia). Медиа – "среда или носитель информации". Мультимедийность, многосредность – актуализация различных сред и чувств восприятия информации: средства озвучивания, оживления – мультипликации, графического и наглядного представления входных и выходных данных задачи и сценариев решения или даже самого решения.
Пример. Примерами средств мультимедиа могут служить звуковые карты ( Sound Blaster ) для генерирования на ЭВМ широкого диапазона звуков, активные звуковые колонки для их передачи и устройства считывания информации с компакт-дисков – CD-ROM, позволяющие считывать большие объемы информации – например некоторую сложную и длительную музыкальную композицию, – а затем воспроизводить их с использованием предыдущих двух средств мультимедиа.
Средства гипермедиа – средства на основе синтеза концепции гипертекста и мультимедиа, то есть в гипертекстовые фрагменты могут быть "встроены" мультимедийное сопровождение, мультимедийные приложения.
Пример. Глобальной гипермедийной системой является WWW ( Word Wide Web – Всемирная Паутина) – система навигации, поиска и доступа к гипертекстовым и мультимедийным ресурсам Интернета в реальном масштабе времени. Глобальной ее можно считать потому, что в отличие от обычного (локального) гипертекста, ссылка на документ в ней (осуществляемая одним или несколькими щелчками мыши) может привести не только к другому документу (как в локальном гипертексте ), но и к другому компьютеру ( WWW -серверу), возможно, в другом полушарии. Работа ведется с помощью универсальной программы-клиента, которая позволяет объединить в единое целое клиента и сервер. Для доступа к WWW -серверу (информации на нем) необходимо знать адрес сервера, например, адрес [ Cкачайте файл, чтобы посмотреть ссылку ] – сервер со списком российских WWW -серверов, http (HyperText Transfer Protocol – протокол работы с гипертекстом ). Имеется система автоматического поиска по определенным ключам (запросам, разделам). Информация в WWW представлена в виде гипертекстового документа, включающего в себя различные типы данных (текст, графика, видео, аудио, ссылки на другие гипертекстовые документы и т.д.). Такие документы называют WWW -страницами ( WWW-pages ). Эти страницы просматриваются с помощью браузеров – специальных программ для навигации по сети. Страницы хранятся на компьютерах-узлах сети, которые называют сайтами (site). Каждый компьютер имеет свой уникальный IP-адрес URL ( Uniform Resource Locator – универсальный локатор ресурсов), с помощью которого браузер знает, где находится информация и что надо с ней делать. Cтраница – основной элемент WWW. На них находится та информация, которую мы ищем в сети, или ссылки на нужную информацию. Страницы, гипертекст – это легкая и быстрая в использовании, чрезвычайно мощная система связанных ключевых слов и фраз (ссылок), позволяющая ссылаться на другие ключевые слова и фразы других страниц. Эти ссылки обычно выделены другим цветом, и достаточно просто щелкнуть мышкой по выделенной ссылке, чтобы перейти к информации, на которую ссылается эта ссылка. Для создания гипертекстовых приложений (например, личной WWW-страницы) используется специальный язык HTML (HyperText Markup Language), позволяющий создавать гипертекстовый документ в любом текстовом редакторе формата ASCII, с подключением графических файлов двух основных форматов – GIF и JPEG.
Технология виртуальной реальности, виртуальная реальность – технологии актуализации различных гипотетических сред и ситуаций, не существующих реально и возможных как варианты развития реальных аналогов, систем реального мира; эти технологии и системы позволяют управлять виртуальным объектом, системой, путем моделирования законов пространства, времени, взаимодействия, инерции и др.
Высшая форма развития компьютерного офиса – виртуальный офис и виртуальная корпорация – это офисы и корпорации, не существующие в обычном, классическом виде ("имеющих вывеску, штат, здание"), а существующие воображаемо, распределенно – как в пространстве, так и во времени (отделы и сотрудники могут находиться даже на различных континентах, общаясь по работе с помощью ЭВМ и сетей связи). Они являются высшей ступенью организации делового сотрудничества и в корне меняют организацию работ и систему информационного обеспечения сотрудников.
Пример. Виртуальная маркетинговая корпорация "Да Винчи" объединяет ряд горнорудных месторождений, производственные (машиностроительные и строительные), транспортные, инвестиционные, экологические системы. Все подсистемы "Да Винчи" поставляются без доработок под конкретный объект (как детские конструкторы сборно-разборного типа). Один из сценариев, предлагаемых в проекте ( Venture Management Model ), моделирует нижеследующую ситуацию. Горнодобывающая компания ведет разработки в Новой Гвинее. Построенный в этой местности отель может быть расширен для обслуживания растущего потока деловых клиентов этой компании, а также туристов. Консорциуму, имеющему бизнес в сфере коммуникаций и гостиничных услуг, предлагается долевое участие в развитии этой местности и эксплуатации отеля. Для снижения накладных расходов на расширение отеля и инфраструктуры туризма привлекаются крупные строительные компании (на условиях долевого участия в прибылях). Отметим при этом, что критерии эффективности бизнеса в таком составе – различны, а процесс принятия стратегических решений сопряжен с конфликтными интересами партнеров, динамически изменяющейся их картиной. Для реализации этой корпорации имеются электронная (мультимедийная) почта для поддержки процессов принятия решений первыми лицами, средства телеконференций для функциональных подразделений и аналитиков, геоинформационная система, САПР, взаимодействующая с СУБД через структуру данных с пространственной привязкой, система компьютерного делопроизводства на всех этапах. Используются современные технологии типа "клиент-сервер" и объектно-ориентированные под Windows NT, Windows 95 (рабочие места), Unix (сервер), полные версии MS Office и компьютерный документооборот. В системе электронного документооборота используются: полнотекстовый поиск, доступ к проектной документации на всех этапах жизненного цикла проекта, подготовка интерактивной технической документации. Документ может содержать текст, например, HTML -документ, иллюстрации в одном или нескольких слоях, редакторские правки и комментарии участников различных рабочих групп, участвующих в проекте, трехмерных объекты из программ САПР, подключаемые к документу видео- и аудиофайлы.
Есть еще много других видов (классов) технологий: компьютерной алгебры, средо-ориентированные, объектно-ориентированные, CASE-технологии, нечеткие и др.
Лекция 15
Информатизация общества. Информационное общество. Интернет.
Аннотация: Рассматриваются основные понятия, относящиеся к информатизации и информационному обществу, информатизации экономики.
Ключевые слова: [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ], [ Cкачайте файл, чтобы посмотреть ссылку ],[ Cкачайте файл, чтобы посмотреть ссылку ]
Информатизация – это системный процесс внедрения достижений методов информатики и новых информационных технологий в общественную жизнь, в научно-технические, социально-экономические, технологические, социокультурные и другие институты государства, страны, с целью повышения их эффективности, демократизации, а также гуманитаризации, гармонизации и гуманизации общества.
Информационное общество, развивающееся на основе информационных потоков – это общество на той стадии его развития, когда основные материальные, энергетические, организационные ресурсы могут актуализироваться с помощью информационных ресурсов, то есть они носят материо-энерго-информационный характер и саморазвиваются, самоорганизуются, поддерживаются государственной политикой.
Информационное общество – это общество, в котором ценность всех ресурсов (материальных, энергетических, организационных) определяется ценностью получения, хранения, использования информационного ресурса.
Информация в информационном обществе стала стратегическим ресурсом, ибо она определяет ключевые системы общества, системы, обеспечивающие жизнедеятельность, жизнеспособность общества.
Пример. В 1989 г. в СССР была разработана Концепция информатизации общества, которая должна быть реализована ориентировочно к 2050 году. Аналогичная программа США ориентирована на завершение к 2020 году, Японии и развитых стран Западной Европы – к 2040 году. Все такие программы строятся с учетом национальных, исторических, культурных и других традиций и особенностей страны. Например, японская программа построения информационного общества основана на использовании всех возможностей традиционной индустрии и японского трудолюбия, благополучного окружения, стабильных и хороших условий жизни. Программы многих стран предусматривают привлечение большого количества молодых специалистов в области информационных технологий, создание им льготных эмиграционных условий. Например, немецкая программа рассчитана на привлечение более ста тысяч таких специалистов.
Информатизация страны состоит в информатизации в частности следующих основных систем общества (перечень неполный, хотя и охватывает все основные системы).
Банковских систем.
Пример. Виртуальные, компьютерные расчеты и платежи, прогноз банковского кредитного риска и надежности банков, разработка и использование АРМ банковского работника и др.
Систем рыночной экономики.
Пример. Прогноз и анализ спроса и предложения на рынке, моделирование поведения сегментов рынка и прибыли от продаж, разработка и использование АРМ работника рыночной экономики и др.
Систем социального обеспечения.
Пример. Прогноз и анализ инфляции в страховании, моделирование принятия решений в различных социо-экономических и социо-культурных ситуациях, в частности катастрофических; разработка и использование АРМ социального работника и др.
Систем налоговой службы.
Пример. Прогноз и анализ собираемости налогов, моделирование и прогнозирование тяжести налогового бремени, расчет оптимальных ставок налогообложения, разработка и использование АРМ работника налоговой службы и др.
Систем биржи и биржевой деятельности.
Пример. Прогноз и анализ динамики курса ценных бумаг, валют, моделирование потоков (товаров, ценных бумаг, платежей, услуг и др. ресурсов) на бирже, моделирование и прогнозирование аномалий, катастроф на бирже; разработка и использование АРМ работника биржи (брокера) и др.
Систем промышленности.
Пример. Прогноз и анализ производительности труда, рентабельности и прибыльности, финансовой устойчивости и платежеспособности предприятий, состава и структуры производства, поставок, сбыта, разработка и использование САПР и АРМ и др.
Систем транспорта и связи.
Пример. Прогноз и анализ, выбор оптимального маршрута движения транспорта, трафика сетей связи, управление транспортными потоками и средствами, навигация транспортных средств, разработка и использование АРМ работника транспорта, связи и др.
Систем топливно-энергетического комплекса.
Пример. Прогноз и анализ (распознавание) мощности нефтеносного пласта, его профиля, автоматизация систем распределения и учета расхода энергии, разработка, использование АРМ работника комплекса и др.
Систем строительного комплекса.
Пример. Прогноз, анализ (оптимизация) парка строительных машин, механизмов, их простоя, учет стройматериалов, автоматизированная компоновка (например, прокладка с использованием пакета программ AutoCAD водопроводных, тепловых, электрических коммуникаций), расчет надежности и долговечности конструкций и др.
Систем правительственных услуг и права.
Пример. Разработка консультационных правовых компьютерных систем, прогноз и анализ динамики правонарушений в зависимости от различных факторов, разработка и использование различных систем консультирования по вопросам права и государства, разработка и использование АРМ работника правительственной службы, права и др.
Систем здравоохранения и медицины.
Пример. Прогноз и анализ эпидемий и различных медико-социо-экономических ситуаций, разработка и использование автоматизированных систем "Поликлиника", "Скорая помощь", "Реабилитационный центр" и др., АРМ терапевта, хирурга, кардиолога, медсестры и др.
Систем экологии.
Пример. Прогноз и анализ загрязнения водного и воздушного бассейна, моделирование и прогнозирование катастроф, разработка экспертных систем и баз знаний для принятия экологически обоснованных решений, разработка и использование АРМ эколога и др.
Систем сельского хозяйства.
Пример. Прогноз и выбор оптимального режима полива и подкормки растений, автоматизация учета и хранения сельскохозпродукции, моделирование прироста биомассы в динамике, принятие рациональных, экологически обоснованных решений; разработка АРМ работника сельского хозяйства и др.
Систем образования и образовательных услуг.
Пример. Разработка и использование систем дистанционного обучения, различных программных, методических продуктов педагогического характера, актуализация и визуализация междисциплинарных связей, в частности с помощью компьютерных лабораторных работ по физике, химии, разработка АРМ директора, завуча, зав. кабинетом, автоматизация составления расписания занятий и др.
Систем военного дела.
Пример. Прогноз и анализ ситуаций на военном поле, обеспечение автоматизированных систем управления огнем, оптимальный выбор рациона питания армии, моделирование тактики поведения военных и судов, кораблей, самолетов, танков, в частности, уклонения их от нападения, разработка АРМ военного и др.
Систем безопасности.
Пример. Разработка высоконадежных средств шифрования и передачи данных, разработка систем защиты и обеспечения надежности сетей и систем ЭВМ, обеспечение защиты от помех и перехвата информационного характера, разработка АРМ работника системы безопасности и др.
Систем делопроизводства
Пример. Использование систем делопроизводства, контроля, электронных словарей и переводчиков, распознавание текстов и их ввод в компьютер, разработка АРМ секретаря-делопроизводителя и др.
Используют часто и термины "региональная информатизация", "региональные проблемы информатизации", которые объединяют совокупность вышеуказанных проблем, возникающих в регионах (областях и республиках, субъектах государства) и учитывающих национально-региональные предпосылки постановки и соответствующие ресурсы при решении указанных выше проблем информатики, уровень информационно-технологического развития региона, исторические, географические, национальные, демографические, социально-экономические, культурные предпосылки, связи региона.
Проблемы информатизации могут возникать на различных уровнях.
Пример. Проблемы информатизации страны: обеспечение дистанционного обучения в рамках страны; разработка и/или исследование адекватных математических моделей демографической ситуации в стране; разработка математических моделей и компьютерных систем прогноза погоды; разработка внутригосударственной автоматизированной системы управления транспортом и продажи билетов. Проблемы информатизации региона: информатизация образования или решение задач информатизациирегионального компонента образования; компьютеризация налоговых и банковских региональных структур; разработка математических моделей и компьютерных систем планирования целей, исследования, принятия решений и управления различными (например, эколого-медицинскими) системами региона. Задачи информатизации города: информатизация, компьютеризация АТС города, например, на базе цифровых систем связи; информатизация и компьютеризация управления таксопарком города; разработка баз данных по юридическим и физическим лицам города. Примерами информатизации быта и досуга могут быть: разработка автоматизированной системы ведения домашней бухгалтерии; разработка и использование мультимедийных программных обучающих систем для домашней и самостоятельной работы школьников; разработка и использование различных игровых систем.
Основные социально-экономические проявления информатизации:
высокая информационная культура членов общества и его систем, государственное воспитание и поддержание этой культуры на государственном уровне;
индустриализация информационного обслуживания членов и институтов общества;
превращение информации в товар с его классическими атрибутами (цена, стоимость, спрос, предложение, наличие денежного эквивалента, издержки, реклама и т.д.) и развитие рынка этого товара;
потенциально свободный доступ каждого к интеллектуальному богатству общества, всего мирового сообщества;
превращение знаний и профессионализма в непосредственный атрибут товаро-денежных отношений, капитализация информационных ресурсов и отношений, знаний;
превращение труда в преимущественно умственный и интеллектуальный труд, высвобождение большего времени для духовного развития или саморазвития человека, высокий уровень информационного сервиса быта и труда;
обеспечение информационной защиты и информационной безопасности общества, стабильности и устойчивости существования этого общества;
более высокий уровень принятия решений на базе соответствующих систем (баз данных, знаний, экспертных систем и др.).
В процессе информатизации общества необходимо:
создать математическую и элементную (техническую) базу;
создать качественную и гибкую индустрию информационных потоков, технологий;
подготовить системы информатизации и совершенствования управления;
обеспечить информационную безопасность (предупреждение негативного воздействия информации на человека и общество);
воспитать информационно, "компьютерно и сетевым образом" грамотных членов общества, создать все условия для этого.
Важную роль в развитии информационного мирового сообщества играют компьютерные сети, Интернет.
Сеть – система компьютеров, соединяемых между собой в соответствии с одной из стандартных типовых форм соединения (топологией сети) для передачи и приема сообщений (пакетов данных).
Основные функции любой сети:
обеспечение доставки пакетов данных;
обеспечение автоматического конфигурирования и надежной работы, сетевого сервиса;
согласование пакетов для различных базовых протоколов.
Имеется специальное устройство – маршрутизатор. Маршрут – адреса последовательных маршрутизаторов, которые проходит пакет от отправителя до адресата. Маршрутизатор объединяет отдельные сети в сложную (составную) сеть и выбирает из альтернативных маршрутов для передачи пакетов данных между двумя конечными узлами – один, более оптимальный в каком-то смысле (например, по времени передачи пакета).
Маршрутизатор соединяет несколько сетей в так называемую интерсеть. Для этого маршрутизаторы обмениваются маршрутной информацией между собой по специальному протоколу – протоколу маршрутизации.
С помощью специальных протоколов обмена маршрутами (протоколов сетевого уровня) маршрутизаторы составляют маршрутную карту межсетевых связей и принимают решение о том, какому следующему маршрутизатору в маршруте нужно передать пакет для образования рационального (например, по времени) пути.
Используют часто и термины "региональная информатизация", "региональные проблемы информатизации", которые объединяют совокупность вышеуказанных проблем, возникающих в регионах (областях и республиках, субъектах государства) и учитывающих национально-региональные предпосылки постановки и соответствующие ресурсы при решении указанных выше проблем информатики, уровень информационно-технологического развития региона, исторические, географические, национальные, демографические, социально-экономические, культурные предпосылки, связи региона.
Проблемы информатизации могут возникать на различных уровнях.
Пример. Проблемы информатизации страны: обеспечение дистанционного обучения в рамках страны; разработка и/или исследование адекватных математических моделей демографической ситуации в стране; разработка математических моделей и компьютерных систем прогноза погоды; разработка внутригосударственной автоматизированной системы управления транспортом и продажи билетов. Проблемы информатизации региона: информатизация образования или решение задач информатизациирегионального компонента образования; компьютеризация налоговых и банковских региональных структур; разработка математических моделей и компьютерных систем планирования целей, исследования, принятия решений и управления различными (например, эколого-медицинскими) системами региона. Задачи информатизации города: информатизация, компьютеризация АТС города, например, на базе цифровых систем связи; информатизация и компьютеризация управления таксопарком города; разработка баз данных по юридическим и физическим лицам города. Примерами информатизации быта и досуга могут быть: разработка автоматизированной системы ведения домашней бухгалтерии; разработка и использование мультимедийных программных обучающих систем для домашней и самостоятельной работы школьников; разработка и использование различных игровых систем.
Основные социально-экономические проявления информатизации:
высокая информационная культура членов общества и его систем, государственное воспитание и поддержание этой культуры на государственном уровне;
индустриализация информационного обслуживания членов и институтов общества;
превращение информации в товар с его классическими атрибутами (цена, стоимость, спрос, предложение, наличие денежного эквивалента, издержки, реклама и т.д.) и развитие рынка этого товара;
потенциально свободный доступ каждого к интеллектуальному богатству общества, всего мирового сообщества;
превращение знаний и профессионализма в непосредственный атрибут товаро-денежных отношений, капитализация информационных ресурсов и отношений, знаний;
превращение труда в преимущественно умственный и интеллектуальный труд, высвобождение большего времени для духовного развития или саморазвития человека, высокий уровень информационного сервиса быта и труда;
обеспечение информационной защиты и информационной безопасности общества, стабильности и устойчивости существования этого общества;
более высокий уровень принятия решений на базе соответствующих систем (баз данных, знаний, экспертных систем и др.).
В процессе информатизации общества необходимо:
создать математическую и элементную (техническую) базу;
создать качественную и гибкую индустрию информационных потоков, технологий;
подготовить системы информатизации и совершенствования управления;
обеспечить информационную безопасность (предупреждение негативного воздействия информации на человека и общество);
воспитать информационно, "компьютерно и сетевым образом" грамотных членов общества, создать все условия для этого.
Важную роль в развитии информационного мирового сообщества играют компьютерные сети, Интернет.
Сеть – система компьютеров, соединяемых между собой в соответствии с одной из стандартных типовых форм соединения (топологией сети) для передачи и приема сообщений (пакетов данных).
Основные функции любой сети:
обеспечение доставки пакетов данных;
обеспечение автоматического конфигурирования и надежной работы, сетевого сервиса;
согласование пакетов для различных базовых протоколов.
Имеется специальное устройство – маршрутизатор. Маршрут – адреса последовательных маршрутизаторов, которые проходит пакет от отправителя до адресата. Маршрутизатор объединяет отдельные сети в сложную (составную) сеть и выбирает из альтернативных маршрутов для передачи пакетов данных между двумя конечными узлами – один, более оптимальный в каком-то смысле (например, по времени передачи пакета).
Маршрутизатор соединяет несколько сетей в так называемую интерсеть. Для этого маршрутизаторы обмениваются маршрутной информацией между собой по специальному протоколу – протоколу маршрутизации.
С помощью специальных протоколов обмена маршрутами (протоколов сетевого уровня) маршрутизаторы составляют маршрутную карту межсетевых связей и принимают решение о том, какому следующему маршрутизатору в маршруте нужно передать пакет для образования рационального (например, по времени) пути.
Для построения сетей используются специальные устройства – концентраторы (хабы), к которым подсоединяются все устройства сети (как к коммутатору телефонной станции). Подсоединяется либо хаб более высокого уровня, либо хаб более низкого уровня, с защитой данных и двумя режимами работы: конфиденциальным (можно получать лишь те сообщения, которые адресованы непосредственно хабу) и публичным (можно получать все сообщения, например, для маршрутизаторов). Хаб время от времени автоматически опрашивает подключенные узлы, выясняет их состояние ("свободен", "передает", "принимает") и анализирует их запросы: сперва обслуживаются запросы высокого приоритета, например, от приложений, требующих немедленной реакции, а затем – запросы с обычным приоритетом. Приоритет выделяется по времени ответа на запрос: чем меньше время ответа – тем, как правило, выше приоритет.
Интернет – развитие проекта американского оборонного ведомства DARPA (Defence Advanced Research Projects Agency) по созданию сетевой архитектуры, обеспечивающей эффективную связь ряда военных и правительственных сетей.
В процессе реализации проекта Интернет оказалось, что модель взаимодействия между компьютерами может эффективно применяться и для создания образовательных, коммерческих, научных, исследовательских и других сетей, то есть для создания глобальной информационной инфраструктуры, в результате чего Интернет стал международной коммуникационной средой.
Интернет – система объединяемых по мере необходимости сетей со стандартизированными едиными протоколами обмена и доступа к информации в режиме реального времени. Это – "Сеть сетей", с добровольным участием, управляемая ISOC (InternetSOCiety), то есть сообществом, способствующим глобальному обмену информацией, вырабатывающим техническую политику и осуществляющим поддержку и управление Интернет.
Различные рабочие группы ISOC имеют различные функции: выпуск документации, выработка стратегии действий, перспективные исследования, разработка новых и модификация используемых стандартов и протоколов.
Доступ в Интернет получают через поставщиков информационно-коммуникационных услуг ( провайдеров ).
Пример. Каждый компьютер в Интернет имеет уникальный 32-разрядный двоичный адрес (IP-адрес).
Интернет построен по технологии "клиент (компьютер пользователя) – сервер (межсетевой связи)". Клиент и сервервзаимодействуют виртуально – сервер по командам клиента выполняет определенные действия с информацией, например, пересылает клиенту файл.
Хотя компьютеры Интернет имеют физические (числовые) номера, адреса, в работе пользователи обычно используются системные имена – доменные адреса.
Доменная система имен – система имен, переданных сетевым группам или элементами [u2]этих групп. Каждый уровень системы называется доменом. Домены в именах отделяются друг от друга точками. В имени может быть различное количество доменов, но обычно их всего 2-3. При движении по доменам слева направо в имени, количество имен, входящих в соответствующую группу, возрастает. Первым в имени стоит название реального компьютера с IP-адресом. Группа входит в более крупное подразделение, оно – входит в еще более крупное, и так далее – до государственной сети. Для США имеются домены сетей образовательных (edu), коммерческих (com), государственных (gov), военных (mil) учреждений, а также сети других организаций (org) и сетевых ресурсов (net). Каждая страна имеет свой домен: Канада ca, Россия – ru и т.д.
Стандартные возможности Интернета:
удаленный доступ (remote login) с помощью протокола эмуляции удаленного терминала (telnet) – когда ваш компьютер эмулирует (имитирует) терминал удаленного компьютера;
передача файлов (ftp) – передача файлов с компьютера на компьютер в реальном масштабе времени с автоматической перекодировкой данных;
электронная почта (e-mail).
Основные нестандартные возможности Интернета:
виртуальные магазины и торговые площадки (порталы);
виртуальные биржи;
виртуальный маркетинг;
виртуальный банкинг и виртуальные платежные системы;
виртуальное, дистанционное обучение;
виртуальная библиотека (медиатека) и виртуальные журналы, подписки;
виртуальное интерактивное общение на всевозможные темы по интересам (чаты).
Развитие Интернета и ЛВС привело к появлению корпоративных Интранет-сетей. В Интранет-сетях используется то же аппаратное ипрограммное обеспечение, те же протоколы и принципы, что и в Интернете. Интранет – это мини-Интернет. Интранет-сетьспособна значительно повысить эффективность и прибыльность корпоративной деятельности за счет того, что имеет такие возможности (приложения), как сетевые электронные доски, различное групповое программное обеспечение, потоковые общие ресурсы и др.
in XРисунок 3x\in Xge log_2 NРисунок 5d \ge log_2 Nsum_{i=1}^n p_{i}log_{2} p_i,Рисунок 4I=-\sum_{i=1}^n p_{i}log_{2} p_i,Рисунок 11Рисунок 31times p^kРисунок 27x=m\times p^ktimes p^lРисунок 26y=n\times p^ltimes p^{k–l}Рисунок 24x + y = (m + n \times p^{l–k}) \times p^k,\\X x y = (m – n \times p^{l–k})\times p^k,\\x \times y=(m \times n) \times p^{k+l},\\x/y = (m/n) \times p^{k–l}.sum_{i=0}^{n-1}p^i = p^n - 1Рисунок 22x_p^{\max}=\sum_{i=0}^{n-1} (p-1)p^i = \sum_{i=0}^{n-1}p^{i+1}-\sum_{i=0}^{n-1}p^i = p^n - 1ldots1}_{n}=2^{n}-1, b=1-2^nРисунок 19a=\underbrace{111\ldots1}_{n}=2^{n}-1, b=1-2^nldots7}_{n}=8^{n}-1, b=1-8^nРисунок 18a=\underbrace{777\ldots7}_{n}=8^{n}-1, b=1-8^n.times n)Рисунок 172457 = 2 \times 3! + 4 \times 2! + 5 \times 1! + 7 \times 0! (0! = 1, n! = 1 \times 2 \times 3 \times \ldots \times n)ldots x_{2}x_{1} (n > 1)Рисунок 16x = x_{n}x_{n1}\ldots x_{2}x_{1} (n > 1)times 0!Рисунок 13x = x_{n}x_{n-1}\ldots x_1 = x_n \times (n – 1)! + x_{n–1} \times (n – 2)! + ... + x_1 \times 0!D(р)={6, 24}Рисунок 48D(р)={6, 24}D(q) = {вторник, среда, воскресенье}Рисунок 47D(q) = {вторник, среда, воскресенье}lor xРисунок 41x \land y = y\land x, x \lor y = y \lor xland x = 0Рисунок 34\overline{0}=1, \overline{1}=0, \overline{x}\lor x=1, \overline{x}\land x = 0land x=0Рисунок 33x\land1=x,\\x\lor0=x,\\x\lor1=1,\\x\land0=0,\\ \overline{x}\lor x=1,\\ \overline{x}\land x=0land zРисунок 52w = x\land y\land zin [0;1]Рисунок 61х,у \in [0;1]cup E(p2)Рисунок 60y)\}=\\=\{(x,y ):x=y\}\cup\{(x,y) : x = –y\} = E(p1)\cup E(p2).lor y)Рисунок 58(x\to y)\equiv(\overline{x}\lor y)Рисунок 54\overline{x\lor y}\lor\overline{x}\land y\land\overline{x}=\overline{x}\land\overline{y}\lor\overline{x}\land y\land\overline{x}=\overline{x}\land\overline{y}\lor\overline{x}=\overline{x}land yРисунок 70x\land yland uРисунок 69z\land uland vРисунок 68\overline{x}\land v.lor v=1Рисунок 67x\lor y=1, z\lor u=1, \overline{x}\lor v=1Longrightarrow yРисунок 62x\Longrightarrow yЭлектрический аналог схемы инвертораРисунок 80Электрический аналог схемы инвертораРисунок 78land yРисунок 74х\land yРисунок 73Рисунок 72Принцип работы конъюнктораРисунок 71Принцип работы конъюнктораРисунок 99Рисунок 98Рисунок 93Рисунок 89z=(x\lor y)\land\overline{x}land 11100010 = 11100000Рисунок 88x\lor y = 00011101 \lor 11100001 = 11111101,\\z=(x\lor y)\land\overline{x}=11111101 \land 11100010 = 11100000.lor t}Рисунок 86u=\overline{x\land y\land z\lor t}Схема для функции 1Рисунок 85Схема для функции 1u = f(х,у,z,t)Рисунок 84u = f(х,у,z,t)Схема для функции 2Рисунок 83Схема для функции 2Рисунок 107Рисунок 106Рисунок 105Рисунок 123X = {1, 3, Г, \oslash}Рисунок 122Граф автомата для продажи газированной водыРисунок 121Граф автомата для продажи газированной водыРисунок 120s_t\in S = \{s_0, s_1, ..., s_n\}Рисунок 119y_{t+1} = f(s_t, x_{t+1})Рисунок 116s_{t+1} = \varphi(s_t, x_{t+1}),\\y_{t+1} = f(s_t, x_{t+1}).Структура ЭВМ фон Неймановской архитектурыРисунок 125Структура ЭВМ фон Неймановской архитектурыСтруктура процессораРисунок 124Структура процессораРисунок 128
Интерфейс FAR-менеджераРисунок 126Интерфейс FAR-менеджераРисунок 170Рисунок 169Рисунок 168subset S(X)Рисунок 167s_{1}(x)\subset S(X)cup TРисунок 164W = N\cup Tto gРисунок 163f\to gin WРисунок 160w_1\in Win WРисунок 159w_2\in WРисунок 157Рисунок 153Рисунок 151Рисунок 149Рисунок 147Рисунок 145Рисунок 143Рисунок 141Рисунок 139to gРисунок 137f\to gto bРисунок 132n\to bin TРисунок 131n, с\in N; a, b\in TРисунок 172Рисунок 171le nРисунок 175i,j \le nзђ Заголовок 115