Алгоритмы и исполнители

Алгоритмы и исполнители

Ключевые слова:

• Алгоритм
• Свойства алгоритмов
• Исполнители алгоритмов
• Система команд исполнителя
• Универсальные исполнители
• Сложность алгоритма

• Основные алгоритмические конструкции
• Вспомогательные алгоритмы
• Формальное исполнение алгоритмов

Учебные алгоритмические задачи

• Выполнить роль исполнителя ( игра Баше)
• Определить исполнителя и систему команд (кассир)
• Определить исходный набор данных (покупки в магазине, вычисление времени падения кирпича с крыши дома)
• Овладеть методикой построения алгоритмов

Алгоритм

• Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми ( Alhorithmi ), жившего в 783—850 гг.
• В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком".
• В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

1. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ. (ФОРМУЛЫ)

2. АЛГОРИТМИЗАЦИЯ ЗАДАЧИ

(БЛОК-СХЕМА)

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

2. ПРОГРАММА, НАПИСАННАЯ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ

( ТЕКСТОВЫЙ ФАЙЛ )

3. КОМПИЛЯЦИЯ ПРОГРАММЫ- СОЗДАНИЕ ВЫПОЛНЯЕМОГО КОДА ПРОГРАММЫ

( .EXE ИЛИ .COM ФАЙЛЫ )

4. ЗАПУСК ПРОГРАММЫ НА ИСПОЛНЕНИЕ.

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

• Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять.

Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.

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

2. Дискpетность (прерывность, раздельность) — алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).

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

3. Опpеделенность — каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола.

Благодаpя этому свойству выполнение алгоpитма носит механический хаpактеp и не тpебует никаких дополнительных указаний или сведений о pешаемой задаче.

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

4. Pезультативность (или конечность) состоит в том, что за конечное число шагов алгоpитм должен:

• 4. Pезультативность (или конечность) состоит в том, что за конечное число шагов алгоpитм должен:

• либо пpиводить к pешению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.
• либо пpиводить к pешению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.
• либо пpиводить к pешению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.
• либо пpиводить к pешению задачи,
• либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения,
• либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.

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

5. Массовость означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными.

Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.

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

• Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

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

использовать Водолей

Система команд:

наполни А

вылей В перелей из А в В

использовать Кузнечик

Система команд:

вперед ( 3 )

назад ( 2 )

перекрасить

использовать Черепаха

Система команд:

поднять хвост

опустить хвост

вперед ( 50 )

назад ( 50 )

вправо ( 45 )

влево ( 45 )

Задания

• Нарисовать прямоугольный треугольник
• Нарисовать равносторонний треугольник
• Нарисовать звезду по 5 линиям
• Нарисовать круг
• Нарисовать цветок из кругов
• Нарисовать елку из треугольников

использовать Робот

Система команд:

вверх; вниз; вправо; влево

закрасить

температура

радиация

сверху стена

сверху свободно

снизу стена

снизу свободно

справа стена

справа свободно

слева стена

слева свободно

клетка закрашена

клетка чистая

Задания

• Пройти лабиринт из стен
• Закрасить всё вокруг стены
• Обрисовать букву (цифру)
• Определить место с радиацией
• Определить пожар (повышенная температура)

использовать Чертежник

Система команд:

поднять перо опустить перо сместиться на вектор ( dx , dy ) сместиться в точку ( x , y ) установить цвет ( "красный" ) надпись ( 12 , "Рисунок" )

Задания

• Нарисовать игрушку домик, грузовик, матрешку и т.д.
• Нарисовать сказочного героя
• Построить график функции y=sin(x)
• Построить график параметрической функции x=r cos(a); y=r sin(a)

Другие исполнители

• Паркетчик
• Стрелка
• ГРИС
• Кенгуру, Строитель, Муравей, РобоЧерт
• BillBot2, Cude-IT, Pereprava
• Scratch (рыжий котенок)
• Kodu (3D игры)
• Blockly

Паркетчик

Стрелка

ГРИС

Кенгуру

Муравей

Строитель

РобоЧерт

BillBot2

Cube-IT

Pereprava

Scratch

Kodu

Blockly