Информатика конспект лекций_2012

-синусоидальные, треугольные, прямоугольные, пилообразные

ипроизвольные колебания любой длительности;

-равномерный, гауссовский, периодический случайный шумы

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

-гамма-шум, пуассоновский, биноминальный шумы, шум Бернулли и т.п.

При моделировании отклика различных систем на разнообразные внешние воздействия может быть использован «Генератор сигналов с заданной длительностью» (рис. 58).

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

ВП генерирует сигнал (signal), имеющий форму, задаваемую на входе тип сигнала (signal type). Вход сбросить фазу (reset phase)

определяет начальную фазу выходного сигнала. По умолчанию на входе установлено состояние ИСТИНА. При этом начальная фаза сигнала устанавливается в соответствии со значением на входе вход фазы (phase in). Если на входе сбросить фазу установлено состояние ЛОЖЬ, то начальная фаза устанавливается равной значению фазы на выходе фазы (phase out) при последнем выполнении этого ВП.

Рис. 58. Генератор сигналов с заданной длительностью

Вход длительность (duration) задает время в секундах, равное длительности генерируемого выходного сигнала. По умолчанию значение длительности равно 1,0.

Вход тип сигнала задает следующие типы генерируемого сигнала: 0-синусоидальный, 1-косинусоидальный, 2-треугольный, 3-прямо-

220

угольный, 4-пилообразный, 5-линейно нарастающий, 6-линейно спадающий.

Вход число выборок (# of samples) задает число выборок выходного сигнала. По умолчанию это значение равно 100.

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

квиста: частота < число выборок/(2·длительность).

Вход амплитуда (amplitude) задает амплитуду выходного сигнала. По умолчанию значение амплитуды равно 1,0.

Вход постоянное смещение (dc offset) задает постоянное смещение или значение постоянной составляющей выходного сигнала. По умолчанию значение постоянной составляющей равно 0.

Рис. 59. Лицевая панель генератора сигналов

221

Рис. 60. Блок-диаграмма программного управления режимом работы генератора

Вход фазы определяет начальную фазу (в градусах) выходного сигнала при установке сбросить фазу в состояние ИСТИНА. По умолчанию значение на входе фазы равно 0.

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

Выход сигнал представляет сгенерированный массив выборок сигнала.

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

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

222

Рис. 61. Палитра функций обработки сигналов в частотной области

Виртуальный прибор (ВП) Передаточная функция (Transfer function) производит расчет односторонней передаточной функции, также известной как частотная передаточная функция, на основе анализа заданных во временной области тестирующего сигнала (Stimulus Signal) и выходного сигнала тестируемого объекта (Response Signal) на входе и выходе тестируемой электрической цепи. (рис. 62)

Рис. 62. Входы и выходы пиктограммы расчета передаточной функции

Лицевая панель системы регулирования и блок-диаграмма тестирования может выглядеть следующим образом (рис. 63).

223

Рис. 63. Лицевая панель тестирования систем автоматики

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

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

224

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

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

вания» – http://www.mathmodel.ru.

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

225

ЛЕКЦИЯ 25. АЛГОРИТМ И ЕГО СВОЙСТВА. СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ

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

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

Само слово «алгоритм» происходит от algorithmi – латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами.

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

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

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

226

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

1.Одно из первоначальных требований, которое предъявляется

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

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

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

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

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

227

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

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

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

Способы записи алгоритма. Основными изобразительными средствами алгоритмов являются следующие способы их записи:

-словесный;

-формульно-словесный;

-блок-схемный;

-псевдокод;

-структурные диаграммы;

-языки программирования.

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

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

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

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

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

-следования, или последовательности операторов;

-развилки, или условного оператора;

228

- повторения, или оператора цикла.

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

Таблица 18

Графические изображения блок-схем

229