Міністерство освіти, науки, молоді та спорту України
Одеський національний політехнічний університет
КОБОЗЄВА АЛЛА АНАТОЛІЇВНА
АНАЛІЗ ТА РОЗПАРАЛЕЛЮВАННЯ АЛГОРИТМІВ
Конспект лекцій для студентів напряму 8.040302 – Інформатика
Затверджено
на засіданні кафедри ІММЗІС
Протокол №6 від 13 грудня 2010 р.
Одеса-2011
Автор: Кобозєва Алла Анатоліївна
Аналіз та розпаралелювання алгоритмів. Конспект лекцій для магістрів напряму підготовки 040302 – Інформатика. – Одеса, 2011. - 81 с.
Передмова
Предметом вивчення в курсі «Аналіз та розпаралелювання алгоритмів» є алгоритми, їх структура та властивості.
Мета: Одержання загальної інформації про алгоритми, їх властивості та структуру, формування навичок і вмінь проведення аналізу властивостей алгоритмів, їх порівняння, побудови різноманітних методів для формування алгоритмів з заданими характеристиками.
Місце дисципліни у навчальному процесі: у системі підготовки магістрів за спеціальністю – «Інформатика» дисципліна “Аналіз та розпаралелювання алгоритмів ” є фундаментальною.
Задачі вивчення дисципліни:
Формування у студентів загального поняття алгоритму, використання його для можливості порівняння декількох алгоритмів за різними параметрами;
Формування навичок виділяти головні характеристики алгоритмів;
Формування навичок аналізувати алгоритм на основі його графу;
Формування навичок виявлення наявності (відсутності) внутрішнього паралелизму алгоритму для з’ясування питання про можливість його розпаралелювання;
Формування навичок аналізувати алгоритм на основі його часових розгорток.
Структура дисципліни:
Кількість кредитів – 4
Кількість семестрових модулів – 2
Повний обсяг часу на вивчення дисципліни, в годинах – 144
В тому числі аудиторні заняття, в годинах – 46
З них: лекційні, в годинах – 30
лабораторні, в годинах – 16
Обсяг часу на самостійну роботу студента, у годинах – 98
Підсумкова форма рейтингового контролю – іспит
Семестровий модуль 1.
Змістовий модуль 1. ПОНЯТТЯ АЛГОРИТМУ. ОСОБЛИВОСТІ ЧИСЕЛЬНИХ АЛГОРИТМІВ
Лекция 1. ФОРМАЛИЗАЦИЯ ПОНЯТИЯ АЛГОРИТМА
План
История развития понятия алгоритма
Общие требования к алгоритму
Формальное представление алгоритма. Машина Тьюринга.
Алгоритмически неразрешимые проблемы: их существование и примеры
1. История развития понятия алгоритма
Понятие алгоритма является одним из основных понятий современной математики. Еще на самых ранних ступенях развития математики (Древний Египет, Вавилон, Греция) в ней стали возникать различные вычислительные процессы чисто механического характера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике получили название алгоритмов.
Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в ІХ в. дал правила выполнения четырех арифметических действий в десятичной системе счисления.
Вплоть до 30-х годов прошлого века понятие алгоритма имело скорее методологическое, чем математическое значение. Под алгоритмом понимали конечную совокупность точно сформулированных правил, которые позволяют решать те или иные классы задач. Однако в этом определении не содержится точной характеристики того, что следут понимать под классом задач и под правилами их решения. В течение длительного времени математики довольствовались этим определением, поскольку общей теории алгоритмов фактически не существовало. Однако, практически не было серьезных случаев, когда математики разошлись бы во мнении относительно того, является ли алгоритмом тот или иной конкретно заданный процесс.
Положение существенно изменилось, когда на первый план выдвинулись такие алгоритмические проблемы, положительное решение которых было сомнительным. Действительно, одно дело доказать существование алгоритма, другое – его отсутствие. Первое можно сделать путем фактического описания процесса, решающего задачу. В этом случае достаточно и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс есть алгоритм. Доказать несуществование алгоритма таким путем невозможно. Для этого надо точно знать, что такое алгоритм.
В двадцатых годах прошлого века задача такого определения понятия алгоритма стала одной из центральных математических проблем. Решение ее было получено в середине тридцатых годов в работах известных математиков: Гильберта, Геделя, Черча, Клини, Поста и Тьюринга.
В 50-е годы прошлого столетия существенный вклад в развитие теории алгоритмов внесли работы Колмогорова и Маркова. Формальные модели алгоритмов Поста, Тьюринга и Черча, равно как и модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешим и в другой.
Хотя первоначально теория алгоритмов возникла в связи с внутренними потребностями теоретической математики (математическая логика, алгебра, геометрия и т.д. остаются и сегодня одной из основных областей приложения теории алгоритмов), другая область ее применения возникла в 40-х годах в связи с созданием быстродействующих электронных вычислительных и управляющих машин. Появление ЭВМ способствовало развитию теории алгоритмов, вызвало к жизни разделы этой теории , имеющие ярко выраженную прикладную направленность. Это, прежде всего, алгоритмические системы и алгоритмические языки, являющиеся основой современной теории программирования для универсальных ЭВМ, и способы точного описания отображений, реализуемых цифровыми автоматами.
Теория алгоритмов оказалась тесно связанной и с рядом областей лингвистики, экономики, физиологии мозга и психологии, философии, естествознания. Примером одной из задач этой области может служить точное описание алгоритмов, реализуемых человеком в процессе умственной деятельности.
2. Общие требования к алгоритму
Во всех сферах своей деятельности человек сталкивается с различными способами или методиками решения разнообразных задач. Они определяют порядок выполнения действий для получения желаемого результата – мы можем трактовать это как первоначальное или интуитивное определение алгоритма. Таким образом, можно нестрого определить алгоритм как однозначно трактуемую процедуру решения задачи. Дополнительные требования о выполнении алгоритма за конечное время для любых входных данных приводят к следующему неформальному определению алгоритма:
Алгоритм – это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых и точно определенных элементарных операций для решения задачи, общее для класса возможных исходных данных.
Пусть
-
множество исходных данных задачи
,
а
-
множество возможных результатов. Тогда
можно говорить, что алгоритм осуществляет
отображение
.
Алгоритм
называется частичным,
если мы получаем результат только для
некоторых
,
и полным,
если алгоритм получает правильный
результат для всех
.
На сегодняшний день отсутствует одно исчерпывающее опредление алгоритма. Приведем несколько используемых определений.
Определение 1. (Колмогоров): Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Определение 2. (Марков): Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
В приведенных словесных определениях очевидна проблема однозначной трактовки терминов, в силу чего возникают следующие неопределенности с
исполнителем предписаний,
вычислительными возможностями исполнителя,
указанием, какие именно операции для исполнителя являются «элементарными».
Более того, если даже алгоритм заведомо существует, его может быть очень трудно описать в некоторой зараннее заданной форме. Например, алгоритм завязывания шнурков.
Однако, несмотря на имеющиеся неопределенности и неоднозначности, различные определения алгоритма в явной или неявной форме постулируют следующие общие требования [Макконнелл]:
Алгоритм должен содержать конечное количество элементарно выполнимых предписаний, т.е. удовлетворять требованию конечности записи;
Алгоритм должен выполнять конечное количество шагов при решении задачи, т.е. удовлетворять требованию конечности действий;
Алгоритм должен быт единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;
Алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т.е. удовлетворять требованию правильности.
Необходимо отметить, что сравнение алгоритмов по их эффективности, проверка их правильности и эквивалентности, определение областей применимости возможны только на основе формализации понятия алгоритма. В связи с этим чрезвычайно важно наличие формально строгого определения понятия алгоритма. Формализации данного понятия связаны с введением специальных математических конструкций – формальных алгоритмических систем или моделей вычислений, каковыми являются машина Поста, машина Тьюринга, рекурсивно-вычислимые функции Черча, и постулированием тезиса об эквивалентности такого формализма и понятия «алгоритм». Несмотря на принципиально разные модели вычислений, использующиеся в теории алгоритмов для определения термина «алгоритм», интересным результатом является формулировка гипотез об эквивалентности этих формальных определений.