21341

Структура базовой информационной технологии и алгоритм решения

Реферат

Информатика, кибернетика и программирование

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

Русский

2013-08-02

513.5 KB

35 чел.

. Структура базовой информационной технологии и

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

Концептуальный уровень описания (содержательный аспект)

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

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

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

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

Специальные (конкретные) ИТ задают обработку данных в определенных типах задач пользователей.

Концептуальная модель базовой информационной технологии содержит информационное описание предметной области (рис. 2.10).

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

Если построить цепочку, состоящую из процессов и процедур, перечисленных на рис. 2.10 последовательно слева на право, получится описание во времени процессов преобразования информационного ресурса в информационный продукт (рис. 2.11). Формирование информационного ресурса осуществляется в процессе «Получение» и начинается с процедуры  «Сбор», отображающей предметную область (параметры, характеристики, состояние объекта управления). Собранная информация должна быть соответствующим образом подготовлена (осмыслена, структурирована, проверена на полноту, достоверность, непротиворечивость и т.д.). После подготовки и проверки информация может быть передана для преобра-зования традиционными способами (телефон, курьер, почта, телеграф), и может быть подвергнута алгоритму преобразования в данные, т.е. процессу ввода.

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

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

I [роцесс «Отображение» содержит процедуры преобразования данных в форму, удобную для восприятия: звук, изображение — текстовое, цифровое, графическое, видео, твердая копия на бумаге.

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

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

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

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

В информатике часто используют слова «информация» и «данные», причем часто как взаимозаменяемые. Хотя в необходимых случаях специалисты отмечают и их смысловое различие. Например, «информация кодируется с помощью данных и извлекается путем их декодирования и интерпретации»1. Кодирование информации происходит в процессе ввода ее в память ЭВМ, и можно считать, что данные — это информация, представленная в специальной фиксированной форме, пригодной для последующей компьютерной обработки, хранения и передачи.

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

2.3.2. Логический уровень (формализованное/модельное описание)

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

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

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

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

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

Модель накопления данных описывает как систему управления базой данных (СУБД), так и саму информационную базу, которая может быть определена как база данных и база знаний. Процесс перехода от смыслового (информационного) представления к физическому осуществляется трехуровневой системой моделей информационной базы: концептуальной (какая и в каком объеме информация должна накапливаться при реализации информационной технологии), логической (структура и взаимосвязь элементов информации) и физической (методы размещения данных и доступа к ним на машинных носителях). Функции управления базами данных регламентируют: язык баз данных SQL (Structured Query Language); информационно-справочную систему IRD (Information Resource Dictionary System); протокол удаленного доступа операций RDA (Remote Data Access), PAS (Publicly Available Specifications) Microsoft на открытый прикладной интерфейс доступа к базам данных ODBC (Open Data Base Connectivity) API (Application Program Interface).

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

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

средств языка ASN1 (Abstract Syntax Notation One), предназначенного для спецификации прикладных структур данных — абстрактного синтаксиса прикладных объектов;

форматов метафайла для представления и передачи графической информации CGM (Computer Graphics Metafile);

спецификации сообщений и электронных данных для электронного Обмена в управлении, коммерции и транспорте EDIFACT (Electronic Data Interchange for Administration, Commence and Trade);

спецификации документов и их структур ODA (Open Document rchitecture);

спецификации структур документов для производства, например   SGML (Standard Generalized Markup Language);

языков описания документов гипермедиа и мультимедиа, например: HyTime, SMDL (Standard Music Description Language), SMSL (Standard Multimedia/Hypermedia Scripting Language), SPDS (Standard Page )Description Language), DSSSL (Document Style Semantics and Specification Language), HTML (HyperText Markup Language);

спецификации форматов графических данных, например форматов JPEG, JBIG и MPEG.

