КОНТРОЛЬНАЯ РАБОТА- Бесплатная работа ОмГА- пример/образец служит исключительно для написания собственного материала. Для заказа уникальной контрольной работы необходимо обратиться к менеджерам. Все контакты указаны на сайте.
Частное учреждение образовательная организация высшего образования "Омская гуманитарная академия"
КОНТРОЛЬНАЯ РАБОТА
на тему: «Формы записи алгоритмов: язык псевдокода, блок-схема»
по учебной дисциплине: Инфокоммуникационные технологии в образовании лиц с ограниченными возможностями здоровья
Выполнила:
Направление подготовки: Специальное
(дефектологическое) образование
Форма обучения: Заочная
Оценка: _____ _______________
______________ _____________
Подпись Фамилия И.О.
“____”_______________2023 г.
Омск, 2023
Содержание
Введение……………………………………………...……………………………3
- Алгоритм и его свойства. Способы записи алгоритма……………..………..4
- Классификация алгоритмов…………………………………………………....8
- Языки программирования…………………………………………………….15
Заключение………………………………………………………………...……..19
Список литературы………………………………………...…………………….20
Введение
Актуальность выбранной темы для данной работы неоспорима. Ведь с появлением ЭВМ появилась необходимость интенсифицировать потоки информации человек - компьютер - человек. Но для повышения эффективности применения человеком компьютера как инструмента нужны общая мысль, общие понятия. С появлением науки Информатики появился новый метод - алгоритмизация - процесс составления алгоритмов решения задачи.
Алгоритмический стиль мышления позволяет связать воедино функционирование информации в конкретной среде с требованиями её машинной обработки. Алгоритмическое мышление помогает формировать навыки: уметь планировать структуру действий, необходимых для достижения заданной цели при помощи фиксированного набора средств; строить информационные структуры для описания объектов и средств; организовывать поиск информации, необходимой для решения поставленной задачи; правильно, четко и однозначно формулировать мысль в понятной собеседнику форме и правильно принимать текстовое сообщение; своевременно обращаться к ЭВМ при решении задач из любой области; формировать навыки анализа информации, умение структурировать ее.
Цель данной работы состоит в исследовании средств и языков описания алгоритмов. Для достижения данной цели необходимо решить ряд следующих задач:
- дать определение понятию алгоритм, определить его свойства и способы записи;
- рассмотреть классификацию алгоритмов;
- рассмотреть языки описания алгоритмов.
- Алгоритм и его свойства. Способы записи алгоритма
Само слово «алгоритм» возникло из названия латинского перевода книги арабского математика IX века Аль-Хорезми «Algoritmi de numero Indoru», что можно перевести как «Трактат Аль-Хорезми об арифметическом искусстве индусов». Составление алгоритмов и вопросы их существования являются предметом серьёзных математических исследований.
Под алгоритмом понимают набор правил, определяющих процесс преобразования исходных данных задачи в искомый результат.
Анализ примеров различных алгоритмов показывает, что запись алгоритма распадается на отдельные указания исполнителю выполнить некоторое законченное действие. Каждое такое указание называется командой. Команды алгоритма выполняются одна за другой. После каждого шага исполнения алгоритма точно известно, какая команда должна выполнятся следующей. Совокупность команд, которые могут быть выполнены исполнителем, называется системой команд исполнителя.
Алгоритм не только задает последовательность выполнения операций при решении конкретной задачи, но и должен обладать рядом свойств.
Свойства алгоритма:
Однозначность алгоритма, под которой понимается единственность толкования исполнителем правила построения действий и порядок их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя.
Конечность алгоритма - обязательность завершения каждого из действий, составляющих алгоритм, и завершимость выполнения алгоритма в целом.
Результативность алгоритма, предполагающая, что выполнение алгоритма должно завершиться получением определённых результатов.
Массовость, т. е. возможность применения данного алгоритма для решения целого класса задач, отвечающих общей постановке задачи. Для того чтобы алгоритм обладал свойством массовости, следует составлять алгоритм, используя обозначения величин и избегая конкретных значений.
Правильность алгоритма, под которой понимается способность алгоритма давать правильные результаты решения поставленных задач.
Эффективность - для решения задачи должны использоваться ограниченные ресурсы компьютера (процессорное время, объём оперативной памяти и т. д.).
Создание алгоритма для решения задач какого-либо типа, его представление исполнителю в удобной для него форме - это творческий акт.
Алгоритм может быть представлен различными способами:
- на разговорном, естественном языке;
- на языке блок-схем;
- на языке программирования.
Выбор и разработка алгоритма и численного метода решения задачи имеют важнейшее значение для успешной работы над программой. Тщательно проработанный алгоритм решения задачи - необходимое условие эффективной работы по составлению алгоритму.
Приведем пример записи алгоритма на естественном языке, то есть на языке человеческого общения. Требуется вычислить сумму двух чисел. Обозначим эти числа a и b. Тогда алгоритм можно записать следующим образом:
- Считать число a.
- Считать число b.
- Выполнить суммирование c := a + b.
- Вывести число c.
Видно, что формулировка алгоритма не зависит от конкретных значений переменных a и b, поэтому его можно применять для решения достаточно большого числа сходных задач, в данном случае вместе составляющих целый класс задач суммирования. Алгоритм описывает действия не над конкретными значениями, а над абстрактными объектами.
Основными объектами программирования являются переменные. Переменные в программе отличаются от переменных, используемых в записи математических формул. Несмотря на сходство терминов, правила использования переменных в программах для компьютера отличаются от правил работы с математическими переменными. Это различие необходимо уяснить. В программировании переменную можно трактовать как одну или несколько ячеек оперативной памяти компьютера, которым присвоено определённое имя. Содержимое этих ячеек может меняться, но имя переменной остаётся неизменным. В математике значение переменной в рамках определённой задачи неизменно, но меняется в других задачах из данного класса. Именно поэтому конструкция а: = а + 1 воспринимается программистом совершенно естественно, а уравнение a = a + 1 математик сочтёт неверным. В первом случае имеется в виду вычисление суммы содержимого ячейки а и числовой константы 1 и занесение полученного результата в ту же ячейку а. Второй случай равносилен неверному тождеству 0 = 1.
Иногда используют полуформальный язык с ограниченным словарём (часто на основе английского языка), промежуточный между естественным языком и языком программирования. Такой язык называется псевдокодом. Запись алгоритма на псевдокоде называется структурным планом. Псевдокод удобен тем, что позволяет программисту сосредоточиться на формулировке алгоритма, не задумываясь над синтаксическими особенностями конкретного языка программирования.
Псевдокод:
Алгоритм < название >
Начало
< последовательность действий >
Конец
Любой алгоритм может быть представлен в виде последовательности действий. Под действием понимают либо базовую операцию, либо базовую структуру.
В качестве базовых операций используются:
операция присваивания вида
< переменная > := < выражение >
операция ввода/вывода
ввод (список ввода)
вывод (список вывода).
Смысл операции присваивания состоит в вычислении результата выражения, стоящего справа от знака «:=», для конкретных значений входящих в него переменных и присваивании этого результата переменной, стоящей слева от знака «:=», например:
D := 5
D := D+1
Min := C
При выполнении операции ввода ввод ( A, B, C) переменным из списка ввода A, B и C присваиваются конкретные значения, вводимые с клавиатуры, например:
-5 7 20 {Enter}
В результате в памяти получим:
A = -5, B = 7, C = 20.
Операция вывода осуществляет вывод значений переменных и выражений из списка вывода на экран, например:
вывод (A, B, C, 10)
На экране получим: - 5 7 20 10
Описание алгоритмов с помощью блок-схем.
Для разработки структуры программы удобнее пользоваться записью алгоритма в виде блок-схемы (в англоязычной литературе используется термин flow-chart). Для изображения основных алгоритмических структур и блоков на блок-схемах используют специальные графические символы.
Составим алгоритм вычисления квадратного корня из произвольного положительного вещественного числа х в виде блок-схемы.
Блок-схема для решения данного рода задач будет выглядеть следующим образом:
Начало
Ввод вещественного числа х
Вычисление корня по формуле
Вывод результата
Конец
- Классификация алгоритмов
Различают три типа базовых структур:
- Следование
- Развилка
- Цикл
Структура Следование - одна из самых важных структур. Она означает, что два действия должны быть выполнены друг за другом.
Структура Развилка обеспечивает выбор одной из двух альтернатив: если < условие 1 > то
< действие 1 >
иначе
< действие 2 >
все
Существует сокращенная форма структуры Развилка, которая позволяет выполнить действие или пропустить его:
если < условие > то < действие >
все
Обобщением структуры Развилка является Множественный выбор:
если Var = Const1 то < действие 1 >
если Var = Const2 то < действие 2 >
если Var = ConstN то < действие N >
все
В зависимости от значения переменной Var выполняется одно из указанных действий, например, если Var = Const3, то выполняется < действие 3 >.
Третьей базовой структурой является Цикл, который предусматривает повторное выполнение определенных действий, необходимое для большинства программ. Различают следующие типы структур Цикл:
цикл «от до»
цикл «пока»
цикл «до»
Цикл «от до» управляет повторением выполнения действия с помощью переменной цикла:
цикл от I:= N1 до N2
< действие >
Здесь I - переменная цикла, N1, N2 - начальное и конечное значения переменной цикла, вычисляются один раз при входе в цикл. Переменная цикла пробегает все следующие друг за другом в порядке возрастания значения от начального до конечного. Изменение значения переменной цикла происходит автоматически после каждого выполнения действия, указанного внутри цикла. В зависимости от соотношения N1 и N2 цикл может не выполниться ни разу (N1>N2) или выполниться (N2-N1+1) раз.
В цикле «пока» управление внутри цикла осуществляется с помощью логического условия:
цикл пока < условие>
< действие >
кц
Выполнение действия повторяется до тех пор, пока истинно условие. Проверка условия осуществляется в начале цикла. Это означает, что действие может не выполниться ни разу. Чтобы такой цикл не был бесконечным, внутри цикла необходимо предусмотреть изменение значения условия с истинного на ложное.
Третий тип структуры цикл «до» имеет вид:
цикл
< действие > до < условие>
кц
Как только значение условия становится истинным, цикл прекращается. Цикл “до“ независимо от значения условия выполнится по меньшей мере один раз, т.к. проверка условия производится после выполнения действия. Для завершения цикла необходимо внутри цикла изменить условие с ложного на истинное. Выбор структуры цикла определяется особенностями алгоритма решения конкретной задачи.
Существенная особенность перечисленных базовых структур состоит в том, что каждая из них имеет один вход и один выход. Их можно соединять друг с другом в любой последовательности. В качестве действия может использоваться любая из перечисленных структур, что обеспечивает возможность вложенности одних структур в другие.
В зависимости от применяемых базовых структур различают следующие типы алгоритмов:
- линейные
- разветвляющиеся
- циклические.
Линейная алгоритмическая структура. Типовые примеры.
Линейным называется алгоритм, блоки которого расположены последовательно один за другим, нет условий и повторений.
Покажем общую структуру линейного алгоритма в виде блок-схемы.
Основной принцип программирования заключается в том, что обрабатывать можно только те данные, которые находятся в определенных областях оперативной памяти компьютера. Для того чтобы поместить исходные данные в оперативную память используются операторы ввода данных.
Для реализации процесса обработки данных используется оператор присваивания.
Результат вычислений помещается в область S оперативной памяти. Чтобы вывести результат из памяти на экран монитора необходимо использовать оператор вывода.
Операторы ввода данных:
INPUT - оператор ввода данных с клавиатуры. Данные задаются в виде переменных. Переменная - это величина, значение которой может меняться в процессе выполнения программы. Для обозначения переменной используются их имена (идентификаторы) - последовательность до 40 латинских букв и цифр, начинающаяся с буквы. Данные могут быть следующих основных типов:
- целые INTEGER (Y%) - 2 байта в памяти (от -32768 до 32767),
- длинные целые LONG (Y&) - 4 байта (от -231 до 231-1),
- вещественные SINGLE (Y) - 6 знаков после , -4 байта (от -3.4Е+38 до 3.4Е+38),
- вещественные удвоенной точности DOUBLE (Y#) -16 знаков после ,- 8 байт (от -Е+308 до Е+308),
- символьные STRING (Y$) - последовательность символов до 32767 символов длиной.
Например: INPUT a,b или INPUT “Введите два числа”;a,b
DATA, READ - операторы ввода данных из блока памяти. Например: DATA 3,4 : READ a,b
Оператор присваивания может быть использован как для ввода данных (Например: a=3 : b=4), так для вычисления выражений. (Например: S=a*b). Оператор присваивания вычисляет выражение, расположенное справа от символа присваивания (=) и результат присваивается переменной, расположенной слева от символа присваивания. При записи арифметического выражения используются арифметические операции и функции. Приоритет выполнения арифметических операций сохраняется. Функции можно использовать стандартные (встроенные) COS(X), SQR(X) … и задаваемые самим пользователем. (Например: Y=3*SQR(X)^2)
Для вывода данных используется оператор PRINT.
Например: PRINT S или PRINT “Площадь”;S или PRINT a,b,S
Для окончания программы используется оператор END. В начале программы можно использовать оператор очистки экрана - CLS.
Пример линейной программы вычисления площади прямоугольника и ее алгоритм в виде блок-схемы:
CLS
INPUT “Введите две стороны прямоугольника”; a,b
S = a * b
PRINT “Площадь”; S
END
Разветвляющая алгоритмическая структура. Основные операторы циклов. Типовые примеры
Алгоритм называется разветвляющимся, если содержит хотя бы одно условие, в результате которого обеспечивается переход на один из двух возможных вариантов решения задачи. Ветвление может быть полным (действия и после да и после нет) и неполным (в случае если нет - ничего не происходит).
Пример разветвляющегося алгоритма - алгоритм решения квадратного уравнения. Появление условия при решении этой задачи связано с отсутствием корней при отрицательном дискриминанте. Рассмотрим блок-схему этого алгоритма:
Для данной алгоритмической структуры характерно, что в любой момент времени её реализации осуществляется обработка только по какой-либо одной из ветвей.
Для описания разветвляющегося алгоритма существуют операторы:
условный
блочной структуры:
IF условие THEN
блок действий 1
ELSE
блок действий 2
ENDIF
линейной структуры:
IF условие THEN блок 1 ELSE блок 2
Обе структуры могут быть использованы как в полной форме так и в усеченной - без блока ELSE.
При работе условного оператора сначала проверяется выполнение условия. Если условие выполняется (истинное), то реализуется блок 1, в противном случае - блок 2. Условие - это логическое выражение, использующее операции сравнения (=, <, > <=, >=, <>) и логические операции (AND, OR).
Программа решения квадратного уравнения с использованием условного оператора имеет вид:
CLS : INPUT A,B,C : D=B^2-4*A*C
IF D>0 THEN
X1=(-b+SQR(d))/(2*a) : X2=(-b-SQR(d))/(2*a) : PRINT X1,X2
ELSE
PRINT ”Решенией нет”
ENDIF
выбора (выражением может быть список через запятую 1,3,4 диапазон значений 1 TO 9; операция сравнения IS >=).
SELECT CASE выражение
CASE условие 1
блок операторов 1
CASE условие 2
блок операторов 2
CASE ELSE
блок операторов n
END SELECT
CLS : INPUT A,B,C : D=B^4*A*C
SELECT CASE D
CASE IS >0
X1=(-b+SQR(d))/(2*a)
X2=(-b-SQR(d))/(2*a) : PRINT X1,X2
CASE ELSE
PRINT ”Решенией нет”
END SELECT
END
Циклические алгоритмические структуры. Основные операторы ветвления. Типовые примеры
Алгоритм называется циклическим, если содержит участок, повторяющийся один или много раз.
Циклы бывают с определённым количеством, неопределённым числом вычислений.
Оператор цикла с параметром:
FOR I = IН TO IK STEP h
тело цикла
NEXT I
Оператор цикла с предусловием:
DO WHILE условие продолжения вычислений (UNTIL условие прекращения вычислений)
тело цикла
LOOP
Оператор цикла с постусловием:
DO
тело цикла
LOOP WHILE условие продолжения вычислений (UNTIL условие прекращения вычислений)
- Языки программирования
Прогресс компьютерных технологий определил процесс появления новых разнообразных знаковых систем для записи алгоритмов - языков программирования. Смысл появления такого языка - оснащенный набор вычислительных формул дополнительной информации, превращает данный набор в алгоритм.
Язык программирования служит двум связанным между собой целям: он дает программисту аппарат для задания действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист, размышляя о том, что делать. Первой цели идеально отвечает язык, который настолько "близок к машине", что всеми основными машинными аспектами можно легко и просто оперировать достаточно очевидным для программиста образом. Второй цели идеально отвечает язык, который настолько «близок к решаемой задаче», чтобы концепции ее решения можно было выражать прямо и коротко.
Связь между языком, на котором мы думаем/программируем, и задачами и решениями, которые мы можем представлять в своем воображении, очень близка. По этой причине ограничивать свойства языка только целями исключения ошибок программиста в лучшем случае опасно. Как и в случае с естественными языками, есть огромная польза быть, по крайней мере, двуязычным. Язык предоставляет программисту набор концептуальных инструментов, если они не отвечают задаче, то их просто игнорируют. Например, серьезные ограничения концепции указателя заставляют программиста применять вектора и целую арифметику, чтобы реализовать структуры, указатели и т.п. Хорошее проектирование и отсутствие ошибок не может гарантироваться чисто за счет языковых средств. Может показаться удивительным, но конкретный компьютер способен работать с программами, написанными на его родном машинном языке. Существует почти столько же разных машинных языков, сколько и компьютеров, но все они суть разновидности одной идей простые операции производятся со скоростью молнии на двоичных числах. Персональные компьютеры IBM используют машинный язык микропроцессоров семейства 8086, т.к. их аппаратная часть основывается именно на данных микропроцессорах. Можно писать программы непосредственно на машинном языке, хотя это и сложно. На заре компьютеризации (в начале 1950-х г.г.), машинный язык был единственным языком, большего человек к тому времени не придумал. Для спасения программистов от сурового машинного языка программирования, были созданы языки высокого уровня (т.е. немашинные языки), которые стали своеобразным связующим мостом между человеком и машинным языком компьютера. Языки высокого уровня работают через трансляционные программы, которые вводят "исходный код" (гибрид английских слов и математических выражений, который считывает машина), и в конечном итоге заставляет компьютер выполнять соответствующие команды, которые даются на машинном языке. Существует два основных вида трансляторов:
- интерпретаторы, которые сканируют и проверяют исходный код в один шаг,
- компиляторы, которые сканируют исходный код для производства текста программы на машинном языке, которая затем выполняется отдельно.
Интерпретаторы. Одно, часто упоминаемое преимущество интерпретаторной реализации состоит в том, что она допускает "непосредственный режим". Непосредственный режим позволяет вам задавать компьютеру задачу вроде PRINT 3.14159*3/2.1 и возвращает вам ответ, как только вы нажмете клавишу ENTER (это позволяет использовать компьютер стоимостью 3000 долларов в качестве калькулятора стоимостью 10 долларов). Кроме того, интерпретаторы имеют специальные атрибуты, которые упрощают отладку. Можно, например, прервать обработку интерпретаторной программы, отобразить содержимое определенных переменных, бегло просмотреть программу, а затем продолжить исполнение.
Больше всего программистам нравится в интерпретаторах возможность получения быстрого ответа. Здесь нет необходимости в компилировании, так как интерпретатор всегда готов для вмешательства в вашу программу. Введите RUN и результат вашего самого последнего изменения оказывается на экране. Однако интерпретаторные языки имеют недостатки. Необходимо, например, иметь копию интерпретатора в памяти все время, тогда как многие возможности интерпретатора, а, следовательно, и его возможности могут не быть необходимыми для исполнения конкретной программы. Слабо различимым недостатком интерпретаторов является то, что они имеют тенденцию отбивать охоту к хорошему стилю программирования. Поскольку комментарии и другие формализуемые детали занимают значительное место программной памяти, люди стремятся ими не пользоваться. Хуже всего то, что интерпретаторы тихоходны. Ими затрачивается слишком много времени на разгадывание того, что делать, вместо того чтобы заниматься действительно делом. При исполнении программных операторов, интерпретатор должен сначала сканировать каждый оператор с целью прочтения его содержимого (что этот человек просит меня сделать?), а затем выполнить запрошенную операцию. Операторы в циклах сканируются излишне много.
Компиляторы. Компилятор-это транслятор текста на машинный язык, который считывает исходный текст. Он оценивает его в соответствии с синтаксической конструкцией языка и переводит на машинный язык. Другими словами, компилятор не исполняет программы, он их строит. Интерпретаторы невозможно отделить от программ, которые ими прогоняются, компиляторы делают свое дело и уходят со сцены. При работе с компилирующим языком, таким как Турбо-Бейсик, вы придете к необходимости мыслить о ваших программах в признаках двух главных фаз их жизни: периода компилирования и периода прогона. Большинство программ будут прогоняться в четыре - десять раз быстрее их интерпретаторных эквивалентов. Если вы поработаете над улучшением, то сможете достичь 100-кратного повышения быстродействия. Оборотная сторона монеты состоит в том, что программы, расходующие большую часть времени на возню с файлами на дисках или ожидание ввода, не смогут продемонстрировать какое-то впечатляющее увеличение скорости.
Заключение
Итак, мы дали понятие алгоритма, определили его свойства и способы записи, рассмотрели классификацию и языки описания алгоритмов.
На основании вышеизложенного сделаем краткие выводы.
Любой человек постоянно встречается с множеством задач: от самых простых и хорошо известных до очень сложных. Для множества из них существуют определенные правила (инструкции, предписания), объясняющие исполнителю, как решать данную задачу. Эти правила человек может изучить заранее или сформулировать сам в процессе решения. Чем более точно и однозначно будут описаны правила решения задач, тем быстрее человек овладеет ими и будет эффективнее их применять. Такие правила принято называть алгоритмами.
Таким образом, алгоритм - это четкая последовательность действий, направленная на достижение поставленной цели или решения задачи.
Существуют несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций: это дискретность, определенность, результативность, массовость.
Различают три типа базовых структур: следование, развилка и цикл. В зависимости от применяемых базовых структур различают следующие типы алгоритмов: линейные, разветвляющиеся и циклические.
Прогресс компьютерных технологий определил процесс появления новых разнообразных знаковых систем для записи алгоритмов - языков программирования. Смысл появления такого языка - оснащенный набор вычислительных формул дополнительной информации, превращает данный набор в алгоритм.
Язык программирования служит двум связанным между собой целям: он дает программисту аппарат для задания действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист, размышляя о том, что делать.
Список литературы
- Ахо Альфред В. Структуры данных и алгоритмы: Вильямс / пер. с английского и ред. Минько А. А., Ахо Альфред В., Хопкрофт Джон Э., Ульман Джеффри Д. — М. и др.: Вильямс, 2017. – 382 с.
- Левитин А.В. Алгоритмы: введение в разработку и анализ. – М.: Издательский дом «Вильямс», 2019. – 576 с.
- Макконнелл Дж. Основы современных алгоритмов. 2-е изд., доп. – М.: Техносфера, 2018. – 368 с.
- Макконелл, Дж. Анализ алгоритмов. Вводный курс / Дж. Макконелл,- М.: Техно-сфера, 2019,- 304 с.
- Вирт Никлаус Алгоритмы и структуры данных: Нев. Диалект / Вирт Никлаус, [перевод с английского Д. Б. Подшивалова] — 2-е изд., испр. — СПб.: Нев. Диалект, 2019. — 351с.
- Скиена С. Алгоритмы. Руководство по разработке. – 2-е изд. – СПб.: БХВ-Петербург, 2020. – 720 с.
- Седжвик Р. Фундаментальные алгоритмы на С++. Части 1 — 5. Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах: Пер. с англ. – К.: Издательство “ДиаСофт”, 2017.
- Окулов С.М. Программирование в алгоритмах. – 3-е изд. – М.: БИНОМ. Лаборатория знаний, 2017. – 383 с.