34645

Понятие алгоритма. Свойства, способы описания

Реферат

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

Понятие алгоритма и способы его описания; Типы алгоритмов; Блоксхемы; Базовые структуры применяемые при создании алгоритмов. Иначе говоря блоксхема служит для графического изображения структуры алгоритма. Последовательность действий в соответствии с блоксхемой указывается с помощью стрелок соединяющих отдельные блоки и показывающих какой блок и вслед за каким должен выполняться. В ходе изучения данной дисциплины будут рассматриваться алгоритмы описанные при помощи языка программирования и при помощи специальных схем...

Русский

2013-09-08

90 KB

109 чел.

исциплина «Основы алгоритмизации и программирование»  Понятие алгоритма. Свойства, способы описания.

Понятие алгоритма. Свойства, способы описания.

  1.  Понятие алгоритма и способы его описания;
  2.  Типы алгоритмов;
  3.  Блок-схемы;
  4.  Базовые структуры, применяемые при создании алгоритмов.

1. Понятие алгоритма и способы его описания

Одним из основных данной дисциплины является понятие алгоритма. В основе каждой программы заложен свой алгоритм.

Но алгоритм  встречается во многих областях деятельности человека.

Пример: Кулинарная книга,  аэробика, как найти дорогу.   

Алгоритм это конечная последовательность команд исполнителю, направленная на достижение определенной цели.

Цель это достижение желаемого результата.

Исполнителем может быть человек, живое существо, автоматическое устройство которое способно к восприятию и исполнению команд.  

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

Каждый  алгоритм предназначен для определенного исполнителя.

Исполнять алгоритм начинают с первой команды. После ее исполнения переходят ко второй и так далее до конца.

Способы описания алгоритмов могут быть различными. Перечислим основные:

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

Алгоритмический язык — формальный язык, предназначенный для записи алгоритмов. Алгоритмический язык задается набором основных символов (алфавитом), системой точных правил построения текстов (синтаксисом) и соответствием синтаксически допустимых текстов языка описываемым объектам и действиям (семантикой). Многие языки программирования, используемые при решении задач на ЭВМ, являются алгоритмическими языками.

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

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

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

Алгоритм должен отвечать определенным требованиям. Принято выделять следующие семь условий:

1) наличие ввода исходных данных;

2) наличие вывода результата выполнения;

3) однозначность — компьютер «понимает» только однозначные инструкции;

4) общность — алгоритм предназначен для решения не одной задачи, а целого класса задач;

5) корректность — алгоритм должен давать правильное решение задачи;

6) конечность — решение задачи должно быть получено за конечное число шагов;

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

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

Существует ряд мер, которые рекомендуют для повышения эффективности.

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

2. Блок-схемы

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

Начало и конец алгоритма.

 

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

Операторный блок(блок действия)

(открыть зонт)

Блок проверки условия. Этот блок предполагает два варианта дальнейшего выполнения алгоритма, в зависимости от того, выполнено ли поставленное условие. Если место в маршрутке есть то я еду домой, если нет, то жду следующую.

Блок ввода или вывода.

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

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

3. Типы алгоритмов

Линейный алгоритм.

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

Набрать 8,

дождаться гудка,

набрать код,

набрать номер телефона.

Разветвляющиеся алгоритмы.

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

1. Проверить условие «Идет дождь» Если условие выполняется перейти к команде 2. Если нет то к команде 3.

2. Взять с собой зонт

3. Оставить зонт на месте.

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

Циклические алгоритмы

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

Например Красить дощечки забора до тех пор пока он не будет покрашен.  Способ организации таких алгоритмов называется повторением.

Повторение – это набор команд, который выполняется до тех пор, пока выполняется некоторое условие.

Алгоритмы, содержащие команду повторения, -  циклические алгоритмы (алг.   с повторениями). 

Красить дощечки – тело цикла.

Пока забор не покрашен, повторять – команда цикла.


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

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

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

Конструкция сочленения соответствует линейному алгоритму. Каждая из операций  S1, S2, ..., Sn может быть представлена как последовательность

конечного числа более простых операций.

Конструкция выбора соответствует разветвляющемуся алгоритму. Она полезна в тех случаях, когда некая операция состоит в выборе одной из двух более простых операций S1 или S2 по условию. Блок  B определяет условие выбора.

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

    Переменная - это область оперативной памяти, занимающая несколько ячеек и имеющая свое имя. Переменная обладает следующими свойствами:

  1.  переменная хранит не более 1 значения;
  2.  переменная способна хранить значения только одного и того же типа;
  3.  переменная хранит значение до тех пор, пока в нее не поместят новое значение, при этом предыдущее содержимое переменной стирается;
  4.  значение переменной может быть вызвано для использования сколько угодно раз без изменения оригинала;
  5.  к началу выполнения программы содержимое переменной считается неопределенным; ячейки памяти, отведенные под переменную путем ее описания, заполняются значениями в ходе выполнения программы с помощью оператора присваивания; этим переменная отличается от константы, которой значение присваивается до выполнения основной программы, в разделе определения констант.

Рассмотрим пример разработки программы с применением метода пошаговой детализации. Задача: Составить программу определения максимального из трёх чисел входа. Сразу же можно предложить следующую абстрактную программу решения поставленной задачи:

Эта программа содержит абстрактную операцию max(a,b,c). В этой связи выполним следующую детализацию блока 2:

  •  

Очевидно, что блоки 2.2 и 2.3 нуждается в дальнейшей детализации:

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

Примечание: Существует и другой вариант детализации блока 2.

После детализации блоков 2.1 и 2.2 нового варианта детализации блока 2 и соответствующей сборки мы получим ещё один вариант программы:


