Поделиться
Средства и языки описания представления алгоритмов.docx
Средства и языки описания представления алгоритмов
Воронеж
2022
Содержание
Введение……………………………………………………………………………..3
Глава 1.Теоретическая часть………………………………………………………5
1.1. Что такое алгоритм?………………………………………………………..5
1.2. Происхождение слова и его развитие………………………………………..6
1.3. Виды алгоритмов……………………………………………………………...8
1.4. Способы описания алгоритмов……………………………………………...11
1.5.Свойства алгоритмов………………………………………………………….14
Глава 2. Практическая часть…………………………………………………… ..16
2.1. Виды алгоритмов……………………………………………………………..16
2.2.Способы описания алгоритмов………………………………………………17
2.3. Свойства алгоритмов………………………………………………………...20
Заключение………………………………………………………………………...22
Список литературы………………………………………………………………23
Введение
Алгоритм - это система точных предписаний о содержании и последовательности поставленных конечных и бесконечных задач.
Появилось это слово от латинского ALGORITHMI и от имени среднеазиатского математика Аль-Хорезми. Раньше использовалось в старой трактовке вместо слова порядок, использовалось ПОСЛЕДОВАТЕЛЬНОСТЬ. Но после развития всё же, последовательность заменилось на слово порядок. Кстати, раньше тоже в русском языке писали АЛГОРИФМ вместо АЛГОРИТМ, так писалось из-за происхождения от латинского слова.
Алгоритм так же используются не только в компьютерной сфере, но и в приготовлении блюд, в задачах строительства и в приготовлении разных ресурсов для какой либо работы. Допустим, чтобы сделать бетон, нужно в бетономешалке перемешать цемент, песок и щебень с водой. И по алгоритму 1 ведро цемента, 3 ведра песка, 6 ведра щебня и 5 ведер с водой, добавляем всё в бетономешалку и готово. Бетон сделан.
Актуальность: Тема АЛГОРИТМА сейчас является актуальной темой в современном мире, ведь сейчас современность технологий и развития в этом, причём алгоритм актуальная тема не только в компьютерной сфере, но и в других сферах жизни.
Объект исследования: программа для работы с презентациями Trio Office Writer.
Предмет исследования: объяснение алгоритма и его свойства.
Цель проекта: сделать проект по теме «Средства и языки описания (представления)».
Задачи проекта:
• Собрать информацию из разных источников информации по теме.
• Рассказать о видах алгоритмов и их свойствах.
• Защитить проект.
Практическая
значимость моего проекта заключается в том, что она может быть
использована в школе для учащихся младших классов для лучшего усвоения
информации, а также в качестве интерактивных дидактических материалов.
Разработанные материалы могут быть использованы для организации самостоятельной
работы учеников при выполнении домашней работы.
Глава 1. Теоретическая часть
1.1. Что такое алгоритм?
Алгоритм,
это последовательность выполнение конечных и бесконечных поставленных задач,
приводящих к выполнению последовательных действий.
Так же, алгоритмы используются не только в компьютерных сферах, но и в других
сферах жизни. Как я приводил пример в Введении, мы понимаем что в жизни
алгоритм куда более распространённый чем мы думаем на первый взгляд.
Так же, алгоритм это искусство счёта цифр.
Алгоритм позволяет нам применять последовательность в каких либо действиях, задачах, тем самым, упрощая нам работу. Ведь поставленный алгоритм, т. е. Действия по которым мы будем делать какую либо работу, облегчает нам работу, ибо мы заранее знаем как будет проходить эта работа и в какой последовательности. Таким образом, занимаясь чем либо заранее поставленным алгоритмом, мы не будем теряться в работе и делать всё правильно и без ошибок.
Чаще
всего, алгоритм применяется в математических сферах науки. Именно с математики
пошло понятие алгоритма, потому его понятие относится к базовым основам основ в
понятии математики. Чтобы что-то вычислить, прибавить умножить и т. д.,
нужно следовать определённому алгоритму с помощью которого можно будет решить
тот, или иной пример.
1.2. Происхождение слова АЛГОРИТМ
Произошло слово алгоритм (по латински algorithmi) от среднеазиатского математика Аль-Хорезми. Его слово приобрело понятие такого как, последовательность к конечной цели задачи.
Потому само слово алгоритм происходит от имени персидского (хорезмского и маверннахрского) учёного Аль-Хорезми.
Сам Аль-Хорезми написал сочинение около 825 года Китаб аль-джебр валь-мукабала (книга о сложении и вычитании) которая кстати, не сохранилась до нашего времени.
В этой книге он впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Аль Хорезми сформулировал правила вычислений в новой системы и использовал впервые цифру ноль для обозначения пропущенной позиции в записи числа, как они писали бы её as-sifr или коротко sifr (отсюда как раз таки и появилось слово цифра и шифр). Ближе к этому времени, этим начали пользоваться и другие учёные.
Около 1250 года, английский астроном и математик Иоанн Сакробоско написал труд по арифметике Algorismus vulgaris на столетия ставший основным учебником по вычислениям в десятичной позиционной системе счисления во многих учебных учреждениях. В его введении автором был назван о счёте мудреца Алгус. А в поэме Роман о Розе (1275-1280гг) Жана де Мена греческий философ Алгус, его ставят рядом с Платоном, Аристотелем, Евклидом и Птолемеем.
Вообще, изначально в старой трактовке вместо слова порядок, использовалось слово последовательность. Но из-за временного постоянного развития, последовательность заменилось на слово порядок.
Связанное
изменение с алгоритмом называется как Проблемы разрешения (от немецкого
Entsheidungsproblem) которую сформулировал как раз таки Давид Гильберт в 1928
году. Именно с этого начались последующие этапы формализации для определения
эффективных вычислений или как лучше назвать, эффективного метода. Среди таких
рекурсивные функции
Геделя — Эрбрана — Клини 1930, 1934 и 1935 гг., λ- HYPERLINK "https://ru.wikipedia.org/wiki/Лямбда-исчисление"исчисление Алонзо Чёрча 1936 г., «Формулировка 1» Эмиля Поста 1936 года и машина Тьюринга
Курт HYPERLINK "https://ru.wikipedia.org/wiki/Гёдель,_Курт"Фри́дрих HYPERLINK "https://ru.wikipedia.org/wiki/Гёдель,_Курт" HYPERLINK "https://ru.wikipedia.org/wiki/Гёдель,_Курт"Гёдель HYPERLINK "https://ru.wikipedia.org/wiki/Гёдель,_Курт"— австрийский логик, математик и философ математики. Наиболее HYPERLINK "https://ru.wikipedia.org/wiki/Гёдель,_Курт"известен HYPERLINK "https://ru.wikipedia.org/wiki/Гёдель,_Курт" сформулированными и доказанными им теоремами о неполноте, которые оказали огромное влияние на представление об основаниях мат HYPERLINK "https://ru.wikipedia.org/wiki/Гёдель,_Курт"ематики.
Жак
HYPERLINK "https://ru.wikipedia.org/wiki/Эрбран,_Жак"Эрбран HYPERLINK
"https://ru.wikipedia.org/wiki/Эрбран,_Жак"— французский математик и
логик.
1.3. Виды алгоритмов
Их
существует три вида.
Линейный алгоритм– это алгоритм, в котором действия выполняются однократно и строго последовательно.
Самый простой пример реализации линейного алгоритма – путь из университета домой.
Словесный способ записи данного алгоритма:
• выйти из университета на остановку;
• подождать нужный автобус;
• сесть на нужный автобус;
• оплатить проезд;
• выйти на требуемой остановке;
• дойти до дома.
Очевидно, что данный пример относится к линейному алгоритму, т.к. все действия следуют одно за другим, без условий и повторений.
Разветвляющийся алгоритм– это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
Самый простой пример реализации разветвляющегося алгоритма – если на улице идет дождь, то необходимо взять зонт, иначе не брать зонт с собой.
Приведенный выше пример псевдокода по нахождению частного двух чисел также относится к разветвляющемуся алгоритму.
Для составления разветвляющегося алгоритма необходимо:
• Установить какие могут быть варианты операций и их количество;
•
Количество условных операторов (которые и отражают заданное
условие)
должно быть на одну единицу меньше, чем количество существующих вариантов;
• Понять, при соответствии каким из условий будет реализован каждый их установленных вариантов;
• Если в алгоритме существует больше двух условий, то необходимо задать и последовательность проверки данных условий;
• Записать алгоритм, который отражает ввод данных, вычисление, вывод окончательного результата;
• Протестировать полученный алгоритм на предмет его корректного функционирования.
Циклический алгоритм– это алгоритм, команды которого повторяются некое количество раз подряд.
Самый простой пример реализации циклического алгоритма – при чтении книги будут повторяться одни и те же действия: прочитать страницу, перелистнуть и т. д.
Для составления циклического алгоритма необходимо:
• Установить, какая из последовательностей операций должна быть в основе цикла;
• Определить вводные данные о количестве повторений тела цикла до начала цикла. Исходя из этих данных, определить какой из видов циклического цикла наиболее целесообразно использовать: цикл с параметром, постусловием или предусловием;
• Установить условие окончания выполнения заданного цикла;
• Установить вводные переменные;
• Записать алгоритм, который отражает ввод данных, вычисление, вывод окончательного результата;
• Протестировать полученный алгоритм на предмет его корректного функционирования.
Рис.1
1.4. Способы записи алгоритмов
Существует 4 способа записи алгоритмов.
1.Словесная
- Самой простой является
запись алгоритма в виде набора высказываний на обычном разговорном языке.
Словесное описание имеет минимум ограничений и является наименее
формализованным. Однако все разговорные языки обладают неоднозначностью,
поэтому могут возникнуть различные толкования текста алгоритма, заданного таким
образом. Алгоритм в словесной форме 
может оказаться очень объёмным и трудным для восприятия.
Рис.2
2. Псевдокод- компактный, зачастую неформальный язык описания алгоритмов использующий ключевые слов императивных языков программирования, но опускающий несущественные для понимания алгоритма подробности и специфический синтаксис. Предназначен для представления алгоритма человеку, а не для компьютерной трансляции и последующего исполнения программы.
3. Графическая- Описание алгоритма с помощью блок-схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками.
В блок-схемах всегда есть начало и конец, обозначаемые эллипсами, между ними — последовательность шагов алгоритма, соединенных стрелками
Шаги
бывают безусловными(изображаются прямоугольниками, параллелограммами) и
условными(изображаются ромбами). Из ромба всегда выходят две стрелки - одна
означает дальнейший путь, в случае выполнения условия (обозначается обычно
словом "да" или "+"), другая - невыполнение
(словом "нет" или "-"). Ввод с клавиатуры или вывод на
экран значения выражения изображается параллелограммом. Команда, выполняющая
обработку действий (команда присваивания), изображается в прямоугольнике.
4. Программная -Программный язык записи алгоритмов, это точные команды и коды, записи.
В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения.
Любой алгоритм есть последовательность предписаний, выполнив которые можно за конечное число шагов перейти от исходных данных к результату. В зависимости от степени детализации предписаний обычно определяется уровень языка программирования - чем меньше детализация, тем выше уровень языка.По этому критерию можно выделить следующие уровни языков программирования машинные, машинно-оpиентиpованные (ассемблеpы), машинно-независимые (языки высокого уровня).
Машинные
языки и машинно-ориентированные языки - это языки низкого
уровня, требующие указания мелких деталей процесса обработки данных. Языки же
высокого уровня имитируют естественные языки, используя некоторые слова
разговорного языка и общепринятые математические символы.
Эти языки более удобны для человека.
Языки
высокого уровня делятся на:
алгоритмические (Basic, Pascal, C и др.), которые предназначены для
однозначного описания алгоритмов; логические (Prolog, Lisp и др.), которые
ориентированы не на разработку алгоритма решения задачи, а на систематическое и
формализованное описание задачи с тем, чтобы решение следовало из составленного
описания. объектно-ориентированные (Object Pascal, C++, Java и др.), в основе
которых лежит понятие объекта, сочетающего в себе данные и действия над нами.
Программа на объектно-ориентированном языке, решая некоторую задачу, по сути
описывает часть мира, относящуюся к этой задаче. Описание действительности в
форме системы взаимодействующих объектов естественнее, чем в форме
взаимодействующих процедур.
Рис.3
Рис.4
1.5. Свойства алгоритмов.
Всего свойств алгоритмов 6.
1. Дискретность — алгоритм должен представлять процесс решения задачи как упорядоченное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
2. Детерминированность - (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список исходных данных вероятностный алгоритм становится подвидом обычного.
3. Понятность— алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
4. Завершаемость (конечность)— в более узком понимании алгоритма как математической функции, при правильно заданных начальных данных алгоритм должен завершать работу и выдавать результат за определённое число шагов. Дональд Кнут процедуру, которая удовлетворяет всем свойствам алгоритма, кроме, возможно, конечности, называет методом вычисления. Однако довольно часто определение алгоритма не включает завершаемость за конечное время. В этом случае алгоритм (метод вычисления) определяет частичную функцию. Для вероятностных алгоритмов завершаемость, как правило означает, что алгоритм выдаёт результат с вероятностью 1 для любых правильно заданных начальных данных (то есть может в некоторых случаях не завершиться, но вероятность этого должна быть равна 0).
5. Массовость (универсальность). Алгоритм должен быть применим к разным наборам начальных данных.
6.
Результативность— завершение алгоритма определёнными результатами.
Глава 2. Практическая часть
2.1 Виды алгоритмов
Линейный
Начало →
Команда 1→ Команда 2→ Конец
Разветвляющийся
Начало
↓
Команда 1←Да← Условие→Нет→Команда 2
↓ Конец
Циклический
Начало
↓
←
Команда 1←Да←Условие
↓
↓ ↑
Конец Нет→Команда 1
2.2 Способы описания алгоритмов
Словесное
1. Сравнить a и b. Если a>b,то в качестве максимума t принять a, иначе
(a<=b) в качестве максимума принять b (t=b).
2. Сравнить t и c. Если t>c, то перейти к шагу 3. Иначе (t<c) принять в качестве максимума c (t=c).
3. Принять t в качестве результата.
НЕДОСТАТКИ СЛОВЕСНОГО СПОСОБА :
- отсутствие наглядности;
- недостаточная точность.
ДОСТОИНСТВА : С его помощью можно описать любые алгоритмы, в том числе и вычислительные.
СПЕЦИАЛЬНЫЕ СОГЛАШЕНИЯ ДЛЯ СЛОВЕСНОЙ ЗАПИСИ АЛГОРИТМОВ:
1. Знак присваивания, слева от которого записывают ту переменную, которой присваивается значение, записанное справа от знака присваивания. Например, х:=х+1
2. Для задания значения исходных данных используют указания: ВВЕСТИ
3. Для запоминая промежуточных результата используют вспомогательные переменные.
4. Для указания начала и конца алгоритма используют указания: НАЧАЛО и КОНЕЦ.
5. Все шаги нумеруют.
Пример алгоритма построения треугольника по трём сторонам:
1. Начало.
2. На произвольной прямой выбрать точку А. Раствором циркуля, равным а, отложить отрезок АВ=а.3. Из точки А провести окружность радиуса в.4. Из точки В провести окружность радиуса с.
5. Конец
Рис.5
Графический
1. В блок-схеме можно использовать строго определённые типы блоков.
2. Стрелки на линиях связи можно не ставить при направлении сверху вниз и слева
направо; противоположные направления обязательно указывают стрелкой на линии.
3. Для удобства блоки могут помечаться метками(буквами или цифрами).
4. Внутри блока ввода/вывода пишется ВВОД или ВЫВОД и перечисляются имена данных, подлежащих вводу/выводу.
5. Внутри блока действия для присваивания переменных значений используется знак присваивания.
Пример нахождения максимума трех чисел.
Рис.6
Псевдокод
(Программы)
Пример программы на языке программирования Паскаль:
PROGRAM RR;
VAR A,B,C, max: INTEGER;
BEGIN
WRITE(‘ ВВЕДИТЕ A, B, C');
READLN(A,B,C);
IF A>B THEN max:=A
ELSE max:=B;
IF C>max THEN max:=C;
WRITELN(max);
END.
И это пример только из языка Паскаля. Так же существует несколько других, но
самые распространённые, это Python, Java, c++.
Рис. 6
2.3. Свойства алгоритмов
Дискретность
Алгоритм обладает дискретностью, если его можно разделить на отдельные этапы
(части, команды)
Детерминированность
Алгоритм обладает свойством детерминированности, если для одних и тех же
наборов исходных данных он будет выдавать один и тот же результат
Результативность
Свойство результативности означает, что алгоритм должен выдавать результат за
конечное число шагов
Массовость
Набор исходных данных, на которых алгоритм должен выдавать верное решение,
заранее ограничен
Правильность
Эта программа должна выдавать правильный результат, а не просто результат какой
бы там ни был
Теперь покажем, что конкретный алгоритм обладает этими свойствами на рисунке 7
Приведенный алгоритм проверяет правильность расстановки скобок, если скобки расставлены правильно, то каждой закрывающей скобке предшествует соответствующая открывающая, а каждой открывающей соответствует закрывающая.
Можно сказать, что алгоритм обладает свойством дискретности, так как весь алгоритм разбит на отдельные части
Доказать детерминированность алгоритма, достаточно сложно, например, когда алгоритм содержит части, которые выполняются параллельно, но не будем сейчас на этом останавливаться. Скажем, что в данном случае программа является детерминированной, т.к. не содержит фрагментов, зависящих от времени выполнения, т.е. сколько бы мы не тестировали алгоритм на одной и той же строке результат не изменится.
Чтобы показать результативность
алгоритма, в данном случае достаточно заметить, что любой путь из начальной вершины
в конечную содержит блок вывода результата. Перед блоком «конец» алгоритм
содержит лишь 2 альтернативные ветви, каждая из которых выводит некоторый
результат.
Заключение
В ходе работы над индивидуальным проектом была достигнута поставленная цель, которая заключалась в объяснении что такое Средства и языки описания (представления) алгоритмов и показа на примере.
Для реализации поставленной цели, мною были
достигнуты задачи:
1) При выполнении индивидуального проекта, мной использовался источник
информации интернет.
2) Проанализировали какие наиболее популярные языки программирования и их свойства, описания, возможности и действия.
3) Описали что такое алгоритм в целом и его работу.
Список литературы
1. Структуры данных и алгоритмы - Альфред в Ахо. Джон э
Хопкрофт. Джеффри д Ульман Глава 1.1 подглавие Алгоритмы.
2. Структуры данных и алгоритмы - Альфред в Ахо. Джон э Хопкрофт. Джеффри д
Ульман Глава 1.1 подглавие Псевдоязык и пошаговая кристаллизация алгоритмов
3. Структуры данных и алгоритмы - Альфред в Ахо. Джон э Хопкрофт. Джеффри д
Ульман Глава 1.4 подглавие Измерение времени выполнения программ.
4. Структуры данных и алгоритмы - Альфред в Ахо. Джон э Хопкрофт. Джеффри д
Ульман Глава 1.5 подглавие Вычисление времени выполнение программ.
5. Структуры данных и алгоритмы - Альфред в Ахо. Джон э Хопкрофт. Джеффри д
Ульман глава 1.6 подглавие практика программирования.
6. Структуры данных и алгоритмы - Альфред в Ахо. Джон э Хопкрофт. Джеффри д
Ульман глава 1.7 подглавие Расширение языка Pascal.
7. Структуры данных и алгоритмы - Альфред в Ахо. Джон э Хопкрофт. Джеффри д
Ульман глава 2.1 подглавие Абстрактный тип Данных «Список»
Скачано с www.znanio.ru
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