Модель отображения информации строится с учетом стандартов X Windows, MOTIF, OPEN LOOK, VT, CGI, PHIGS, машинной графики (GKS, графического пользовательского интерфейса GUI.

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

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

2.3.3. Физический уровень (программно-аппаратная реализация)

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

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

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

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

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

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

5. ОСНОВНЫЕ ЭТАПЫ  РЕШЕНИЯ ЗАДАЧ НА ЭВМ

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

 Математическая постановка задачи. 

При разработке решения деятельность постановщика и разработчика решения задачи условно можно разделить на несколько этапов:

  1.  Технические требования для решения задачи или постановка задачи.
  2.  Построение модели.
  3.  Разработка метода решения или алгоритма решения.
  4.  Реализация алгоритма, программирование алгоритма
  5.  Отладка и проверка программы.
  6.  Составление документации.

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

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

 Построение модели

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

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

Наиболее общие правила построения моделей можно сформулировать так:

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

Отметим еще одну особенность составления математической модели – приступая к разработке модели, следует задать, по крайней мере, два основных вопроса:

  1.  Какие математические структуры больше всего подходят для задачи?
  2.  Существуют ли решенные аналогичные задачи?

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

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

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

  •  Вся ли информация хорошо описана математическими объектами?
  •  Существует ли математическая величина, ассоциируемая с искомым результатом?
  •  Выявлены ли  какие-нибудь полезные отношения между объектами модели?
  •  Можно работать с моделью? Удобно ли с ней работать?

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

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

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

Первая крупная модель в физике - механика НЬЮТОНА.

В начале ХХ в. появилась специальная теория относительности, объясняющая целый класс новых физических явлений, для которых модель Ньютона уже не годилась. При этом между моделью Ньютона и моделью Эйнштейна устанавливалась вполне определенная связь - при малых значениях =v2/c2, где v - собственная скорость движения, а с - скорость света, результаты полученные в рамках обоих моделей практически совпадали. Все эти модели прекрасно выдержали испытание практикой, а их роль в формировании мировоззрения и практической деятельности людей трудно переоценить.

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

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

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

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

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

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

В качестве еще одного примера , поясняющего один из возможных подходов к формализации задачи, рассмотрим составление расписание занятий в вузе. При этом используется геометрическая интерпретация  задачи, когда ее решение сводится к отысканию покрытия заданного прямоугольника, набором меньших прямоугольников, суммарная площадь которых равна площади исходного. Возможные варианты расписания учебных занятий определяются существующими вариантами покрытия прямоугольника АВСD «прямоугольниками учебных занятий», удовлетворяющих обязательными требованиям, предъявляемым к расписанию. На этапе  формализации тщательно составляется перечень этих требований, например:

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

 

для всех i, j и l, где n- общее число учебных занятий, i = 1 - 6 - дни учебной недели, j = 1, 8 - номера пар часов учебных занятий в течение дня. l – соответствующее учебное помещение.

              

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

 

Выбор и разработка метода решения.

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

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

Рассмотрим методику формирования решения на примере следующей задачи.

Пример. 

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

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

SABC = SABD + SBDC + SACD

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

Алгоритм и некоторые его свойства. 

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

Для пояснения понятия "алгоритм" важное значение имеет определение понятия "исполнитель алгоритма". Алгоритм формируется в расчете на конкретного исполнителя: - человека, дрессированное животное, специализированную машину, ЭВМ. Алгоритм является руководством к действию для исполнителя, поэтому слово “АЛГОРИТМ” близко к значению слов "указание" или "предписание". То есть, можно сказать, что

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

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

Два наиболее популярных инструмента разработки алгоритма в планировании – это блок – схема   и псевдокод.

Блок – схема  алгоритма 

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

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

 Ввод и вывод данных. Фрагмент программы, в котором пользователь вводит данные и программа выводит результат на экран.

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

Структура принятия решения. Фрагмент программы, в котором принимается решение о направлении вычислительного процесса. В ромб всегда входит одна линия, а выходит две. Одна из выходящих линий отмечается словом «Да», а другая – «Нет».

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

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

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

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

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

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

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

Псевдокоды

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

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

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

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

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

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

Идея алгоритма заключается в просмотре всего текста и когда встречается гласная буква счетчик букв увеличивается на 1, затем просмотр продолжается до встречи в тексте со знаком $.

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

1. Объектом алгоритма являются символы текста и числа (над символами проводятся операции сравнения, числами – счета ).

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

3.  Начальное значение счетчика гласных должно быть равно нулю.

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

  1.  Инициализировать счетчик (записать в счетчик 0).
  2.  Установить указатель на первый символ текста.
  3.   Если символ не $, перейти к п. 4, иначе - п. 7.
  4.   Если символ - гласная, увеличить счетчик на 1.
  5.   Перевести указатель на следующий символ.
  6.   Идти на п. 3.
  7.   Распечатать все найденные гласные и их число.
  8.   Остановить поиск.

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

Особенности алгоритма

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

  •  массовость;
  •  понятность;
  •  дискретность;
  •  определенность;
  •  выполнимость;
  •  конечность;
  •  эффективность.

  1.  Алгоритм имеет некоторое число входных данных. Он указывает последовательность их обработки и возможные результаты. В приведенном примере  результат - число букв. Для подобного алгоритма можно брать различные наборы входных данных, то есть, применимость подобного алгоритма определяется типом (классом используемых данных). Это свойство алгоритма называется массовостью. Другие примеры : турникет в метро, вычисление среднего и т.п.
    1.  Алгоритм должен быть понятен исполнителю, чтобы он мог быть выполнен, то есть, исполнитель должен знать, что делать для исполнения алгоритма (необходимо учитывать особенности исполнителя алгоритма) - {понятность алгоритма}.
    2.  Алгоритм представляется конечной последовательностью шагов. Говорят. что алгоритм имеет дискретную структуру. Его выполнение расчленяется на выполнение отдельных шагов - дискретность алгоритма.
    3.  Алгоритм завершается после конечного числа шагов, отдельные из этих шагов могут повторяться многократно – Конечность алгоритма.
    4.  Каждый шаг алгоритма должен быть четко и недвусмысленно определен и не должен произвольно трактоваться исполнителем. Алгоритм рассчитан на чисто формальное (механическое) исполнение. Это очень важно и означает, что если один и тот же алгоритм поручить разным исполнителям, то они должны прийти к одним и тем же результатам, то есть, должна иметь место  определенность алгоритма. Исполнение алгоритма можно поручить автомату, не обладающего "здравым смыслом". (Пример. Подсчета гласных с учетом дополнительных условий по тексту).
    5.  Каждый шаг алгоритма должен быть выполнен за строго определенное время. То есть, алгоритм должен быть эффективным. Алгоритм должен быть выполнен  не просто за конечное, а за разумно конечное время. Вот почему при разработке алгоритма необходимо учитывать и возможности конкретных физических исполнителей алгоритма.

 Разработка алгоритма 

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

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

Алгоритм. Определить принадлежность точки  D(xd, yd}) треугольнику АВС, заданного  точками (xa, ya ;xb, yb ;xc, yc).

