Редакционно-издательским советом Томского политехнического университета Издательство Томского политехнического университета 2011 ббк 32. 973. 2я73

Вид материала

Документы

Содержание 3.3. Понятие алгоритма, свойства алгоритмов Достоинства псевдокода Основные свойства Правильность алгоритмов Простейшие виды

Подобный материал:

• Редакционно-издательским советом Томского политехнического университета Издательство, 1488.99kb.
• Редакционно-издательским советом Томского политехнического университета Издательство, 1434.78kb.
• Редакционно-издательским советом Томского политехнического университета Издательство, 3189.24kb.
• Редакционно-издательским советом Томского политехнического университета Издательство, 2424.52kb.
• Конспект лекций Рекомендовано в качестве учебного пособия Редакционно-издательским, 1023.31kb.
• Учебное пособие подготовлено на кафедре философии Томского политехнического университета, 1526.78kb.
• Я управления рисками в организации рекомендовано в качестве учебного пособия Редакционно-издательским, 1160.94kb.
• Рекомендовано в качестве конспекта лекций Редакционно-издательским советом Томского, 1088.59kb.
• Методические указания для преподавателей Издательство Томского политехнического университета, 882.32kb.
• Учебное пособие Рекомендовано в качестве учебного пособия Редакционно-издательским, 2331.42kb.

3.3. Понятие алгоритма, свойства алгоритмов

Алгоритм относится к фундаментальным понятиям информатики. На понятии алгоритма построено все основные принципы программирования – составления программ для вычислительных машин.

Алгоритм – это совокупность действий со строго определенными правилами выполнения. В информатике изучаются различного рода алгоритмы – диалоговые алгоритмы, алгоритмы обработки данных, вычислительные алгоритмы, алгоритмы управления роботами, станками и другими техническими устройствами [1].

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

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

Алгоритм, приведенный слева, записан на псевдокоде. Псевдокод – это язык записи структурированных алгоритмов в качестве докумен­тации к программам для ЭВМ. Особенность псевдокода заключается в том, что описания на нем выполняются на родном языке – русском, английском, украинском, казахском, немецком и т.п.

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

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

Основные свойства алгоритмов и программ для вычислительных машин следующие [12]:

1) однозначность;

2) результативность;

3) правильность;

4) массо­вость;

5) определённость;

6) дискретность.

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

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

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

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

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

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

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

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

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

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

Простейшие виды машинных операций – операции присваивания. С помощью присваиваний в алгоритмах описываются вычисления в программах для ЭВМ.

Компиляторы и интерпретаторы

С помощью языка программирования создается текст, описывающий ранее составленный алгоритм. Чтобы получить работающую программу, надо этот текст перевести в последовательность команд процессора, что выполняется при помощи специальных программ, которые называются трансляторами. Трансляторы бывают двух видов: компиляторы и интерпретаторы.

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

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