Лекции по информатике

Лекции по информатике.

Лекция 1

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

План

1. Разбор описания Алгоритма - "точное предписание о порядке выполнения действий, из заданного фиксированного множества, для решения всех задач, заданного типа".

Вводятся понятия: исходные данные, результат, действия, исполнитель.

Действие - преобразование об'ектов : Исходные данные -> Результаты.

Эти понятия демонстрируются на примере алгоритма Евклида нахождения наибольшего общего делителя (НОД) :

Дано: a, b - натуральные числа

Найти НОД (a, b)

Алгоритм:

1. Обозревай a и b (следующий шаг)

2. Сравни a и b (следующий шаг)

3. Если a=b, то a-рузультат (стоп)

иначе (следующий шаг)

4. Если a<b, то поменяй их местами (следующий шаг)

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( <n в ун. записи> ) = <n-1 в ун. записи>;

3.U( <n в ун. записи> ) = n;(строиться как композиция МТ1 и МТ2)

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;