25127

Понятие алгоритма

Доклад

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

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

Русский

2013-08-12

40.5 KB

1 чел.

4   Понятие алгоритма.

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

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

Интуитивное понятие алгоритма

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

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

В информатике под АЛГОРИТМОМ понимают понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи.   

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

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

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

Всякий алгоритм обладает 7 характеристиками или параметрами:

  1.  Совокупность всевозможных исходных данных;
  2.  Совокупность возможных результатов;
  3.  Совокупность возможных промежуточных результатов;
  4.  Правило начала;
  5.  Правило непосредственной переработки;
  6.  Правило окончания;
  7.  Правило извлечения результата.

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

Основные требования к алгоритмам

  1.  Любой алгоритм применяется к исходным данным и выдаёт результаты. Кроме того, в ходе работы алгоритма появляются промежуточные результаты, которые используются в дальнейшем. Таким образом, каждый алгоритм имеет дело с данными – входными, промежуточными и выходными. Данные – это объекты, которые чётко определены и отличимы от других данных и от «необъектов». К ним относятся числа, векторы, формулы.
  2.  Данные для своего размещения требуют памяти. Память обычно считается однородной и дискретной, каждая ячейка памяти может содержать один символ алфавита данных. Т.о., единицы измерения объёма данных и памяти согласованы.
  3.  Следует различать: а) описание алгоритма (инструкцию или программу); б) механизм реализации (ЭВМ); в) процесс реализации алгоритма.

Критерии качества алгоритма

  1.  Связанность. Определяется количеством промежуточных результатов.  Чем выше количество промежуточных результатов, тем ниже связанность.
  2.  Объем алгоритма.  Это количество операций или шагов, которые необходимо выполнить, а также сложность этих шагов.
  3.  Логическая сложность. Определяется количеством ветвлений и циклов.


 

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

42327. Ограничения целостности. SQL-операторы для работы с ограничениями 124.5 KB
  Ограничения целостности Цель работы Изучить используемые в Firebird типы ограничений целостности. Изучить SQLоператоры для работы с ограничениями. Теоретические сведения Ограничения целостности данных представляют собой такие ограничения которые вводятся с целью предотвратить помещение в базу противоречивых данных. Ограничения внешнего ключа Foreign keys ссылочная целостность.
42328. Триггеры, генераторы, исключения 133 KB
  Студент получает индивидуальный вариант исходных данных с кратким описанием предметной области, который используется при выполнении всех лабораторных работ. При этом каждая очередная лабораторная работа является продолжением выполненной ранее и поэтому они должны обязательно выполняться последовательно. Варианты заданий к лабораторной работе №5 № варианта Имя пользователя Имя файла БД Имя таблицы Бизнес-правило для поля 1 TEM001 SLRY.FDB Цех Дата_поступления 2 TEM002 STUFF.FDB Собрано День_недели 3 TEM003 STUFFPLUS.FDB Изделия Наименование 4 TEM004 TELEPHONE.
42329. Внесение изменений в базу данных 96 KB
  Внесение изменений в базу данных Цель работы Изучить используемые в реляционных СУБД операторы изменения данных. Заполнить таблицы разрабатываемой базы данных тестовыми данными для последующего использования. Исходные данные Студент получает индивидуальный вариант исходных данных с кратким описанием предметной области который используется при выполнении всех лабораторных работ. Теоретические сведения В SQL имеется три оператора относящиеся к группе операторов DML Dt Mnipultion Lnguge которые предназначены для выполнения запросов...
42330. Выборка данных 173.5 KB
  Изучить используемый в реляционных СУБД оператор извлечения данных из таблиц. Получить навыки работы с оператором SELECT в программе "IBExpert". SELECT [DISTINCT LL] { величина [ величина ]} [INTO :Переменная [ :Переменная ]] FROM tbleref [ tbleref ] [WHERE условие поиска ] [GROUP BY Колонка [ Колонка ]] [HVING условие поиска ] [UNION [LL] select_expr ] [ORDER BY список сортировки ]; величина = {Колонка :Переменная константа выражение функция udf [ величина [ величина ]] NULL USER} [S Псевдоним] константа = Число 'Строка' выражение = SQL выражение возвращающее единичное значение функция = COUNT [LL] величина DISTINCT величина SUM [LL] величина ...
42331. Хранимые процедуры (Procedures) 113.5 KB
  Хранимые процедуры Цель работы Изучить виды используемых в Firebird хранимых процедур. Теоретические сведения Хранимые процедуры Procedures Хранимая процедура – это откомпилированная во внутреннее представление сервера СУБД подпрограмма хранящаяся в базе данных. Хранимые процедуры пишутся на специальном языке хранимых процедур и триггеров в котором имеются операторы присваивания ветвлений и циклов и в которых можно использовать операторы SQL такие как INSERT DELETE UPDTE и SELECT. Хранимые процедуры позволяют переносить часть...
42332. Разработка концептуальной модели базы данных 233 KB
  Добавьте следующие элементы в структуру данных сущности FIRMS: Имя атрибута Назначение ID Идентификатор партнера Nme Наименование партнера ddress Адрес City Город Phone Телефоны EMil Адрес электронной почты Person Контактное лицо FinDelt Финансовое сальдо ChngDelt Обменное сальдо Coeff Коэффициент скидки наценки RetDys Количество дней для возврата В структуру данных сущности BOOKS добавьте следующие элементы: Имя атрибута Назначение ID Идентификатор книги Nme Название книги uthor Авторы Publish Издательство Yer Год выпуска Pges Количество...
42333. Разработка реляционной модели базы данных 232 KB
  Разработка реляционной модели базы данных Цель работы Изучить виды моделей данных. Получить навыки разработки реляционной модели данных с помощью CSEсредства Open ModelSphere. Теоретические сведения Что такое реляционная модель данных Реляционная логическая модель данных это модель данных логического уровня для реляционной СУБД но не привязанная ни к какой конкретной СУБД. Перед созданием реляционной модели данных необходимо изучить такие понятия этоой модели данных как таблицы столбцы; первичные потенциальные и внешние ключи;...
42334. Технология программирования Active Server Pages 91.5 KB
  По расширению файла . Функции и выражения для работы с файлами При осуществлении открытия фала в одном из режимов мы будем работать с объектом типа FileSystemObject который обладает всеми необходимыми методами для работы с фалами. В нашем случае с её помощью мы будем создавать объект типа FileSystemObject и использовать его для работы с файлами.FileSystemObject с именем objFSO OpenTextFile Это метод возможно использовать для открытия файла и получения его файлового дескриптора.
42335. Переход в РНР 137.5 KB
  Стандартные теги Стандартные теги используются программистами РНР чаще остальных способов что объясняется наглядностью и удобством этой формы записи: php print Welcome to the world of PHP ; У стандартных тегов есть еще одно дополнительное преимущество: за открывающей конструкцией следуют символы php однозначно определяющие тип дальнейшего кода. Короткие теги Короткие теги обеспечивают наиболее компактную запись для перехода в РНР: print Welcome to the world of PHP ; По умолчанию короткие теги не используются их нужно...