2803

Основные этапы решения задач на ЭВМ

Лекция

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

Основные этапы решения задач на ЭВМ 1. Математическая формулировка задачи (формализация условий задачи). Любая задача подразумевает наличие входных данных, которые в процессе её решения преобразуются в выходные данные. На этапе формализации...

Русский

2012-10-19

45.5 KB

48 чел.

Лекция 1

Основные этапы решения задач на ЭВМ

1.Математическая формулировка задачи (формализация условий задачи).

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

2. Выбор численного метода решения задач данного класса.

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

3. Разработка алгоритма решения задач данного класса (алгоритмизация), то есть запись методики решения задачи выбранным методом.

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

Для алгоритма должны быть характерны следующие свойства:

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

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

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

Доказано, что для представления любого алгоритма достаточно набора из 2-х базовых элементов, называемых структурами управления. Это «следование» и «ветвление». Часто в качестве альтернативного выбора используются «обход» и «циклическое исполнение» в двух разновидностях: «цикл ДО» и «цикл ПОКА». Блок-схемы структур управления приведены на рисунке 1.

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

4. Программирование разработанного алгоритма, то есть запись конкретного алгоритма на языке конкретной ЭВМ.

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

Рис. 1

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

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

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

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

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

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

По назначению языки высокого уровня делятся на 3 группы.

1 группа. Проблемно-ориентированные языки – предназначенные для решения частных задач обработки данных из конкретной прикладной области (языки САПР, СУБД, систем искусственного интеллекта).

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

3 группа. Универсальные языки – включают средства обработки данных сложной структуры, символьной информации, средства для создания нестандартных типов данных и инструментов для их обработки (языки C, Pascal, C++).

5. Отладка программы.

На завершающем этапе создания программы проводится её отладка, которая представлена в виде схемы на рисунке 2.

Рис. 2

Основные понятия и программы, используемые в процессе отладки.

Исходный текст – текст программы на языке программирования.

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

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

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

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

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

Время компиляции – период, во время которого происходит компиляция программы.

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

Для облегчения процесса программирования существуют специальные программы-оболочки, создающие необходимую для этих целей среду, в которую входят инструменты написания текста программы, редактирования, компиляции и отладки программы. Мы будем работать в среде Borland C++ 3.1.


 

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

22114. Понятие устойчивости конечного автомата 48 KB
  Дело в том что триггера в схеме имеет различные времена задержек сигналов обратной связи которые поступают с выходов триггеров на их входы через комбинационную схему II. По этим причинам если при переходе автомата из состояния ai в as должны измениться состояния нескольких триггеров то между выходными сигналами этих триггеров начинаются гонки. изменит свое состояние раньше других триггеров может через цепь обратной связи изменить может изменить сигналы возбуждения на входах других триггеров до того момента как они изменят свои состояния....
22115. Синтез конечных автоматов 31.5 KB
  В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени но и от состояния схемы которое в свою очередь определяется значениями входных сигналов поступивших в предшествующие моменты времени. Понятие состояния введено в связи с тем что часто возникает необходимость в описании поведения систем выходные сигналы которых зависят не только от состояния входов в данный момент времени но и от некоторых предысторий т. Состояния как раз и соответствуют некоторой памяти о прошлом...
22116. Способы задания автомата 362 KB
  Существует несколько способов задания работы автомата но наиболее часто используются табличный и графический. Совмещенная таблица переходов и выходов автомата Мили: xj ai a0 an x1 a0x1 a0x1 anx1 anx1 xm a0xm a0xm anxm anxm Задание таблиц переходов и выходов полностью описывает работу конечного автомата поскольку задаются не только сами функции переходов и выходов но и также все три алфавита: входной выходной и алфавит состояний. Для задания автомата Мура требуется одна таблица поскольку в этом...
22117. Частичные автоматы 194 KB
  Оказывается что для любого автомата Мили существует эквивалентный ему автомат Мура и обратно для любого автомата Мура существует эквивалентный ему автомат Мили. Рассмотрим алгоритм перехода от произвольного конечного автомата Мили к эквивалентному ему автомату Мура. Требуется построить эквивалентный ему автомат Мура Sb = {Ab Xb Yb b b} у которого Xb = Xa Yb = Ya т. Для определения множества состояний Ab автомата Мура образуем всевозможные пары вида ai yg где yg – выходной сигнал приписанный входящей в ai дуге.
22118. Абстрактный синтез конечных автоматов 25.5 KB
  Составить аналогичную таблицу описывающую работу конечного автомата не представляется возможным т. множество допустимых входных слов автомата вообще говоря бесконечно. Мы рассмотрим один из возможных способов формального задания автоматов а именно задание автомата на языке регулярных событий. Представление событий в автоматах.
22119. Операции в алгебре событий 24.5 KB
  Дизъюнкцией событий S1 S2 Sk называют событие S = S1vS2vvSk состоящее из всех слов входящих в события S1 S2 Sk. Произведением событий S1 S2 Sk называется событие S = S1 S2 Sk состоящее из всех слов полученных приписыванием к каждому слову события S1 каждого слова события S2 затем слова события S3 и т. слова входящие в события S1S2 и S2S1 различны: т. Итерацией события S называется событие{S} состоящее из пустого слова e и всех слов вида S SS SSS и т.
22120. Система основных событий 28.5 KB
  Событие состоящее из всех слов входного алфавита всеобщее событие. F = {x1 v x2 v v xm} Событие содержащее все слова оканчивающиеся буквой xi. Событие содержащее все слова оканчивающиеся отрезком слова l1 S = F l1 Событие содержащее все слова начинающиеся с отрезка слова l1и оканчивающиеся на l2: S = l1 F l2 Событие содержащее только однобуквенные слова входного алфавита S = x1 v x2 v v xm Событие содержащее только двухбуквенные слова входного алфавита S = x1 v x2 v v xm x1 v x2 v v xm Событие содержащее все...
22121. Генетические основы эволюции 118.5 KB
  Комбинативная изменчивость – изменчивость в основе которой лежит образование комбинаций генов которых не было у родителей. Комбинативная изменчивость обуславливается следующими процессами: независимым расхождением гомологичных хромосом в мейозе; случайным сочетанием хромосом при оплодотворении; рекомбинацией генов в результате кроссинговера. Частота мутаций не одинакова для разных генов и для разных организмов. Поскольку генов в каждой гамете много например у человека в геноме содержится около 30 тысяч генов то в каждом поколении около...
22122. ЭЛЕМЕНТАРНЫЕ ФАКТОРЫ ЭВОЛЮЦИИ 88 KB
  Тогда частота аллеля b в популяции будет медленно но неуклонно возрастать в каждом поколении на одну десятитысячную если этому возрастанию не будут препятствовать или способствовать другие факторы эволюции. В принципе только благодаря мутационному процессу новый аллель может практически полностью вытеснить старый аллель из популяции. Однако в одной популяции растущей на вершине урансодержащих гор вблизи Большого Медвежьего озера Канада обнаружены многочисленные мутантные растения с бледнорозовыми цветками. Изоляция – это прекращение...