Аргументы:  xa, ya ;xb, yb ;xc, yc xd, yd.

Результат: Z,

Действия:

Вычислить S1: равное значению площади треугольника ABC;

Вычислить S2: равное значению площади треугольника ABD;

Вычислить S3: равное значение площади треугольника ACD ;

Вычислить S4: равное значению площади треугольника CBD

Если 

То     Z=1 и точка d внутри треугольника ABC;

Иначе  Z=0 и точка d - вне треугольника ABC.

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

Если         S <  S2 + S3 + S4

То        z = 0

           И « точка d  вне треугольника»

Иначе  z=1,

     И «точка d внутри треугольника»

конец

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

S1 = S2 + S3 + S4

и

S1 < S2 + S3 + S4

Значения переменных S1 ,S2, S3  и S4  приближенно, , то есть, всегда существует некоторая погрешность вычисления площади треугольника . Таким образом, можно записать

S1  max = S1 +

А максимальное значение суммы

S2 + S3 + S4+ 3,

то есть, если не учесть данного обстоятельства, то  для всех случаев, когда точка d находится внутри треугольника, то условие S1 = 4i=2Si,  выполнятся  будет трудно. Поэтому в рассматриваемом алгоритме необходимо использовать условие

S1 < S2 + S3 + S4

но и оно должно быть скорректировано

