Алгоритмические машины и свойства алгоритмов
Группа № 11 Информатика и ИКТ
Урок № 12
Тема: Обработка информации. Систематизация информации. Алгоритмизация как необходимое условие автоматизации.
Практическая работа № 6. Составление алгоритма управления работой исполнителя
Цели: познакомиться с основными понятиями темы.
ПЛАН
1. Проработать теоретический материал
2. Найти информацию в Интернете «Организация хранения и обработки данных, в том числе с использованием интернет-сервисов, облачных технологий и мобильных устройств».
Теоретические сведения
Обработка информации, наряду с хранением и передачей, относится к основным видам информационных процессов.
Варианты обработки информации
Обработка информации производится каким-то субъектом или объектом (например, человеком или компьютером) в соответствии с определенными правилами. Будем его называть исполнителем обработки информации. Информация, которая подвергается обработке, представляется в виде исходных данных. На рисунке 2.2 в обобщенном виде представлен процесс обработки информации.
Можно привести множество примеров, иллюстрирующих схему на рис. 2.2.
Первый пример: ученик (исполнитель), решая задачу по математике, производит обработку информации. Исходные данные содержатся в условии задачи. Математические правила, описанные в учебнике, определяют последовательность вычислений. Результат — это полученный ответ.
|
|
Второй пример: перевод текста с одного языка на другой — это пример обработки информации, при которой не меняется ее содержание, но изменяется форма представления — другой язык. Перевод осуществляет переводчик по определенным правилам, в определенной последовательности.
Третий пример: работник библиотеки составляет картотеку книжного фонда. На каждую книгу заполняется карточка, на которой указываются все параметры книги: автор, название, год издания, объем и пр. Из карточек формируется каталог библиотеки, где эти карточки располагаются в строгом порядке. Например, в алфавитном каталоге карточки располагаются в алфавитном порядке фамилий авторов.
Четвертый пример: в телефонной книге вы ищете телефон нужной вам организации, например плавательного бассейна; или в том же библиотечном каталоге разыскиваете сведения о нужной вам книге. В обоих случаях исходными данными является информационный массив — телефонный справочник или каталог библиотеки, а также критерии поиска — название организации или фамилия автора и название книги.
Приведенные примеры иллюстрируют четыре различных вида обработки информации:
|
|
1) получение новой информации, новых сведений;
2) изменение формы представления информации;
3) систематизация, структурирование данных;
4) поиск информации.
Все эти виды обработки может выполнять как человек, так и компьютер. В чем состоит принципиальное различие между процессами обработки, выполняемыми человеком и машиной?
Если исполнителем обработки информации является человек, то правила обработки, по которым он действует, не всегда формальны и однозначны. Человек часто действует творчески, неформально. Даже однотипные математические задачи он может решать разными способами. Работа журналиста, ученого, переводчика и других специалистов — это творческая работа с информацией, которая выполняется ими не по формальным правилам.
Об алгоритмах
Для обозначения формализованных правил, определяющих последовательность шагов обработки информации, в информатике используется понятие алгоритма.
Из курса информатики основной школы вы знаете, что слово «алгоритм» произошло от имени выдающегося математика средневекового Востока Мухаммеда аль-Хорезми, описавшего еще в IX веке правила выполнения вычислений с многозначными десятичными числами. Правила сложения, вычитания, умножения столбиком, деления «уголком», которым вас учили в младших классах, — это алгоритмы аль-Хорезми.
|
|
С понятием алгоритма в математике ассоциируется известный способ вычисления наибольшего общего делителя (НОД) двух натуральных чисел, который называют алгоритмом Евклида.
В словесной форме его можно описать так:
1. Если числа не равны, то большее из них заменить на разность большего и меньшего из чисел.
2. Если два числа равны, то за НОД принять любое из них, иначе перейти к выполнению пункта 1.
Первоклассник, который не знает, что такое НОД, но умеет сравнивать целые числа и выполнять вычитание, сможет исполнить алгоритм. Действовать при этом он будет формально.
Такой формализованный алгоритм легко запрограммировать для современного компьютера. Мечта создать машину — автоматическое устройство, которое сможет без вмешательства человека производить расчеты, появилась очень давно. Для ее реализации требовались не только технические возможности, но и глубокое понимание сущности алгоритмов обработки информации и разработка формализованного способа представления таких алгоритмов.
Алгоритмические машины и свойства алгоритмов
В 30-х годах XX века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.
|
|
Английский ученый Алан Тьюринг предложил модель такого исполнителя, получившую название «машина Тьюринга». По замыслу Тьюринга, его «машина» является универсальным исполнителем обработки любых символьных последовательностей в любом алфавите. Практически одновременно с Тьюрингом (1936-1937 гг.) другую модель алгоритмической машины описал Эмиль Пост. Машина Поста работает с двоичным алфавитом и несколько проще в своем «устройстве». Можно сказать, что машина Поста является частным случаем машины Тьюринга. Однако именно работа с двоичным алфавитом представляет наибольший интерес, поскольку, как вы знаете, современный компьютер тоже работает с двоичным алфавитом. Подробнее с машиной Поста вы познакомитесь в следующем параграфе.
На основании моделей Тьюринга, Поста и некоторых других ученые пришли к выводу о существовании алгоритмически неразрешимых задач.
Язык программирования алгоритмических машин представляет собой описание конечного числа простых команд, которые могут быть реализованы в автоматическом устройстве.
Совокупность всех команд языка исполнителя называется системой команд исполнителя алгоритмов — СКИ.
Алгоритм управления работой алгоритмической машины представляет собой конечную последовательность команд, посредством выполнения которой машина решает задачу обработки информации.
Алгоритм управления такой машиной должен обладать следующими свойствами:
• дискретностью (каждый шаг алгоритма выполняется отдельно от других);
• понятностью (в алгоритме используются только команды из СКИ);
• точностью (каждая команда определяет однозначное действие исполнителя);
• конечностью (за конечное число шагов алгоритма получается искомый результат).
Отметим разницу между понятиями «команда алгоритма» и «шаг алгоритма». Команда — это отдельная инструкция в описании алгоритма, а шаг алгоритма — это отдельное действие, которое исполнитель выполняет по команде. В циклических алгоритмах число шагов при выполнении алгоритма может быть больше, чем число команд в алгоритме, за счет повторного выполнения одних и тех же команд.
Выполнить практическую работу № 2.1 "Управление алгоритмическим исполнителем"
Цель работы: закрепление навыков программного управления учебными исполнителями алгоритмов, полученных при изучении курса информатики в 7-9 классах.
Используемое программное обеспечение: среда какого-либо учебного исполнителя алгоритмов графического типа, назначение которого — рисование на экране компьютера. К числу таких исполнителей относятся: Черепашка Лого, Чертежник, Кенгуренок и др.
Задание 1
Написать подпрограмму (процедуру) STEP и с ее помощью составить программу рисования лесенки по диагонали через все поле рисунка.
Задание 2
Написать программы для рисования следующих рисунков на всю ширину поля, используя вспомогательные алгоритмы (подпрограммы).
Задание 3
Описать подпрограмму для рисования следующей фигуры.
Задание 4
Используя подпрограмму из предыдущего задания, составить программу для рисования «забора» через все поле рисунка.
Задание 5
Оформить решение задания 4 в виде подпрограммы и с ее помощью составить программу рисования следующей фигуры.
Домашнее задание
Проработать § 10.
Вопросы и задания
1. Приведите примеры процессов обработки информации, которые чаще всего вам приходится выполнять во время учебы. Для каждого примера определите исходные данные, результаты и правила обработки. К каким видам обработки относятся ваши примеры?
2. Если вы решаете задачу по математике или физике и при этом используете калькулятор, то какова ваша функция в этом процессе и какова функция калькулятора?
3. Используя алгоритм Евклида, найдите НОД для чисел 114 и 66. Сколько шагов алгоритма при этом вам пришлось выполнить?
4. Какие проблемы решает теория алгоритмов?
5. Почему калькулятор нельзя назвать алгоритмической машиной, а компьютер можно?
6. Придумайте минимально необходимую систему команд для кассового аппарата, который подсчитывает стоимость покупок и сумму сдачи покупателю. Опишите алгоритм управления работой такого автомата.
Дата добавления: 2020-11-15; просмотров: 131; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!