Домашнее задание:

Составить блок-схемы для решения следующих задач:

1. Ввести сторону квадрата. Найти и вывести его площадь и периметр.

2. Дано вещественное число А. Не пользуясь никакими арифметическими операциями, кроме умножения, получить:

  1) А^6 за три операции;

  2) А^7 за четыре операции;

  3) А^8 за три операции;

  4) А^9 за четыре операции;

  5) А^13 за пять операции;

3. Поменять местами содержимое двух переменных

4. Дано трехзначное число. Найти число, полученное при прочтении его цифр справа налево.

  •  Дано трехзначное число. Найти сумму его цифр;
  •  Дано трехзначное число. Найти произведение его цифр;


 

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

27416. Проектирование/моделирование, организация и методика проведения интегрированных уроков в процессе обучения искусству 36 KB
  Уроки художественноэстетического цикла должны создавать условия для формирования и развития художественной культуры обучающихся. На протяжении работы в школе в качестве учителя изобразительного искусства хотелось сделать уроки искусства более эмоциональными запоминающимися и плодотворными а главное заинтересовать обучающихся вызвать желание творить. Проникновение современных технологий в образовательную практику в том числе и в уроки искусства открывает новые возможности и перспективы. Интегрированные уроки изобразительного искусства и...
27417. Понятие открытого образовательного пространства как пространства субъектного действия. Модульная система оргформ порождения и становления образовательного пространства в области художественного образования 48.5 KB
  Когда мы говорим о пространстве образования то имеем в виду пространство где формируется образ человека его внутренняя форма. Фомина рассматривает образовательное пространство района как систему управления развитием личности. Автор отмечает что образовательное пространство формируется с помощью целого комплекса направлений деятельности. Под образовательным пространством мы понимаем пространственновременное поле функционирования и развития системы образования как открытой и активной социальной сферы в которой действует своя идеология...
27418. Методика обучения основам синтетических видов искусства (9ый класс). Синтетические искусства и изображение (театр, кино, видео, компьютерные экранные технологии, анимация) 60 KB
  Методика обучения основам синтетических видов искусства 9ый класс. Синтетические искусства и изображение театр кино видео компьютерные экранные технологии анимация. Общая характеристика учебного предмета9 клаcc Этот тематический блок представляет собой расширение курса визуальнопластических искусств и осознание их прочной связи с синтетическими искусствами кино телевидение и др. Именно синтетические искусства непосредственно происходящие от изобразительных являются сегодня господствующими во всей системе видеокультуры.
27419. Народная художественная культура национальные, этнические формы искусства. Методы и формы приобщения учащихся к многообразию культурного наследия, к региональным (местным) национальным культурам и искусству на уроках ИЗО и во внеклассной работе 46.5 KB
  Виды и формы ДПИ. Методика обучения основам ДПИ в школе и формах дополнительного образования. ДПИ невозможно без художественного творчества так же как невозможно и без ремесленных основ владения технологией обработки тех или иных материалов. Методика преподавания ДПИ основанного на традиционной народной культуре сравнительно молодой раздел методики преподавания образовательной области Технология .
27420. Особенности методики преподавания искусства в детских художественных школах и школах искусств. Технологии преподавания рисунка, живописи, композиции, скульптуры, ДПИ, истории искусств 89 KB
  первый этап обучения в общеобразовательной школе должен через искусство заложить основы художественного эстетического восприятия явлений окружающей действительности. За четыре года начального обучения необходимо в сознании и эмоциональном развитии ребенка создать фундамент художественных представлений на которые он сможет опираться во всем дальнейшем обучении. Педагог должен с самого начала обучения создавать вокруг темы урока ситуацию уподобления т. ЦЕЛИ:Единство воспитания и образования обучения и творческой деятельности учащихся...
27421. Проектирование, моделирование, исследование и творчество – ведущие способы эффективной деятельности учителя и учащихся 45.5 KB
  Проектирование моделирование исследование и творчество ведущие способы эффективной деятельности учителя и учащихся. Он формирует опыт деятельности поэтому незаменим. Философия цели и деятельности.Обратите внимание предполагает ли решение проблемы различные виды деятельности изготовление предметов рисунки аппликации записи на плёнку интервью короткую пьесу и.
27422. Методика организации и проведения педагогического эксперимента в области художественного образования/эстетического воспитания и обучения искусству 81.5 KB
  Так имеются методы дидактического воспитательного частнометодического управленческого лабораторного и естественного ограниченного и массового качественного и количественного экспериментов и т. К методам педагогического эксперимента примыкают и взаимопроникают методы психологического физиологического медицинского социологического экономического и других исследований.Внутри эксперимента понимаемого как комплексный метод исследования используются теоретические методы: анализ и синтез индукция и дедукция сравнение аналогия...
27423. Методика обучения конструктивным видам искусства: архитектура и дизайн в жизни человека (8 класс). Интегрированный подход 52.5 KB
  Методика обучения конструктивным видам искусства: архитектура и дизайн в жизни человека 8 класс. Язык этого вида искусства всегда строился и строится на организации пространства здания города села парка и проживания в нём человека. но возникновение этого вида искусства прочно связано с промышленностью с расцветом индустриального производства. Выход за рамки одного искусства одного предмета.
27424. История художественного образования.Обучение искусству в древних цивилизациях:Др.Египет, др.Греция, Античный Рим 48 KB
  Общеобразовательная система художественного образования строилось на обучении рисунку так как написание иероглифов требовало определенных навыков. Система образования имела строгие требования к дисциплине. Система художественного образования в Древней Греции.