S1 < S2 + S3 + S4 - ,

где 

0< < (S1 max - S1) 

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

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

,

где p- полупериметр; а a, b, c - длины сторон треугольника. То есть, в данном случае необходимо разработать дополнительный алгоритм вычисления площади треугольника.

АЛГОРИТМ ВЫЧИСЛЕНИЯ ПЛОЩАДИ ТРЕУГОЛЬНИКА.

Аргументы:  xa, ya ;xb, yb ;xc, yc

Результат: S

Вычислить длину отрезка AB

Вычислить длину отрезка AC

Вычислить длину отрезка BC

p=0.5*(AB+AC+BC)

 ,

 Таким образом, задача сводится к включению в главный алгоритм  вспомогательного алгоритма - нахождения площади треугольника. В результаты работы вспомогательного алгоритма вычисляется площадь треугольника с координатами (xa, ya; xb, yb; xc, yc) и полученное значение площади присваивается переменной S 

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

АЛГОРИТМ "ДЛИНА ОТРЕЗКА"

Аргументы: xa, ya; xb, yb

Результат: AB

 

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

  1.   На уровне 1 создается общее описание алгоритма в целом. Определяются основные логические шаги, необходимые для решения задачи, даже, если пока (в общем случае),неизвестно, как их выполнять. Эти логические шаги могут отражать различные физические шаги решения или могут быть удобными групповыми именами для тех действий, выполнение которых представляется достаточно смутно. Последовательность шагов записывается либо на естественном языке, либо на псевдокоде.
  2.   На уровне 2 в общих терминах детализируется описание шагов выделенных на уровне 1. В детализированное описание может входить обозначение циклических структур, в то время, как действия внутри циклов могут по прежнему оказываться неясными, то есть, выполняется эскиз сложных действий.  
  3.   На уровне 3 и последующих уровнях в виде последовательности операций проводятся те же действия, что на этапе 1. При каждой новой итерации уточняются детали, оставшиеся неясными после предыдущей итерации и создаются более определенные описания. Неопределенные детали становятся проще, а на каком то этапе все неясности будут сняты и детали алгоритма будут полностью описаны.
  4.   Разработка алгоритма завершена. Получено его полное описание. Перевод этого описание в программу на языке программирования  должно быть достаточно простой задачей.
  5.   Если в процессе пошаговой детализации возникли детали и переменные, независящие от остальных частей программы или произошло дублирование модулей, то подобные модули являются очень вероятными кандидатами в подпрограммы или функции. В подобной ситуации модуль описания используется для создания тела подпрограммы или функции и при организации головной программы организуется соответствующее обращение к ним.
  6.   Рисуется общая полная блок-схема алгоритма или он пишется на псевдокоде,  из которого и реализуется программа решения задачи.


 

А также другие работы, которые могут Вас заинтересовать

29126. Исковая давность (понятие, сроки, применение) 28.5 KB
  Исковой давностью признается срок для защиты права по иску лица право которого нарушено. Сроки: Общий срок исковой давности 3 года для отдельных видов требований законом могут устанавливаться специальные сроки исковой давности сокращенные или более длительные по сравнению с общим сроком. Сроки исковой давности и порядок их исчисления не могут быть изменены соглашением сторон. Основания приостановления и перерыва течения сроков исковой давности устанавливаются настоящим Кодексом и иными законами.
