Диссертация (1148854), страница 8
Текст из файла (страница 8)
Развитие и совершенствованиевычислительной техники приводит к необходимости не просто оперироватьданными, но и принять требование, чтобы используемые алгоритмы были бымаксимально экономичными, так как количество ресурсов, что они используют,превышает технические возможности некоторых вычислительных машин. Таким39образом, теория алгоритмов изучает не только вычленение и определениеалгоритмов, но и возможность, их максимально эффективного применения. Тутмы опять возвращаемся к вопросам языка, поскольку теперь возникает ситуациякоммуникации не только между людьми, но и между человеком и машиной, атакже машиной и машиной. Особым исполнителем в данном примере возьмемкомпьютер, для которого создавались специальные средства для интерпретации –языки программирования. Они действуют только на уровне структурированныхданных и правил, а именно - алгоритмов, здесь недопустимы неоднозначности.Именноблагодаряэтойстрогойформеязыкаисталовозможнымкоммуницирование с техникой.Предоставляемый людям объем информации повлиял также на развитиематематики и информатики, а именно - на теорию алгоритмов.
Исследованиематематикикакнаукиовыявленииопределенныхвеличинипостроениипространственных фигур, был основополагающим уже много сотен лет. Согласнополученным результатам, конкретная величина может быть выражена в рамкаходной системы измерения в виде числа (от единицы), а, следовательно, наиболееважной частью было именно исследование взаимодействий между подобнымичислами.
Пространственные фигуры тоже очень долгое время развивались тольков сторонуопределения их метрических свойств.Такой угол рассмотрения был характерен для математики со временантичности (Пифагор, Архимед, Евклид) вплоть до XVIII века. В это самое времяглавным объектом изучения математики служили величины (переменные), а ещебольше функциональная связь между ними. В XIX веке, с появлением вматематике все более абстрактных понятий и теорий, остро встал вопрос об ихобосновании (теория множеств, математические парадоксы, теория типов имножество других проектов). Стало ясно, что проверка математическихположений практическими методами естественных наук или сильно затруднена,или невозможна вовсе.
Обоснование математики приняло форму доказательстванепротиворечивости математических теорий. Начался критический пересмотр40теорий: от системы аксиом, лежащих в их основе, до правил доказательств иконечных выводов.46Таким образом, появилась необходимость в философском осмысленииматематических проблем. Философские проблемы математики способствуютлучшему пониманию математического знания, его специфики, а также природы иметодов, которые оно использует.
Основные вопросы философии математикикасались осмысления сущности, природы и методов математического мышления,специфики математического знания, отношения понятий и объектов математики креальности, соотношения логики и математики, природы математическогодоказательства, соотношения между чистой и прикладной математикой, сущностиматематической бесконечности и так далее.
Ответы на эти вопросы такженеоднозначны и значительно изменялись со временем, создавая различныефилософские течения.В то же время, глубокому изучению и осмыслению подверглось и понятие«алгоритм». Главным образом это произошло в связи с проблемой понимания егосущностииалгоритмическойнеразрешимостивконтекстеимеющейсяматематической модели.
Дело в том, что попытки решить ряд задач натолкнулисьна трудности, которые не удалось преодолеть, несмотря на долгие и упорныеусилия многих крупных математиков, таких как Б. Рассел47, Г. Кантор48, Г.Фреге49, А. Пуанкаре50, К. Гедель51.Теория алгоритмов строит, упорядочивает и изучает конкретные моделиалгоритмов. Однако ввиду усиления интеграции наук, открытия в одной изобластей той же математики, физики, химии или, например, биологии могли46Галимова А.М., Тебякина Е.Е. Влияние развития технических наук на человека: проблемаконструирования идентичности в информационном обществе // Вестник ЛенинградскогоГосударственного университета имени А.С.
Пушкина. 2016. № 1. С. 93-99.47Рассел Б. Введение в математическую философию. Новосибирск: Сибирское университетскоеиздательство. 2007. 264 с.48Кантор Г. Труды по теории множеств. М.: Наука. 1985. 424 с.49Фреге Г. Избранные работы. М.: Дом интеллектуал. кн.: Анашвили. 1997. 159 с.50Пуанкаре А. Избранные труды в трех томах. М.: Наука. Том II. Новые методы небесноймеханики. Топология. Теория чисел. 1972. 358 с.51Колмогоров А.Н., Драгалин А.Г.
Математическая логика. М.: УРСС. 2004. 240 с.41свободно переходить и влиять на любую другую: информатику, астрономию,медицину. С развитием вычислительной техники и теории программированиявозрастаетнеобходимостьнаправленныхнапостроенияповышениеновыхэффективностиэкономичныхобработки,алгоритмов,полученияииспользования информации. Таким образом, изменяются способы построения,функционирования и записи алгоритмов на языке, понятном исполнителю, атакже способов конвертирования информации, пригодной для пользовательскогоиспользования. А, поскольку, особым типом исполнителя алгоритмов являетсякомпьютер, то необходимо создавать специальные средства, позволяющиечеловеку в удобном виде записывать алгоритмы и дающие компьютерувозможность понимать написанное. Такими средствами являются языкипрограммирования или алгоритмические языки.Дляпрактическогоподходакпроблемеиспользуетсяпоисквинформационных системах.
Он обеспечивает автоматизацию решения задач, нореализуется только при наличии алгоритма. Такой подход не дает возможностиформально описать задачу, так как простой полный перебор большой системыпрактически неосуществим и непригоден для описания сущности разумнойдеятельности. В реальной жизни люди все же используют перебор: нумизмат дляпополнения коллекция подбирает себе нужные монеты, просматривая каждыйпредложенный вариант, но он не станет брать все подряд, а будет обращатьвнимание только на то, что ему действительно подходит, то есть имеетопределенную ценность. Но все же полный перебор не используют даже люди:все тот же нумизмат не будет хвататься за любые попавшиеся монеты, он ужезнает какие виды ему стоит рассматривать, а какие нужно сразу отложить, дажене приступая к рассмотрению.
Сходным образом поступает, например,шахматный игрок при выборе хода, врач при определении диагноза илипрограммист при выборе кода для написания программы. Вопрос остается заактом конкретного выбора, учетом первостепенных факторов и наборовнеобходимых условий.42Проблемой сознательного выбора интересовался уже Аристотель, в«Никомаховой этике» можно найти следующее определение: «стремление исуждение, имеющее что-то целью. Сознательный выбор – это стремящийся ум, тоесть ум, движимый стремлением, или же осмысленное стремление, то естьстремление, движимое мыслью, а именно такое начало есть человек»52.
Решениезадачичеловеком основаноинформационнымсистемам,на правилах,направляющихкоторыекаким-топопоискпричинамктемкажутсянаилучшими. Так, математик, который проектирует программные средства,руководствуется собственным опытом и теоретическими знаниями.«Слово «алгоритм» (algorithm) уже само по себе представляет большойинтерес. На первый взгляд может показаться, будто кто-то намеревался написатьслово «логарифм» (logarithm), но случайно переставил первые четыре буквы. [...]оно берет начало от имени автора знаменитого персидского учебника поматематике, Абу Абд Аллах Мухаммед ибн Муса аль-Хорезми (около 825 г.),означающего буквально «Отец Абдуллы, Мухаммед, сын Мусы, уроженецХорезма».53 По переложенному с арабского на латинский арифметическомутрактатуаль-Хорезми,средневековаяЕвропазнакомиласьсиндийскойпозиционной системой счисления и с искусством счета в этой системе.
Влатинских названиях, составленных в XII веке изложений трудов аль-Хорезми,его имя транскрибировалось как alchorismi или algorismi, а относящийся к томуже веку латинский перевод его арифметического трактата начинался словами«Dixit algorizmi», т. е. «Сказал аль-Хорезми». Отсюда и пошло слово «алгоритм»— сначала для обозначения десятичной позиционной арифметики и алгоритмовцифровых вычислений (т. е. первых алгоритмических процедур, имеющих дело ссимволами, так как до того считали на счетной доске — абаке), а затем дляобозначения52произвольныхалгоритмов.54СамтерминалгоритмсталАристотель.
Соч.: в 4 т. Т. 4 М.: Мысль. 1983. 830 с.Кнут Д.Э. Искусство программирования. Основные алгоритмы. М., Т. 1. 2007. С. 27-28.54Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М., 1987.С. 7.5343употребляться для обозначения четырех арифметических операций, а именносложения, вычитания, умножения, деления.Но сами примеры алгоритмов существовали и были достаточно популярныеще задолго до появления книги аль-Хорезми.
Алгоритм Евклида можно назватьодним из наиболее известных и появился он еще с античности, приблизительно300 лет до н.э. Если записать его современным языком, то описание получитсяследующим: нам даны два целых положительных числа, что нужно сделать,чтобы найти наибольший общий делитель, то есть наибольшее положительноецелое число, которое нацело делит эти оба числа. В виде последовательныхуказаний можно его проиллюстрировать следующим образом:1. Задаем два целых положительных числа. Переход к следующему пункту.2. Сравнение этих чисел в трех вариантах: равенство, первое большевторого, первое меньше второго. Переход к следующему пункту.3. Если выполняется первый вариант с равенством чисел, то каждое из нихи дает нужный результат.
Этот случай останавливает дальнейшие вычисления, ноесли нет, то происходит переход к следующему пункту.4. Если первое данное число меньше второго, то они переставляютсяместами. Переход к следующему пункту.5. Далее вычитается второе число из первого и происходит определениедвух чисел: вычитаемого и остатка. Переход к пункту 2, где происходилосравнение чисел. И так до тех пор, пока не окажется выполненным условие,содержащееся в третьем пункте. Процесс прекращается.После пятого пункта идет возвращение ко второму до тех пор, пока небудет выполнено условие третьего пункта. Хотя заранее определить, сколькобудет подобных циклов, - сложно, но можно точно сказать, что к результатуможно прийти за конечное число шагов.Классические работы по теории алгоритмов были представлены ссередины 1930-х годов, публиковали их Алан Тьюринг, Алоиз Черч, Эмиль Пост.Исследования были посвящены построению формального описания алгоритма:Черч предложил класс рекурсивно-формальных функций, появились машина44Тьюринга и машина Поста.
Предположения, возникшие у этих ученых ивыраженные в виде вычислительных моделей, оказались эквивалентны как врамках формальных систем, так и в своем интуитивном определении алгоритма.Дальнейшиеразработкиужекасалисьдоказательствсуществованияалгоритмически неразрешимых проблем.Спустя приблизительно двадцать лет возник новый подход к изучениюпроблем теории алгоритмов – теория формальных грамматик, алгоритмическийформализм и другие. Но и эти исследования Колмогорова и Маркова оказалисьэквивалентными ранее упомянутым моделям Черча, Тьюринга и Поста в томзначении, что одну и ту же решаемую проблему в одной из систем, можно былорешить и в другой.Особый скачок произошел при появлении электронновычислительных машин и применении на практике полученных результатов.55Сегодня наиболее интересные результаты в разработке эффективныхалгоритмов связаны с привлечением аппарата других научных дисциплин, вчастности – биологии, физики и теоретических результатов специальных разделовсовременной математики.Алгоритмыделятсяпоразличнымоснованиям.Наиболеераспространенное деление - на численные и логические.
Алгоритмы, которыесводят решение поставленной задачи к арифметическим действиям над числами,называются численными алгоритмами. Типичными примерами численныхалгоритмов служат решения следующих задач: нахождение наибольшего общегоделителядвухположительныхнатуральныхчисел(алгоритмЕвклида);извлечение квадратного корня из рационального числа с заданной степеньюточности; вычисление ранга целочисленной матрицы.Логический алгоритм используется в игре «15»56.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
