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.  Логическая сложность. Определяется количеством ветвлений и циклов.


 

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

20662. Философское учение Платона 70.5 KB
  Платон настоящее имя Аристокл Платон от греческого platys – широкоплечий полный 427 – 347 год до н. Платон был основателем собственной философской школы занятия слушателей которой проходили в роще посвящённой античному герою Академу что непосредственно повлияло на её название Академия. Философская Академия Платона просуществовала 915 лет.
20663. Философия Аристотеля, Критика платоновского учения об идеях 72.5 KB
  Аристотель 384 – 322 год до н. Аристотель проучившись в платоновской академии 20 лет вплоть до смерти Платона развивал философские положения своего учителя придерживаясь объективного идеализма и смог привнести в это течение новые неоспоримо значимые идеи. Аристотель предпочитал проводить занятия со своими учениками прогуливаясь по саду вблизи школы. Для обозначения философской школы Аристотеля используется и такое название как перипатетика от греческого peripatio – крытая галерея занятия Аристотель проводил не только прогуливаясь...
20664. Философские школы поздней античности (эллинистическая эпоха) 186.5 KB
  Если ранее у греков существовало представление о своём духовном превосходстве над варварами не способных к культуре и к свободной деятельности что запечатлевалось даже в работах Платона и Аристотеля то в новую эпоху взаимовлияния культур формируется представление о едином бытие человека. Под влиянием восточных культур например астрологических и мистических течений Вавилона происходит эклектическое соединение рационального и сверхъестественного в понимание мира что пагубно отражается и на морали где вера в судьбу в определённость...
20665. Специфика философской мысли в эпоху средневековья 76 KB
  Этот период патристика сталкивается с внутренним противоречием которое выражено в том что стремление посредством рациональной аргументации доказать бытие Бога бессмертие души и прочих сакральных компонентов христианской догматики идёт в разрез с краеугольным положением религии о непостижимости при помощи разума божественных таинств доступных только исключительно в вере. Обсуждаются проблемы: а тринитальный вопрос о единстве и троичности Бога; б христологический вопрос о сочетание в Христе двух начал природного и божественного; в...
20666. Характерные черты эпохи Возрождения 77.5 KB
  Разум в силу своей конечности и определённости пропорцией не является истиной и не способен её постигать настоль точно чтобы утверждать о её исчерпанности. Отсутствие пропорциональности которую мы способны зафиксировать только в конечных вещах является причиной нашего незнания. Конечность нашего ума является источником диспропорции между разумом и бесконечностью в которую он включён и которую стремиться познать. На общем онтологическом уровне индивид связывает все вещи и поэтому является микрокосмом любой вещи.
20667. Учение о субстанции в философии Бенедикта Спинозы и Готфильда Лейбница 51 KB
  Таким образом для Спинозы субстанция является causa sui причиной самой себя. Движение по мнению Спинозы относится лишь к миру модусов и не является атрибутом субстанции по той причине что для его осуществления необходима внешняя причина воздействие связи которая может существовать только в природе порождаемой. По его мнению абсолютно свободен лишь Бог так как является вселенским порядком и субстанцией вбирает в себя и определяет все природные причинноследственные связи необходимость. И так как в мире вещей господствует...
20668. Английский материализм и эмпиризм 17-18 века 64.5 KB
  Согласно Гоббсу каждый из нас стремиться рассуждать о какихнибудь вещах поэтому желание философствовать это врождённое состояние человека свойственное ему от природы. Гоббс таким образом показывает прямую зависимость мышления человека от материального мира и его эмпирического восприятия. Философия природы занимается естественными телами в том числе и изучением тела человека. Данный тип философии направлена на трактовку умственных и нравственных способностей человека этика и определение обязанностей гражданина политика.
20669. Философия французского просвещения. Характерные черты эпохи Просвещения 58 KB
  Главным положением данной эпохи становится указание на первостепенное значение разума рассудка для деятельности человека что например было запечатлено в таких высказываниях как Имей мужество пользоваться своим умом или Дерзай быть мудрым Sapere ande. Вера в человеческий разум выразилась в убеждении о решающей роли естественнонаучных знаний; в стремлении освободиться от предрассудков слепой религиозности невежества неопределённых метафизических догм неподдающихся научной проверке; в пересмотре интеллектуальных ценностей...
20670. Критическая философия Иммануила Канта. Философская система Г.В.Ф. Гегеля 58 KB
  Основы метафизики которая понимается Кантом как наука о принципах чистого разума. Само чувственное познание интуитивно поскольку непосредственно общается с объектом без посредничества разума рассудка. после двенадцати лет философских исследований работы Критика чистого разума. Наиболее значимыми произведениями этого этапа становятся также Критика практического разума и Критика способности суждения.