29127. Перерыв и приостановление исковой давности. Последствия с ними связанные 30 KB
  Перерыв и приостановление исковой давности. Перерыв течения срока исковой давности предъявлением иска в установленном порядке совершением обязанным лицом действий свидетельствующих о признании долга. После перерыва течение срока исковой давности начинается заново; время истекшее до перерыва не засчитывается в новый срок. Приостановление течения срока исковой давности: если предъявлению иска препятствовало чрезвычайная и непреодолимая сила; если истец или ответчик находится в составе Вооруженных Сил переведенных на военное положение;...
29128. Требования, на которые исковая давность не распространяется 27 KB
  Требования на которые исковая давность не распространяется. Исковая давность не распространяется на: требования о защите личных неимущественных прав и других нематериальных благ; требования вкладчиков к банку о выдаче вкладов; требования о возмещении вреда причиненного жизни или здоровью гражданина. требования собственника или иного владельца об устранении всяких нарушений его права хотя бы эти нарушения не были соединены с лишением владения.
29129. Содержание права собственности 25.5 KB
  Собственнику принадлежат права 1 владение т. Собственник вправе по своему усмотрению совершать в отношении принадлежащего ему имущества любые действия не противоречащие закону. Собственник несет бремя содержания принадлежащего ему имущества если иное не предусмотрено законом или договором. Риск случайной гибели или случайного повреждения имущества несет его собственник если иное не предусмотрено законом или договором.
29130. Формы права собственности 49 KB
  В РФ признаются: Негосударственная Государственная: на праве собственности РФ федеральная собственность на праве собственности субъектам РФ собственность субъекта РФ. Земля и другие природные ресурсы не находящиеся в собственности граждан юридических лиц либо муниципальных образований являются государственной собственностью. Имущество находящееся в государственной собственности закрепляется за государственными предприятиями и учреждениями во владение пользование распоряжение.
29131. Основания возникновения права собственности и их классификация 32 KB
  Находка Нашедший потерянную вещь обязан немедленно уведомить об этом лицо потерявшее ее или собственника вещи и возвратить ему найденную вещь. Вещь может быть также сдана транспортной организации в милицию или орган местного самоуправления. В случае неустановления владельца вещи в 6 месяцев нашедший вещь приобретает право собственности на нее. При возврате вещи владельцу нашедший вещь вправе потребовать от него вознаграждение за находку в размере до 20 стоимости вещи а также возмещение необходимых расходов связанных с хранением или...
29132. Приобретательская давность как основание возникновение права собственности 26.5 KB
  Приобретательная давность лицо гражданин юридическое лицо не являющееся собственником имущества но добросовестно открыто и непрерывно владеющее как своим собственным недвижимым имуществом в течение 15 лет либо иным имуществом в течение 5 лет приобретает право собственности на это имущество. Приобретательная давность это новая для отечественного законодательства форма приобретения права собственности. Право собственности на недвижимое и иное имущество подлежащее государственной регистрации возникает у лица приобретшего это...
29133. Прекращение права собственности 39.5 KB
  Прекращение права собственности – право прекращающие юридические факты которые могут быть связаны с действиями по отчуждению имущества с событиями смерть. Классификация прекращения права собственности: Добровольная – собственник передает это право другому лицу на основании различных договоров административных актов а также при отказе его от права собственности гибели или уничтожении имущества и при утрате права собственности на имущество. Принудительная – обращение взыскания на имущество по обязательствам на основании решения суда...
29134. Отступное в гражданском праве 29.5 KB
  По какимлибо причинам вы ничем кроме честного слова должника свой договор не обеспечили. Пришел час расплаты а денег у должника нет. Первый подать в суд потребовать продажи имущества должника и обязать его расплатиться с вами деньгами вырученными от продажи его имущества. Получив имущество вы отступаете от должника со своими требованиями о возврате долга.