Введение в программирование и основы алгоритмизации задач

 

 Введение в программирование и основы алгоритмизации задач  

 

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

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

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

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

Анализ алгоритмов

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

Примеры 

1. Вычислить значение  функции   у= х2

шаг 1. Взять (задать) конкретное  значение  аргумента х

шаг 2. Умножить х на х,  вычислив х2

шаг 3. Напечатать полученный результат    у= х2

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

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

2. ПОСТРОЕНИЕ АЛГОРИТМА. Алгоритм – некоторая конечная последовательность предписаний (правил), определяющая процесс преобразования исходных и промежуточных данных в результат решения задачи.  В нашем примере по созданию модели ВУЗа нам будет необходимо связать сформулированные на первом этапе зависимости между собой.  В итоге мы должны будем получить  подробную запись решения задачи, как правило, расписанную в виде отдельных процедур, соединенных между собой логическими связями. Предположим, что в наш алгоритм мы включили процедуру оценки влияния отмен и переносов занятий  на качество подготовки студентов, которая должна влиять с какого- то  определенного количества отмены занятий. Для этого в структуру алгоритма нам нужно будет включить блок, проверяющий выполнение следующего условия: «Количество переносов занятий больше N?». Если это условие не выполняется, осуществляется переход к очередной процедуре. Если это условие выполняется, сначала вносятся изменения в конечный  критерий, а потом осуществляется переход к очередной процедуре. Таким образом, в  итоге мы должны получить алгоритм решения нашей задачи в виде отдельных, не связанных между собой процедур, выполнение которых  завершается  расчетом критерия оценки качества подготовки студентов.

3. РАЗРАБОТКА ПРОГРАММЫ.

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

Определенностью, т.е. общепонятностью  и точностью;       

Массовостью, т.е. возможностью использования различных данных при решении однотипных задач;       

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

Дискретностью, при выполнении разбивается на конечную последовательность действий или шагов;       

Конечностью, т.е. должен выполняться  за конечное время.

2. Для представления алгоритмов используются несколько способов:      

Словесный (описание на естественном человеческом языке);       

Графический (на языке блок-схем);        

С помощью символов специального языка проектирования программ-псевдокодов;      

С помощью одного из  языков программирования.

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

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

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

Процесс решения задачи на ЭВМ состоит из восьми этапов:         

Первый – постановка задачи;          

Второй- ее математическое описание;          

Третий – алгоритмизация задачи;         

Четвертый – программирование;          

Пятый  - разработка тестовой задачи;         

Шестой – перенос программы  на машинные носители;         

Седьмой – отладка задачи;          

Восьмой –получение и анализ результатов.

3.Виды алгоритмов

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

Рассмотрим алгоритм линейной структуры на примере определения  площади треугольника по трем известным  сторонам a,b и c с использованием теоремы Герона:, где p=0,5*(a+b+c).

2.Разветвляющиеся алгоритмы – алгоритмы, в котором в зависимости от значений некоторого признака производится выбор одного из нескольких направлений, называемых ветвями. В основе организации разветвления лежит проверка логического условия, которое может быть истинно или ложно. Частный вид логического условия – это операция типа =, ≠,>,<,≥,≤.

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

Согласно этой блок-схеме  в зависимости от результата проверки условия выполняются только действия ветви «Да» (действия 1 и 2) или только ветви «нет» (действия 3 и 4).

В алгоритме решения квадратного  уравнения  происходит разветвление после проверки условия D >=0 . В общем случае число может быть больше двух.

Решение квадратного уравнения ax2 + bx + c =0

В зависимости от значения подчеркнутого выражения D=b2 – 4ac искомые результаты могут быть получены из выражений:

x1,2=   0,³, где D

x1,2j*w , где z=-±=z   ,   w=   , если  0<D

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

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

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

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

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

Задать начальное значение параметра цикла;       

Задать правило изменения  параметра цикла;       

Задать условие окончания  цикла.

Согласно этому алгоритму  пока выполняется условие, будет  повторяться действия 1 и 2.

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

 

 

 

Список  использованной литературы:  

 

1 Аветисян Р.Д., Аветисян Д.Д., Теоретические основы информатики.- М: Наука, 1997

2. Аладьев В.З.и др.Основы информатики.- М. «Филин», 1999

3. Гласс Р., Нуазо Р. Сопровождение программного обеспечения? Пер.с англ.М.Мир, 1975

4. Грис Д.Наука программирования.: пер.с англ.М.Мир:, 1984

5. Дейкстры Э. Дисциплина программирования. М.:Мир, 1976

6. Информатика для юристов и экономистов, учебник  для вузов, под ре.  С. В.     Симоновича, Москва, 2004 г.

7. Информатика под ред.Макаровой-3-е перераб. изд.-М., 2003-765

8. Информатика, учебник под ред. профессора Н. В.  Макаровой,  Москва, «Финансы и статистика», 2004 г.

9. Лабораторный практикум по информатике, В. А. Острейковского, Москва, Высшая школа, 2003

10.       Липаев В. Надежность программного обеспечения АСУ.- М.:Энергоиздат, 1981

11.       Липаев В., Потапов А. Оценка затрат на разработку программных средств, М.:Финансы и статистика, 1988

12.       Липаев В., Поташов А. Оценка затрат на разработку программных средств. М.:Финансы и статистика, 1988

13.       Логическое программирование: пер с.англ.М.:Мир, 1988