План Разбор описания Алгоритма "точное предписание о порядке выполнения действий, из заданного фиксированного множества, для решения всех задач, заданного типа". Вводятся понятия: исходные данные, результат, действия, исполнитель
| Вид материала | Лекции |
- «бесконечность», 189.92kb.
- Понятие, свойства и способы описания алгоритма, 81.96kb.
- Ю. А. Самарский 10 июня 2011 г. Программа, 140.09kb.
- Понятие алгоритма, 18.42kb.
- Программа по дисциплине: информатика (алгоритмы и алгоритмические языки). Продвинутый, 140.13kb.
- Программа по дисциплине информатика (алгоритмы и алгоритмические языки). Основной курс, 103.21kb.
- План урока Организационный момент(1 мин) Проверка материала прошлого урока(10 мин.), 53.54kb.
- Для заданного полупроводникового диода, 92.07kb.
- Сценарий занятия по теме «Инсценировка произведения С. Маршака «Сказки о глупом мышонке», 37.09kb.
- Методические рекомендации: Взадачах такого типа используются понятия: объем видеопамяти, 338.92kb.
Лекции по информатике.
Лекция 1
Интуитивное понятие алгоритма и его свойств.
План
1. Разбор описания Алгоритма - "точное предписание о порядке выполнения действий, из заданного фиксированного множества, для решения всех задач, заданного типа".
Вводятся понятия: исходные данные, результат, действия, исполнитель.
Действие - преобразование об'ектов : Исходные данные -> Результаты.
Эти понятия демонстрируются на примере алгоритма Евклида нахождения наибольшего общего делителя (НОД) :
Дано: a, b - натуральные числа
Найти НОД (a, b)
Алгоритм:
1. Обозревай a и b (следующий шаг)
2. Сравни a и b (следующий шаг)
3. Если a=b, то a-рузультат (стоп)
иначе (следующий шаг)
4. Если a
5. Вычти bиз a (следующий шаг)
6. Положи a=разность, b=вычитаемое (перйти к шагу 2)
Подчеркивается различие между описанием алгоритма и вычислительным процессом (^ Вычислительный процесс - список всех совершенных действий. Вычислительный процесс порождается алгоритмом.)
Обращается внимание на два вида действий - над данными и над вычислительным процессом. Вводится понятие выражения.
2. ^ Численные алгоритмы : данные - числа; выражения - арифметические выражения.
На примере алгоримов вычисления полинома в точке по схеме Горнера "в лоб" демонтрируется существование нескольких алгоритмов для решения одной и той же задачи, но имеющих разную сложность.
Задача: для выражения вида AnX^n + ... +A1X + A0, где Ai - рациональное число, n>=1, Вычислим значение в точке X.
1. Схема Горнера.
1. Обозревай n-ый коэф. An и число X.
2. Умножь эти 2 числа
3. Прибавь следующий коэф. к произведению
4. Если коэф. на шаге 3 был с индексом 0,
то сумма на шаге 3 - результат.(стоп)
иначе обозревай сумму и число X (шаг 2)
Кол-во арифметических действий - 2n.
2. Прямой алгоритм.
1. Положим индекс i=n, а Сумму=0
2. Возведи X в степень i
3. Обозревай степень и коэф. Ai
4. Умножь эти 2 числа
5. Обозревай Сумму и произведение.
6. Сложи эти 2 числа
7. Результат положи в Сумму
8. Если индекс i=0, то результат - сумма (стоп)
иначе из i вычти 1 (шаг 2)
Кол-во арифметических действий - n*(n+1)/2+2*n.
Сложность алгоритма - кол-во действий в вычислительном процессе, порожденным этим алгоритмом. Для численных алгоритмов - это Кол-во арифметических действий.
Рассматривается вопрос: всегда ли численный алгоритм дает точное решение? На примере вычислений 20:3 и sqrt(2) показывается что в целом ряде случаев мы вынуждены довольствоваться лишь приблизительным решением.
3. Разъяснение свойтсва массовости алгоритмов. Парадокс Эвбулида "Что есть куча?" Один камень - это куча? Два? и т.д.
Массовость предполагает существование четко определенного класса объектов, которые могут быть исходными данными. Мощность класса - свойство класса объектов, а не алгоритма. Массовость означает существование языка данных, т.е. есть четкие правила построения этих объектов, называемых данными. Такие объекты - конструктивные объекты. Дается понятие конструктивных объектов - атомарные или составленные из атомарных по фиксированным правилам.
^ Класс задач - такие задачи, для которых существуют строгие правила строения исходных данных.
4. Нечисленные алгоритмы, как пример алгоритмов где исходные данные имеют сложную структуру. Расматривается проблема построения выигрышной стратегии для следующего класса игр:
Класс игр:
- Игроки ходят по очереди;
- Обязятельно выигрывает только один;
- При выборе очередного хода случайность отсутствует;
- Каждый играющий знает свои ходы и ходы притивника.
Строятся дерево игры (каждая ветвь - возможный вариант развития игры), алгоритм выбора выигрышного хода.
Теорема. В любой играе из расматриваемого класса всегда существует выигрышная стратегия для одного из игроков.
Доказательство: по индукции
1) Для n=1 ( n-кол-во ходов )
A: .
* * * * ... *
- дерево игры из одного хода, где * - или '+' (выигрыш), или '-'.
Если среди * есть хотя бы один '+', то A выиграл, иначе - B.
2) По индукции: если верно для S, то верно для S+1:
A: .
. . . . ... .
/ \ / \ / \ / \ / \
*** *** *** *** ***
Если среди * есть хотя бы один '+', то существует выигрышное поддерево (S) (по предположению индукции) => A выиграл.
Разъясняется свойство массовости применительно к данному случаю (А. применим к любой игре данного типа). На примере дерева игры для шахмат, вычислений над иррациональными числами вводится понятие потенциально осуществимого алгоритма, как алгоритма, вычислительный процесс которого доставляет желаемый результат, но время необходимое ему для этого не приемлемо для пользователя - того, в чьих интересах алгоритм выполняется.
5. Разъясняется понятие не применимости алгоитма к исходным данным.
А. наз. применимым к данным, если при работе с ними он остановится и выдаст определенный результат.
Приводятся как численные так и не численные примеры.
^ Проблема применимости.
Построить алгоритм, который по алгоритму и его исходным данным определяет, применим ли алгоритм к своим данным.
6. Рассматривается вопрос: для всякой ли массовой проблемы существует алгоритм. На примере 10-ой проблемы Гильберта (решение диофантовых уравнений) показывается существование алгоримтмически неразрешимых проблем:
Пример диофантова уравнения: X^2 + Y^2 - Z^2 = 0 (в целых числах). Одно из решений - X=3, Y=4, Z=5.
Решить уравнение: 6*X^18 - X +3 = 0 в целых числах.
Не существует алгоритма для решения любого диофантова уравнения.
Выводы :
Не для всякой массовой проблемы существует А;Для одной и той же проблемы могут существовать разные А с разной сложностью; А определяет последовательность действий;Данные, алгоритм и вычислительный процесс - конструктивные объекты;.Исходные данные образуют класс, описываемый некоторым языком;.А исходные данные определяют вычислительный процесс полностью;.При одних и тех же исходных данных А всегда дает один и тот же результат;.А одинаково понимается всеми исполнителями.
Алгоритм - точное предписание, которое задает потенциально осуществимый вычислительный процесс, начинающийся с призвольного исходного данного, из класса исходных данных, к которым данный А применим, и направленный на получение результата, полностью определенного этими исходными данными.
Основные свойства А:
- Массовость;
- Потенциальная осуществимость (конечность,сложность);
- Детерминированость;
- Однозначность понимания всеми исполнителями.
Вопросы :
1.Что определяет А?
2.Что такое вычислителдьный процесс?
3.Всегда ли по А можно определить точное число действий в вычислительном процессе?
4.2х2 = 4 - это А ?
5.Что такое численный А?
6.Всегда ли А дает точное решение?
7.Что означает массовость А?
8.Что такое конструктивный объект?
9.Отметить какие из нижеперечисленных объектов являются конструктивными - число 2, множество натуральных чисел, множество текстов на русском языке.
10.Что означает потенциальная осуществимость А?
11.Всякий ли А должен быть потенциально осуществим?
12.Что такое сложность А?
13.В каких единицах измеряется сложость А?
14.Можно ли сказать, что понятие области определения функции есть аналог множества исходных данных для А?
15.Как отличить результат от исходных данных и промежуточных результатов? результатов?
Лекция 2.
Уточнение понятия А - Машина Тьюринга. Основные понятия теории А.
1. Основные понятия теории А. Определяются понятия вычислимой функции, разрешимого множества, перечислимого множества.
A. вычисляет f(x) если для любого x, принадлежащего {Область применимости A} : A(x)=f(x)
В этом случае говорят что f(x) - вычислимая функция.
А. разрешает мн-во M относительно мн-ва X , где M - подмн-во X , если для любого m из мн-ва M: A(m)="да" и для любого x из X\M: A(x)="нет". Пример такого А. - признак делимости.
А. перечисляет мн-во B, если область применимости А - мн-во натуральных чисел, а совокупность результатов - мн-во B. Область применимость любого А. - пречислимое мн-во.
Демонстрируется взаимосвязь понятий функция и А. Формулируются основные свойства вычислимой функции, перечислимого множества, разрешимого множества. Слушателей подводят к необходимости формализации понятия А.
M - подмн-во X. Мн-во M называется разрешимым относительно мн-ва X <= M и X\M пречислимы.
2. Формализация понятия А. Каждый А хактеризуется 7 основными параметрами:
1.Совокупность возможных исходных данных;
2.Совокупность возможных результатов;
3.Совокупность возможных промежуточных результатов;
4.Правила непосредственной переработки (действия);
5.Правило начала;
6.Правило окончания;
7.Правило извлечения результата.
Вводится понятие уточнения А:
Выбор класса параметров определяет класс А. Цель математического уточнения А - изучение свойств А, как математического объекта, но не как практического инструмента для построения А.
3. Машина Тьюринга вводится как уточнение вышеперечисленных 7 параметров.
Алфавит D (один символ).
1.Совокупность возможных исходных данных D
2.Совокупность возможных результатов D;
3.Совокупность возможных промежуточных результатов DxRxQ;
4.Правила непосредственной переработки (действия): dp->rqw, где
d, r - принадл. D (символы)
p, q- принадл. Q (алфавит состояний)
w- принадл. { Л, П, Н }
5.Правило начала: начальное состояние.
6.Правило окончания '!' - принадл. Q
7.Правило извлечения результата: результат - справа от каретки до символа пустоты.
Рассматриваются следующие примеры МТ:
1.U(n) = n+1;
2.U(
3.U(
4.МТ для вычисления НОД.
Для каждого примера подсчитывается сложность.
1) А(n) = n+1
D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, П}
0 1 2 3 4 5 6 7 8 9 П
A 1ЛQ 2ЛQ 3ЛQ 4ЛQ 5ЛQ 6ЛQ 7ЛQ 8ЛQ 9ЛQ 0ЛA 1Л!
Q ЛQ ЛQ ЛQ ЛQ ЛQ ЛQ ЛQ ЛQ ЛQ ЛQ !
2) Унарная запись натурального числа : D = { |, П }
A(n) = n-1
| П
A ПЛQ |Л!
Q ЛQ !
3) Унарная запись -> десятичная.
1. Стираем палочку
2. Влево до цифры или пустоты
3. Увеличиваем число на 1
4. Вправо до последнего '|'
5. Если ее нет, то влево до пустоты, стоп.
Тезис Тьюринга: Для любой интуитивно вычислимой функции существует МТ, ее вычисляющая.
Выводы :
.А реализают лишь подмножество (класс вычислимых функций) функции, рассматриваемых в курсе мат.анализа;
.Алгоритмизация решения задачи состоит в разбиении задачи на подзадачи, подзадач на подподзадачи и т.д.;
.МТ можно строить из ранее построенных МТ.
Вопросы:
1.Квадратный крень из x - вычислимая функция?
2.Что такое вычислимая функция?
3.Как отличить вычислимую функцию от не вычислимой?
4.Множество вещественных чисел перечислимо?
5.Что такое пречислимое множество?
6.Мн-во четных целых чисел разрешимо относительно мн-ва целых чисел?
7.Сформулируйте условие разрешимости мн-ва В отностительно мн-ва М.
8.Перечислить параметры для уточнения поняти А.
9.Как в МТ задаются исходные данные?
10.Как в МТ задаются возможные результаты?
11.Как в МТ задаются промежуточные результаты?
12.Как в МТ задается правило начала работы А?
13.Как в МТ задается правило окончания работы?
14.Как в МТ извлекается результат?
15.Можно ли МТ строить из других МТ?
16.Как можно объединять несколько МТ в одну МТ?
Лекция 3.
Нормальные Алгоритмы Маркова.
Построение алгоритмов из алгоритов.
Нормальные алгоритмы Маркова вводяться как уточнение 7 основных параметров А:
1.Сов-ть возможных исходных данных - слова в алфавите S;
2.Совокупность возможных результатов - слова в W;
3.Совокупность возможных промежуточных результатов - SuWuV;
4.Правила непосредственной переработки (действия) - правила подстановки, порядок их применения и порядок просмотра слова;
5.Правило начала - всегда с первого правила и начала слова;
6.Правило окончания - терминальные парвила и неприменимость ни одного из правил;
7.Правило извлечения результата - преобразованное слово.
Сложность измеряется в количестве примененных правил подстановки. Рассматриваются примеры НАМ:
1.U(n) = n+1;
S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; W=S; V={*, +};
*0 -> 0*
*1 -> 1*
...
*9 -> 9*
* -> +
0+ -> +0
1+ -> +1
...
9+ -> +9
+ -> 1
-> *
2.U(
| |-> (Первый штрих в записи числа исчезает)
^ 3.U(
1) Поставить 0 слева от слова
2) Удалить '|'
3) Увеличить число на 1
4) Если нет '|', то стоп
иначе к шагу 2
0| -> 1
1| -> 2
2| -> 3
...
8| -> 9
9| -> |0
| -> 1
^ 4.МТ для вычисления НОД.
Во всех примерах подсчитывается сложность. Подчеркивается свойство НАМ - композиция нескольких НАМ в одну.Заканчиваетя рассмотрение НАМ формулировкой тезиса Маркова. Обращается внимание на равномощность МТ и НАМ в смысле мн-ва алгоритмов, которые можно описать с помощью этих А.с.
^ Тезис Маркова: Для любой интуитивно вычислимой функции существует НАМ, ее вычисляющий.
Построение алгоритмов из алгоритов.
На примере МТ и НАМ была показана возможность строить А из других А. Возникает вопрос: является ли этот принцип композиции универсальным. Другими словами можно ли аккумулировать знания в форме А, так чтобы на их основе строить другие А.
Эта проблема рассматривается на примере МТ. Вводятся четыре операции
° - последовательной композиции;
N - параллельной композиции;
if_then_else- разветвление;
while_do - цикл.
Доказывается четыре теоремы о том, что если есть МТ1 и МТ2 , то существует регулярная процедура построения МТ, эквивалентной последовательной и параллельной композации МТ1 и МТ2 ; если есть распознающий алгоритм F, то можно построить МТ реализующую if F then МТ1 else МТ2 ; МТ реализующую while F do МТ1.
Теорема 1.
Для любых МТ A и B можно эффективно построить МТ, С(p)=A(p)°B. (Для любого p из области применимости A)
Док-во
| A | |
| | B |
Алфавит полученной МТ ести об'единение алфавитов исходных МТ.
'!' в МТ A , заменим на переход в начальное состояние B.
^ Правило паралелльной композиции
Паралелльная композиция A||B
A(P||R)°B = B(P||R)°A = B(P) || A(R)
Теорема 2
Для любых МТ A и B можно эффективно построить МТ, С(P||R)=A(P) || B(R).
МТ с полулентой не слабее МТ с полной лентой.
^ Разветвление алгоритма
Ф(р) = 1, если условие выполнено
0, в противном случае
=> Ф - распознающий алгоритм.
Теорема 3
Для любых МТ A, B и распознающей Ф с одинаковым алфавитом можно эффективно построить МТ, С(P) = A(P), если Ф(р)=1
B(P), в противном случае.
^ Повторное применение А
Теорема 4
Для любой МТ A и распознающей Ф можно эффективно построить МТ, С(P) = { повторяй A, пока Ф }
Теорема
Любая МТ может быть построена с помощью опраций последовательной и паралелльной композиций, условной и циклической конструкций.
Выводы :
. Алгоритм - конструктинвый объект;
. Алгоритм можно строить из других алгоритмов;
. °, N, if_then_else, while_do - универсальный набор действий по управлению вычислительным процессом.
Вопросы :
1. Что такое правило подстановки?
2. Зависит ли резельтат от порядка следования правил в НАМ?
3. Что происходит когда не применимо ни одно правило подстановки?
4. Что утверждает тезис Маркова?
5. Что означает равномощность А.с.?
6. Что такое А.с.?
7. Можно ло доказать тезис Маркова?
8. Семантика операции °?
9. Семантика операции N?
10.Семантика операции if_then_else?
11.Семантика операции while_do?
Лекция 4.
Существование универсальных вычислителей.
Алгоритмические проблемы и взаимосвязь алгоритмических систем.
1. ^ Существование универсальных вычислителей.
Рассматривается проблема: А - описание, определенного множества последовательностей действий, из фиксированного множества действий. Для каждого А нужен свий исполнитель или же можно построить один способный выполять все алгоритмы в данной А.с.?
Эта проблема рассматривается для А.с. - МТ. Сначала рассматривается алгоритм подражения в интуитивной форме. Требуется построить МТ:
исходные данные - функциональная схема другой МТ и данные для нее.
результат - результат, который выдала бы задаваемая МТ при работе.
Затем показывается, что для того чтобы преобразовать этот интуитвный А в форму МТ надо решить две проблемы:
- как задать функциональную схему МТ в линейной форме?
- так как произвольная МТ может иметь произвольный алфавит, то какой алфавит будет у универсальной МТ (УМТ)?
Дается строгое математическое решение этих двух проблем. После этого алгоритм подражания переформулируется из интуитивной формы в форму МТ.
1. Запишем МТ пятерками вида A 0 1 Л Q
2. Проблема кодировки. Пример кодировки :
Л 101
Н 1001
П 10001
S1 100001 Q1 1000001
S2 10000001 Q2 100000001
S3 1000000001 Q3 10000000001
... ...
2. ^ Алгоритмические проблемы и взаимосвязь А.с.
Рассматривается понятие Алгоритмической проблемы. Приводятся примеры 10-ой проблемы Гильберта как неразрешимой А.п.
Дано: правила подстановки, слова W и S.
?Можно ли преобразовать W->S с помощью данных правил подстановаки?
Ответ: Нельзя.
Алгоритм самоприменим, если он может быть применен к слову, представляющему его описание.
^ Теорема: Распознавание самоприменимости неразрешимо.
Доказательство:
Допустим, что существует А, распознающий самоприменимость
А(U) = b, если U самоприменим
c, в противном случае.
=> можно из А построить B(U), который не останавливается, если U самоприменим и останавливается, выдавая c в противном случае.
Рассмотрим B(B):
- если B(B)=c => B остановился => самоприменим. Но в то же время он несамоприменим. Противоречие.
- если B(B) не остановился => B несамоприменим. Но в то же время он самоприменим. Противоречие.
=> Теорема доказана.
В связи с неразрешимостью А.п. рассматривается проблема: Не может ли оказаться так, что А.п. неразрешимая в одной А.с. окажется разрешимой в другой А.п.?
На примере МТ и НАМ доказывается что для равномощных А.с. если А.п. неразрешима в одной А.с., то она не разрешима и в другой.
Две А.с. - равномощны если они описывают одни и теже классы А.
Доказываются две теоремы:
1. Для любой МТ существует эффективная процедура построения эквивалентного НАМ.
2. Для любого НАМ существует эффективная процедура построения эквивалентной МТ.
Все доказательства конструктивны.
Выводы :
. Для любой А.с. существует универсальный исполнитель, который есть интерпритатор множества действий заданной А.с.;
. В силу тезиса Тьюринга любой А реализуем в терминах действий последовательной, паралелльной композаций, выбора и цикла и базового набора действий;
. Проблема применимости не применима;
. Если А.п. не разрешима, то она не разрешима в любой равномощной А.с.;
. МТ и НАМ равномощны.
Вопросы :
1. Что такое интерпритация?
2. Что такое кодирование?
3. В чем проблема линеаризации Ф.с. для МТ?
4. Что такое универсальный исполнитель:
- он может исполнять заданный А в любой А.с.?
- он может исполнять любой А, выразимый в даннолй А.с.?
5. Как решается проблема произвольности алфавита в УМТ?
6. Что такое А.п.?
7. Самоприменимость - что это такое?
8. А.п. самоприменимости разрешима?
9. В МТ А не закончен если нет применимого правила, в НАМ в этом случае А - закончен. Как это несоответсвие реашется при доказательстве сводимости МТ к НАМ и наоборот?
10. Что означает запись:
Если F (*P) то M (1NQ*a R)°U °U иначе U °U °U ?