Условные графические обозначения в схемах алгоритмов

Инструкционная карта для обучающегося

Тема 2.1 Алгоритмы

Формализация понятия алгоритма. Машина Тьюринга. Машина Поста. Примеры задач выполнения алгоритма. Алгоритм. Виды. Свойства алгоритма. Сохранение и использование промежуточных результатов. Представление о структурах данных.

Лабораторная работа № 20. Построение блок-схем, выполнение готовых алгоритмов.

1. Посмотрите видео

2. Изучите материал лекции

3. Напишите конспект

4. Выполните лабораторную работу № 20. Построение блок-схем, выполнение готовых алгоритмов.

5. Сфотографируйте конспект и лабораторную работу (2 странице на фото и пришлите на почту)

6. Прислать до 14.04.2020 до 14:00 на электронную почту BaranovaOB2021@gmail.com

АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ

ПОСМОТРИТЕ ВИДЕО

1) Машина Поста (6мин.) https://www.youtube.com/watch?v=Yx9MlTleUio

2) Машина Тьюринга в двух словах (3мин 33сек)

https://www.youtube.com/watch?v=Fo7Q4cKkbLs

3) Способы записи алгоритмов (13 мин 30 сек)

https://www.youtube.com/watch?time_continue=735&v=0SDWiVLF7ic&feature=emb_logo

КОНСПЕКТ ЗАНЯТИЯ

Формализация понятия алгоритма. Теория алгоритмов

ПРОЧИТАТЬ

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

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

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

История конечных автоматов: машина Поста и машина Тьюринга. Машина Поста – абстрактная вычислительная машина, предложенная Постом, которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

ПЕРЕПИСАТЬ В ТЕТРАДЬ

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

Алгоритм это фундаментальное понятие

Свойства алгоритма

· Однозначность – понимают единственность толкования правил выполнения действий и порядка их выполнения.

· Понятность – указания, которые понятны исполнителю

· Массовость – подразумевают возможность применения для целого класса задач

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

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

· Результативность – завершение работы за конечное число шагов.

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

· Правильность – в итоге выдавались правильные результаты для решения поставленных задач

ПРОЧИТАТЬ

Для задания алгоритма необходимо описать следующие его элементы:

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

• правило начала;

• правило непосредственной переработки информации (описание последовательности действий);

• правило окончания;

• правило извлечения результатов.

Алгоритм всегда рассчитан на конкретного исполнителя. В нашем случае таким исполнителем является компьютер. Для обеспечения возможности реализации на компьютере алгоритм должен быть описан на языке программирования.

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

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

ПЕРЕПИСАТЬ В ТЕТРАДЬ

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

1) словесный; 2) графический (блок-схемы); 3) псевдокоды;

4) язык программирования (программный).

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

Впервые о блок-схемах заговорили в 1956г. Ляпунов А.А., и Янов Ю.Н.

Условные графические обозначения в схемах алгоритмов

1. Пуск - остановка		Начало, конец алгоритма
2. Процесс		Вычислительные действия
3. Ввод - вывод		Ввод, вывод в общем виде
4. Решение		Проверка условий
5. Модификация		Начало цикла
6. Предопределенный процесс		Программа, стандартная подпрограмма
7. Соединители		Разрыв линий потока на странице, на разных страницах

Алгоритмы подразделяются на:

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

ПЕРЕПИСАТЬ ПРОЧИТАТЬ

2) Алгоритмы ветвления. В разветвляющихся алгоритмах выбор направления продолжения вычисления осуществляется по итогам проверки заданного условия.

ПЕРЕПИСАТЬ ПРОЧИТАТЬ

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

ПРОЧИТАТЬ ПРОЧИТАТЬ

ПЕРЕПИСАТЬ

ПРОЧИТАТЬ

ПЕРЕПИСАТЬ

Вспомогательный (подчиненный) алгоритм (процедура) – алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.

ПРОЧИТАТЬ

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

Рассмотрим пример, Вы хотите спеть песню, у которой три куплета и припев, исполняемый после каждого куплета. Алгоритм Ваших действий будет следующим:
1. Спеть 1-й куплет.
2. Спеть припев.
3. Спеть 2-й куплет.
4. Спеть припев.
5. Спеть 3-й куплет.
6. Спеть припев.
Действия, объединенные в пункт "спеть припев", трижды повторяются. Таким образом, этот алгоритм содержит набор повторяющихся одинаковых действий и возникает необходимость многократного использования одного и того же набора действий (алгоритма), следовательно такой набор действий или алгоритм можно выделить в качестве самостоятельного фрагмента. Он становится вспомогательным алгоритмом.

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

ПРОЧИТАТЬ

№1. Составить блок схему для рисования узора с использованием подпрограммы.

Определяем блок элементов, которые повторяются и описываем один блок в «Замок» (Сокращаем написание «1шаг вправо» 1ш и так далее)