Пятница, 21.07.2017, 21:45
ОТКРЫТАЯ ИНФОРМАТИКА
Приветствую Вас Гость | RSS
Главная Алгоритм Регистрация Вход
Меню сайта

Форма входа

Поиск

Календарь
«  Июль 2017  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930
31

Урок 1-2

Алгоритм. Основы теории алгоритмов.

Интуитивное определение алгоритма

Алгоритм – это конечная последовательность указаний на языке понятном исполнителю, задающая процесс решения задач определенного типа и ведущая к получению результата, однозначно определяемого допустимыми исходными данными.

Историческая справка

Слово "алгоритм" было введено в обращение узбекским математиком, основателем алгебры, жившим в IX веке - аль-Хорезми. В науке использовать понятия "алгоритм" начал немецкий ученый Лейбниц в 17-м веке. Первые известные алгоритмы — это правила выполнения арифметических действий с числами. В них четко определены объекты (числа в десятичной записи) и элементарные шаги (сложить, вычесть, перемножить два однозначных числа).

Мухаммед Муса аль-Хорезми

Долгое время считалось, что для абсолютно любой задачи можно составить алгоритм. Однако, в 1931 году австрийский математик А.Гедель  доказал теорему о неполноте, смысл которой состоит в том, что в любой достаточно сложной формальной системе, основанной на аксиомах (например, в арифметике, где введены натуральные числа и операции сложения и умножения), есть утверждение, которое невозможно ни доказать, ни опровергнуть в рамках этой системы. Поэтому было высказано предположение о том, что некоторые задачи алгоритмически неразрешимы, то есть для них в принципе не существует алгоритма решения, и поэтому искать его бессмысленно. Исследования, которые начали проводить в этой области в 30-х годах 20-го века привели к возникновению теории алгоритмов. В настоящее время, теория алгоритмов занимается: доказательством алгоритмической неразрешимости задач; анализом сложности алгоритмов; сравнительной оценкой качества алгоритмов. 1

Значительный вклад в развитие теории алгоритмов внесли:

Алан Тьюринг (Великобритания).
Предложенная им в 1936 году абстрактная вычислительная "Машина Тьюринга" позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследований.

Эмиль Пост (США).
Предложил абстрактную вычислительную машину - машину Поста.


Алонзо Чёрч (Великобритания)
прославился разработкой теории лямбда-исчислений, последовавшей за его знаменитой статьёй 1936 года, в которой он показал существование «неразрешимых задач»

Стивен Клини (США).
Теория конечных автоматов.

Андрей Андреевич Марков (СССР)


         

  ЦОР : school-collection.edu.ru 

FLASH- интерактивный слайд "Возникновение понятия алгоритм" 

FLASH- интерактивный слайд "Исполнитель алгоритма"  

FLASH- интерактивный слайд "Свойства алгоритма"  

Исполнитель алгоритма

Понятие "алгоритм" тесно связано с понятием "исполнитель" - устройство, выполняющее алгоритм.  Алгоритм должен, соответственно, использовать только те команды, которые понятны исполнителю.  При этом про любой алгоритм можно сказать, что:

- алгоритм получает на вход данные (в дискретном виде - цифра или слово);

- алгоритм обрабатывает полученные данные по шагам, вычисляя на каждом шаге промежуточные данные. Этот процесс может быть конечным и бесконечным.

- если процесс работы алгоритма конечен, то результат работы алгоритма - данные, вычисленные на последнем шаге.

- если процесс работы алгоритма бесконечен (зациклился), то результат его работы - неопределен.

Универсальным исполнителем называют исполнителя, для которого можно построить алгоритм, эквивалентный любому алгоритму для любого другого исполнителя. Такого исполнителя можно использовать для доказательства разрешимости или неразрешимости задач. Если удается построить алгоритм решения задачи для универсального исполнителя, то задача разрешима. Если доказано, что алгоритма не существует, то задача неразрешима. Система команд такого исполнителя должна быть как можно проще — так его будет легче использовать в доказательствах.

Каждый универсальный исполнитель строится на основе математических терминов. Созданием универсальных исполнителей занимались такие ученые, как А.Тьюринг (машина Тьюринга), А.Пост (машина Поста), А.А. Марков (нормальные алгоритмы Маркова).

Универсальный исполнитель связан с проблемой строгого определения алгоритма:

