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

Лекция 8. Программный принцип работы компьютера.

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

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

1) программа вычислений вводится в память ЭВМ и хранится в ней наравне с исходными числами;

2) команды, составляющие программу, представлены в числовом коде по форме ничем не отличающемся от чисел.

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

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

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

Уровни программной конфигурации компьютера:

02На самом нижнем уровне находятся программы базовой системы ввода-вывода (BIOS). Их код записан в одной из микросхем компьютера. В момент включения компьютера эти программы выполняют проверку оборудования и обеспечивают простейшее взаимодействие с клавиатурой и монитором — клавиатура способна реагировать на нажатие некоторых клавиш, а на мониторе отображается информация о ходе запуска компьютера. Взаимодействие с человеком у программ этого уровня крайне ограниченно и возможно только в первые секунды после запуска компьютера.
Системные программы предназначены для работы со всеми устройствами компьютера. Они принадлежат к промежуточному уровню. Одни системные программы управляют работой устройств и используют программы нижнего уровня, а другие отвечают на запросы программ более высоких уровней. Те системные программы, которые непосредственно управляют устройствами, еще называют драйверами устройств. Люди работают с программами этого уровня только в тех сравнительно редких случаях, когда требуется настроить оборудование.
Служебные программы — это следующий уровень, программы которого предназначены для обслуживания компьютера, проверки его устройств, а также для настройки устройств и программ. Одни программы общаются с программами нижних уровней, другие передают данные программам верхнего уровня по их запросу. Степень взаимодействия с человеком определяется необходимостью. Например, мастера по наладке и настройке оборудования активно работают со служебными программами. Обычные пользователи используют их сравнительно редко.
Уровень прикладных программ — самый верхний. Здесь находятся программы, обслуживающие человека и удовлетворяющие его потребности. С их помощью выполняется набор и редактирование текстов, создание чертежей и иллюстраций, коммуникация между людьми, воспроизведение музыки и видео, а также многое другое. Сверху программы прикладного уровня общаются с человеком, а снизу — с программами нижележащих уровней. Прямого доступа к устройствам программы прикладного уровня, как правило, не имеют.

Первая вычислительная машина, способная хранить программу в своей памяти, разрабатывалась в 1943—1948 гг. в США под руководством Джона Мочли и Преснера Экерта.

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

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

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

Моделировать можно:

1. Объекты 

Примеры моделей объектов:

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

2. Явления 

Примеры моделей явлений:

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

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

4. Поведение

При выполнении человеком какого-либо действия ему обычно предшествует возникновение в его сознании модели будущего поведения. Собирается ли он строить дом или решать задачу, переходит улицу или отправляется в поход – он непременно сначала представляет себе все это в уме. Это главное отличие человека мыслящего от всех других живых существ на земле.
Один и тот же объект в разных ситуациях, в разных науках может описываться различными моделями. Например, рассмотрим объект “человек” с точки зрения различных наук:

в механике человек – это материальная точка;

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

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

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

Трёхмерные объекты - это объекты, которые имеют ширину, длину и высоту, т.е. при их построении необходимо оперировать с тремя осями координат. Выделим основные этапы моделирования трёхмерных объектов

Алгоритм. Способы описания алгоритмов.

Основные типы алгоритмических структур

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

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

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

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

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

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

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

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

Способы описания алгоритмов

        Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

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

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

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

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

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

(1) Блок, характеризующий начало/конец алгоритма (для подпрограмм – вызов/возврат);

(2) Блок - процесс, предназначенный для описания отдельных действий;

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

(4) Блок - ввода/вывода с неопределенного носителя;

(5) Блок - ввод с клавиатуры;

(6) Блок - вывод на монитор;

(7) Блок - вывод на печатающее устройство;

(8) Блок – решение (проверка условия или условный блок);

(9) Блок, описывающий блок с параметром;

(10) Блок – границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»;

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

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

Основные алгоритмические конструкции

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

Линейная алгоритмическая конструкция

          Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i- гo действия (шага) выполняется (i+ 1)-е действие (шаг), если i-e действие – не конец алгоритма.

         Пример 1.

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

         Псевдокод:

Ввод двух чисел а, b .

Вычисляем сумму S = а + b .

Вывод S.

Конец.

Разветвляющаяся алгоритмическая конструкция

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

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

             Пример 2.

           Заданы три числа. Найти значение наименьшего из них Заданные числа обозначим: а, b, с; результирующее наименьшее – min. На рис. 5 представлена блок-схема алгоритма решения данной задачи.

Алгоритмическая конструкция «Цикл»

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

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

Арифметический цикл

        В арифметическом цикле число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (К) значений параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение параметра равно N, на втором – N + h, на третьем – N + 2h и т.д. На последнем шаге цикла значение параметра не больше К, но такое, что дальнейшее его изменение приведет к значению, большему, чем К.

        Пример 3.

      Вывести 10 раз слово «Привет!».

       Параметр цикла обозначим i, он будет отвечать за количество выведенных слов. При i=1 будет выведено первое слово, при i=2 будет выведено второе слова и т. д. Так как требуется вывести 10 слов, то последнее значение параметра i=10. В заданном примере требуется 10 раз повторить одно и то же действие: вывести слово «Привет!». Составим алгоритм, используя арифметический цикл, в котором правило изменения параметра i=1,10, 1. т. е. начальное значение параметра i=1; конечное значение i=10; шаг изменения h=1. На рис. 6 представлена блок-схема алгоритма решения данной задачи.

Цикл с предусловием

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

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

Цикл с постусловием

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

Контрольные вопросы:

1. Что такое алгоритм?

2. В чем состоит задача алгоритмизации?

3. Какими свойствами обладает алгоритм?

4. Какие виды алгоритма бывают?