Понятие алгоритма и его свойства. Блок-схема алгоритма. Технология Robson

Министерство образования и науки РФ

«Южно-Уральский государственный университет»

Факультет: «Механико-Технологический»

Кафедра: «Технология Машиностроения»

РЕФЕРАТ

по дисциплине «Информатика»

Понятие алгоритма и его свойства. Блок-схема алгоритма. Технология ROBSON

Проверил, (доцент)

Бизяев М.Н.

Автор работы

студент группы МТ-174

Гильманов.И.Р.

Челябинск 2012

АННОТАЦИЯ

Цель: Изучение понятия алгоритм, свойств алгоритма.Технология Robson.

Задача: Изучить алгоритм и его свойства,а также блок-схему алгоритма и технологию Robson.

ОГЛАВЛЕНИЕ

1. РАЗЛИЧНЫЕ ПОДХОДЫ К ПОНЯТИЮ«АЛГОРИТМ»

. ПОНЯТИЕ ИСПОЛНИТЕЛЯ АЛГОРИТМА

. БЛОК - СХЕМА АЛГОРИТМОВ

4. СВОЙСТВА АЛГОРИТМОВ

5. ПОНЯТИЕ АЛГОРИТМИЧЕСКОГО ЯЗЫКА

. ТЕХНОЛОГИЯ ROBSON

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ВВЕДЕНИЕ

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

1. РАЗЛИЧНЫЕ ПОДХОДЫ К ИЗУЧЕНИЮ ПОНЯТИЯ «АЛГОРИТМ»

алгоритм графический блок схема

Понятие алгоритма - одно из фундаментальных понятий информатики. Алгоритмизация наряду с моделированием выступает в качестве общего метода информатики. К реализации определенных алгоритмов сводятся процессы управления в различных системах, что делает понятие алгоритма близким и кибернетике. Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисциплины, примыкающей к математической логике - теории алгоритмов. Особенность положения состоит в том, что при решении практических задач, предполагающих разработку алгоритмов для реализации на ЭВМ, и тем более при использовании на практике информационных технологий, можно, как правило, не опираться на высокую формализацию данного понятия. Поэтому представляется целесообразным познакомиться с алгоритмами и алгоритмизацией на основе содержательного толкования сущности понятия алгоритма и рассмотрения основных его свойств. При таком подходе алгоритмизация более выступает как набор определенных практических приемов, особых специфических навыков рационального мышления в рамках заданных языковых средств. Можно провести аналогию между этим обстоятельством и рассмотренным выше подходом к измерению информации: тонкие математические построения при «кибернетическом» подходе не очень нужны при использовании гораздо более простого «объемного» подхода при практической работе с компьютером. Само слово «алгоритм» происходит от algorithmi - латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами.

2. ПОНЯТИЕ ИСПОЛНИТЕЛЯ АЛГОРИТМА

Понятие исполнителя невозможно определить с помощью какой-либо формализации. Исполнителем может быть человек, группа людей, робот, станок, компьютер, язык программирования и т.д. Важнейшим свойством, характеризующим любого из этих исполнителей, является то, что исполнитель умеет выполнять некоторые команды. Так, исполнитель-человек умеет выполнять такие команды как «встать», «сесть», «включить компьютер» и т.д., а исполнитель-язык программирования Бейсик - команды PRINT, END, LIST и другие аналогичные. Вся совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя (СКИ). Одно из принципиальных обстоятельств состоит в том, что исполнитель не вникает в смысл того, что он делает, но получает необходимый результат. В таком случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции.

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

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

3. БЛОК - СХЕМА АЛГОРИТМА

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

Таблица 1.

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

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

. СВОЙСТВА АЛГОРИТМОВ

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

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

. Используемые на практике алгоритмы составляются с ориентацией на определенного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие - не может. Мы знаем, что у каждого исполнителя имеется своя система команд. Очевидно, составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его СКИ. Это свойство алгоритмов будем называть понятностью.

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

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

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

. ПОНЯТИЕ АЛГОРИТМИЧЕСКОГО ЯЗЫКА

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

Очень часто при составлении алгоритмов возникает необходимость использования в качестве вспомогательного одного и того же алгоритма, который к тому же может быть весьма сложным и громоздким. Было бы нерационально, начиная работу, каждый раз заново составлять и запоминать такой алгоритм для его последующего использования. Поэтому в практике широко используют, так называемые, встроенные (или стандартные) вспомогательные алгоритмы, т.е. такие алгоритмы, которые постоянно имеются в распоряжении исполнителя. Обращение к таким алгоритмам осуществляется так же, как и к «обычным» вспомогательным алгоритмам. У исполнителя-робота встроенным вспомогательным алгоритмом может быть перемещение в склад.

. ТЕХНОЛОГИЯ ROBSON