Любой алгоритм может быть представлен, как программа для универсального исполнителя.

Алгоритм - это программа для универсального исполнителя.

Это основная идея теории алгоритмов.

В настоящее время универсальным исполнителем считается компьютер.

Свойства алгоритма

Дискретность (разделенность на части) и упорядоченность. Алгоритм должен состоять из отдельных действий, которые выполняются последовательно друг за другом.

Детерминированность (однозначная определенность). Многократное применение одного алгоритма к одному и тому же набору исходных данных всегда дает один и тот же результат.

Формальность. Алгоритм не должен допускать неоднозначности толкования действий для исполнителя.

Результативность и конечность. Работа алгоритма должна завершаться за определенное число шагов, при этом задача должна быть решена.

Массовость. Определенный алгоритм должен быть применим ко всем однотипным задачам.


Центральная задача теории алгоритмов — выяснить, существует ли алгоритм решения той или иной задачи.

Если да, то возникает следующий вопрос: а можно ли им воспользоваться на практике, при современном уровне развития вычислительной техники? То есть способен ли компьютер за приемлемое время получить результат?

Требования к алгоритму:

1. Максимальная скорость выполнения алгоритма (временная сложность - время выполнения программы, работающей по данному алгоритму).

Временем работы алгоритма называется количество выполненных им элементарных операций T. Такой подход позволяет оценивать именно качество алгоритма, а не свойства исполнителя (например, быстродействие компьютера, на котором выполняется алгоритм).

Как правило, величина T будет существенно зависеть от объема исходных данных: поиск в списке из 10 элементов завершится гораздо быстрее, чем в списке из 10 000 элементов. Поэтому сложность алгоритма обычно связывают с размером входных данных n и определяют как функцию T(n). Например, для алгоритмов обработки массивов в качестве размера n используют длину массива. Функция T(n) называется временнóй сложностью алгоритма.

2. Минимальный объем памяти (пространственная сложность).

3. Проста и понятность, что позволяет легче отлаживать программу.


Вопрос:

Более полувека тому назад была написана пьеса «РУР» («Россумские универсальные роботы»), персонажами которой были люди и роботы, т. е. искусственные люди. Позже слово «робот» стало часто использоваться при описании электронных цифровых устройств, имеющих механические системы для передвижения, совершения манипуляций. Кто придумал слово «робот»?


Контрольные вопросы:

1. Каковы способы записи алгоритмов?

2. Кто и когда впервые ввел понятие алгоритма?

3. В чем заключаются основные свойства алгоритма?

4. Перечислите основные алгоритмические структуры и опишите их.

5. Каковы основные принципы разработки алгоритмов?

6. Чем объясняется разнообразие форм записи алгоритмов?

7. Охарактеризуйте словесно-пошаговый способ записи алгоритмов.

8. Охарактеризуйте табличную форму записи алгоритмов.

9. Что такое результат выполнения алгоритма?

10. Что такое исходные данные?

11. Что представляет собой графическая форма записи алгоритма?

12. Каков порядок составления блок-схем?

13. Охарактеризуйте основные блоки блок схем?

14. Для чего необходимо ветвление в алгоритмах?

15. Какие формы ветвления различают?

16. Для чего используют структуру "цикл"?

17. Какие виды циклов вы знаете?

18. Что такое тело цикла?

19. Какие циклы называют итерационными? Приведите примеры.

20. Что такое итерация?


Проверь себя:

Кроссворд  (И. Семакин http://school-collection.edu.ru/) 

       Тренировочный интерактивный тест

      Итоговый интерактивный тест


 Дополнительные источники:

          Статья "Введение в понятие алгоритма" (сайт Планета Информатики)

FLASH - иллюстрированный материал (презентация) "Алгоритмическое обеспечение информационных технологий"


Использованная литература:

1. Журнал "Информатика". "Алгоритм - понятие неопределяемое? Основы теории алгоритмов". К.Ю. Поляков, Е.А Еремин

Наш опрос
Имеете ли вы доступ к компьютеру и в какой форме?
Всего ответов: 447

Друзья сайта
  • Министерство образования РБ
  • Официальный портал подготовки к ГИА и ЕГЭ
  • Всероссийская олимпиада школьников
  • Федеральный портал Российского образования
  • Институт развития образования РБ

  • Статистика

    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0

    Copyright MyCorp © 2017 Бесплатный конструктор сайтов - uCoz