Обработка информации на ЭВМ. Урок Этапы решения задач на ЭВМ

Вид материала

Содержание

Анализ результатов. Если необходимо, уточнение модели (перейти к п.3)
Системой команд исполнителя (ски
Неформальный исполнитель
Управление исполнителями.
Обратная связь
Алгоритм и его свойства
Свойства алгоритма
5. Результативность, конечность
Способы представления алгоритмов
Построение математической модели
Математическая постановка задачи

Подобный материал:

Обработка информации на ЭВМ.

Урок 1. Этапы решения задач на ЭВМ.

Как вы думаете, все ли задачи можно решить с помощью компьютера?

Существуют задачи, которые без компьютера решить невозможно. Например, решить систему уравнений 20-й степени с 20-ю неизвестными; найти значение числа π с точностью 100 знаков после запятой.
Есть задачи, которые без компьютера решить проще, чем с помощью компьютера: 2+2
Есть также задачи, которые с помощью компьютера решить невозможно: что я хочу съесть сегодня на обед.

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

Задача: Определить площадь поверхности стола.

Обычно сразу напрашивается ответ: длину умножить на ширину. Потому что есть такая формула: S=A*B. Но ведь это же не формула для определения площади поверхности стола, а для определения площади прямоугольника. Есть и другие формулы определения площади, например, площади круга: S=2R.

Хочется возразить: стол-то – прямоугольный. А кто это сказал? Нам ведь не уточнили, площадь какого именно стола нужно определить. Значит, необходимо уточнить задачу: определить площадь конкретного прямоугольного стола.

Теперь можно выделить существенные признаки, что стол – прямоугольный, именно поэтому мы можем применить известную формулу S=A*B. Важен ли факт, что стол – белого цвета, сделан из пластика и проч.? Нет.

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

Что является исходными данными для решения задачи? – Длина и ширина прямоугольника.

Как будем решать задачу? – По формуле S=A*B.

Далее необходимо определить последовательность шагов (действий), которые нужно выполнить (алгоритм):

1. Измерить длину.

2. Измерить ширину.

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

Поэтому получим следующую последовательность действий для компьютера:

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

2. Вычислить S=A*B.

3. Сообщить полученный результат S.

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

Таким образом, вырисовываются следующие этапы решения задач с использованием ЭВМ:

Постановка задачи
Уточнение (если необходимо) постановки задачи.
Построение математической (формализованной) модели.

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

Алгоритм.
Программа на языке программирования (ввод программы в компьютер, ее отладка, тестирование и выполнение на ЭВМ).

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

Т.е. необходимо ОБЯЗАТЕЛЬНО добавить еще один этап – Анализ результатов

Анализ результатов. Если необходимо, уточнение модели (перейти к п.3)

Урок 2. Алгоритм и его свойства.

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

ИСПОЛНИТЕЛЬ - человек или механическое устройство (или, например, компьютер), который умеет выполнять строго определенный набор команд (и больше ничего!).

Набор команд, который умеет выполнять Исполнитель (т.е. список всех команд), называется СИСТЕМОЙ КОМАНД ИСПОЛНИТЕЛЯ (СКИ).

Исполнители бывают ФОРМАЛЬНЫМИ и НЕФОРМАЛЬНЫМИ.

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

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

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

какие команды умеет выполнять исполнитель;
как они отдаются;
как выполняются;
когда возникает отказ.(ОТКАЗ - это ситуация, когда исполнитель не может выполнить команду).

Исполнитель

Среда СКИ

какие команды

как отдаются

как выполняются

когда отказ

Управление исполнителями.

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

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

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

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

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

Управляющий объект

Управляемый объект

Управляющее воздействие

В приведенных примерах управляющее воздействие происходит в разной форме…

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

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

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

Т.о., объект управления можно назвать исполнителем управляющего алгоритма.

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

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

Управляющий объект

Управляемый объект

Управляющее воздействие

Обратная связь

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

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

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

команды

Человек Исполнитель

результаты

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

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

Управление в этом случае распадается на несколько этапов.

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

программа

Ч

еловек Компьютер Этап 1

ЭВМ команды  Исполнитель Этап 2

 результаты

 Исполнитель

Человек результаты Этап 3

 ЭВМ

Итак, управление исполнителем возможно с использованием двух режимов:

Непосредственное управление:
Программное управление:

АЛГОРИТМ И ЕГО СВОЙСТВА.

Само слово алгоритм происходит от имени выдающегося математика средневекового Востока Мухаммеда аль Хорезми (787-850) (Мухаммед из Хорезма). Им были предложены приемы выполнения арифметических вычислений с многозначными числами. Позже в Европе эти приемы назвали алгоритмами (Algorithmi – латинское написание имени аль-Хорезми)

Точного определения алгоритм нет. Это понятие можно определить, например, так:

АЛГОРИТМ - точное предписание, задающее преобразование исходных данных в искомый результат за конечное число шагов.

АЛГОРИТМ - это последовательность команд, в результате выполнения которых будет решена поставленная задача.

Другими словами алгоритм - это последовательность действий со строго определенными правилами выполнения.

Алгоритм, записанный на специальном языке, понятном исполнителю (для исполнителя ЭВМ – на языке программирования), называется ПРОГРАММОЙ.

Существует много разных языков программирования. В настоящее время их число насчитывает уже несколько тысяч. Вот некоторые из них: Фортран, Алгол, ПЛ/1, Бейсик, Паскаль, Си, Ада, Лого, Лисп, Пролог.

Все языки имеют правила, устанавливающие, что и как можно писать. Эти правила называются СИНТАКСИСОМ.

Примеры:

Алгоритм приготовления бутерброда: исх. данные: хлеб, продукт. Искомый результат - бутерброд (ломтик продукта, положенный на ломтик хлеба). Предписание - а) отрезать ломтик хлеба; б) отрезать ломтик продукта; в) положить продукт на хлеб.
“Пойди туда - не знаю куда, принеси то - не знаю что” (алгоритмом не является)
Правила поведения в компьютерном классе: … не ударяйте резко и сильно по клавиатуре (алгоритмом не является, т.к. алгоритм – это последовательность действий, а здесь перечень того, чего делать не нужно)

СВОЙСТВА АЛГОРИТМА:

1. ОПРЕДЕЛЕННОСТЬ, ТОЧНОСТЬ - однозначность предписываемой последовательности действий, не допускающая произвольного ее толкования, т.е. каждая команда алгоритма должна определять однозначное действие исполнителя (единственность толкования правил выполнения действий и их порядка) (каждому ясно, что “отрезать ломтик хлеба” означает: взять нож, а не пилу...).

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

3. ДИСКРЕТНОСТЬ – разделение алгоритма на последовательность шагов, которые исполнитель может выполнить без дополнительных разъяснений ( а), б). ...).

4. ДЕТЕРМИНИРОВАННОСТЬ – исполнитель должен выполнять команды алгоритма в строго определенной последовательности (например, при взлете самолет не может оторваться от взлетной полосы, пока самолет не набрал необходимую скорость, нельзя открыть дверь, не достав сначала ключ и т.п.)

5. РЕЗУЛЬТАТИВНОСТЬ, КОНЕЧНОСТЬ - возможность получения результата за конечное число шагов (как бы долго алгоритм ни выполнялся, он все равно когда-нибудь закончится).

СПОСОБЫ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ:

1. Словесный (кулинарный рецепт).

2. Графический (в виде блок-схем).

3. На алгоритмическом языке.

ПРЕДСТАВЛЕНИЕ АЛГОРИТМОВ С ПОМОЩЬЮ БЛОК-СХЕМ.

Изображение основных блоков:

^{Процесс, выполнение действий, вычисление по формуле}

^{Блок принятия решения (блок проверки условия)}

^{Ввод исходных данных (в общем виде)}

Запишем в виде блок-схемы алгоритм определения площади стола.

Задача.

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

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

Математическая постановка задачи: Даны два числа А и В (их необходимо ввести в компьютер). Найти наибольшее из них и записать его в переменную С.

Исходные данные: два числа А и В. Результат – максимальное число С.

Алгоритм: запишем алгоритм сначала в словесном виде, а затем – в графическом

Ввести в компьютер 2 числа А и В.
Если А больше В, то С=А, в противном случае С=В.
Вывести результат – С.

Алгоритм в графическом виде (блок-схема) представлен на Рис. 2.

Ошибки в алгоритмах.

1. Синтаксические. Если при составлении алгоритма или записи программы на языке программирования мы случайно вместо команды ввода исходных данных INPUT напишем IMPUT, или Роботу вместо «вправо» скомандуем «вправа» то ЭВМ нашу запись не поймет и, даже не приступая к выполнению алгоритма, сообщит об ошибке.

2. Отказы - проявляются при выполнении алгоритма, например при попытке исполнителя Робот выйти за пределы поля или попытке деления на 0. В этом случае выполнение алгоритма или программы прекратится, и ЭВМ сообщит об ошибке.

3. Логические ошибки, которые ни ЭВМ, ни исполнитель вообще не могут обнаружить. Например, если мы вместо команды “вправо” напишем случайно “влево”, Робот выполнит алгоритм, но мы не попадем в ту клетку, куда было надо. Или если вместо команды S=A*B мы напишем S=A/B, ЭВМ все равно выполнит эту команду. Однако никаких сообщений об ошибках мы не получим (да и откуда ЭВМ может знать, куда мы на самом деле хотели переместить Робота, или по какой формуле мы хотели считать).

Blog

Обработка информации на ЭВМ. Урок Этапы решения задач на ЭВМ

Содержание