Для того чтобы быть производительным, компьютер должен быть сбалансирован. То есть, все его составляющие (видеокарта, процессор, память и прочие «запчасти») должны иметь сравнимую скорость работы. Так, например, если в компьютере установлена мощная видеокарта и слабенький процессор, то возможности такого компьютера будут ограничены возможностями процессора. Сегодня узким местом, ограничивающим возможности современных ПК, являются жесткие диски. Можно, конечно же, повысить скорость работы дисковых накопителей организацией RAID-массивов (это, грубо говоря, когда несколько винчестеров, воспринимаются компьютером как один диск). Практически все современные материнские платы имеют один-два встроенных RAID-контроллера. Но, к сожалению, RAID-массивы лишь частично решают проблему производительности дисковой системы. Например, они не способны повлиять принципиальным образом на скорость загрузки операционной системы или каких-либо отдельных приложений. Можно повысить скорость работы самих дисков, и производители винчестеров непрерывно работают над этим. Но проблема состоит в том, что скорость роста производительности дисков явно меньше скорости роста производительности остальных составляющих компьютера. Возможно, одним из вариантов решения проблемы станет использование в качестве дисков флэш-накопителей большой емкости. В 2006 компанией Samsung был представлен ноутбук, в котором был применен накопитель на базе флэш-памяти вместо обычного винчестера. Флэш-память имеет очевидные преимущества: она имеет высокую скорость чтения и записи, достаточно надежна, долговечна, потребляет мало энергии и абсолютно бесшумна. При демонстрационном запуске ноутбук Samsung с флэш-накопителем загружался меньше чем за 20 секунд, а ноутбуку с обычным винчестером потребовалось больше тридцати. Естественно, имея столько плюсов, нельзя не обойтись без минусов. Главным из них является стоимость - использованный в описанном ноутбуке флэш-накопитель емкостью 32 Гбайт стоил больше тысячи долларов. Безусловно, рано или поздно, флэш-память станет дешевле (этот процесс идет уже несколько лет) и флэш-винчестеры, возможно, станут стандартным решением. А пока что корпорация Intel предлагает гибридное решение - технологию Robson.Технология Robson предусматривает использование флэш-памяти в дополнение к жесткому диску ноутбука. В этой памяти предполагается хранить часто используемые данные. Фактически, она представляет собой буфер между винчестером и оперативной памятью.

Основное достоинство технологии Robson заключается в том, что она позволяет ускорить загрузку системы и приложений, не поднимая стоимость компьютера до заоблачных высот. Помимо этого, обеспечивается экономия энергии за счет уменьшения количества обращений к винчестеру и использования флэш-памяти, потребляющей незначительное количество энергии. В результате время работы ноутбука от аккумулятора значительно возрастает. Первые сведения о технологии Robson были представлены в марте 2006 года. Разработка тут же привлекла внимание разработчиков аппаратного и программного обеспечения. Например, компания Microsoft заявила о намерении ориентировать свою новую операционную систему Windows Vista на технологию Robson, что позволит сократить время загрузки системы.

Обычные (не мобильные) компьютеры тоже не избежали внимания компании Intel. Для ПК разрабатывается схожая технология, получившая название Snowgrass. Правда пока что какого-либо окончательного описания или спецификации данной технологии нет, и говорить определенно о том, как это будет реализовано, не приходится. Возможно, на материнских платах будет разъем для дополнительных флэш-карт, а может быть производители станут производить материнские платы со встроенными флэш-накопителями. Как говорится, будущее покажет.

ЗАКЛЮЧЕНИЕ

Опыт парадоксов теории множеств научил математику крайне осторожно обращаться с бесконечностью и даже о бесконечности рассуждать с помощью финитных методов. Существо финитного подхода заключается в том, что он допускает только конечные комплексы действий над конечным числом объектов. Выяснение того, какие объекты и действия над ними следует считать точно определенными, какими свойствами и возможностями обладают комбинации элементарных действий, что можно и чего нельзя сделать с их помощью - все это стало предметом теории алгоритмов. Главным внутриматематическим приложением теории алгоритмов явились доказательства невозможности алгоритмического решения некоторых математических проблем. Такие доказательства неосуществимы без точного понятия алгоритма (для доказательства несуществования алгоритма решения того или иного класса задач, надо точно знать несуществование чего требуется доказать).

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1.Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: «Вильямс», 2006. - С. 1296. - ISBN 0-07-013151-1

.Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. - 3-е изд. - М.: «Вильямс», 2006. - С. 720. - ISBN 0-201-89683-4

.Порублев Илья Николаевич, Ставровский Андрей Борисович. Алгоритмы и программы. Решение олимпиадных задач. - М.: «Вильямс», 2007. - С. 480. - ISBN 978-5-8459-1244-2

.Игошин В. И. Математическая логика и теория алгоритмов. - 2-е изд., стер. - М.: ИЦ «Академия», 2008. - 448 с. - ISBN 5-7695-1363-2

Больше работ по теме: