 |
Обработка информации.
|
|
|
|
Обработка информации - третий вид информационных процессов. Вот хорошо вам знакомый пример - решение математической задачи: даны значения длин двух катетов прямоугольного треугольника, нужно определить его третью сторону - гипотенузу. Чтобы решить задачу, ученик кроме исходных данных должен знать математическое правило, с помощью которого можно найти решение. В данном случае это теорема Пифагора: "квадрат гипотенузы равен сумме квадратов катетов". Применяя эту теорему, получаем искомую величину. Здесь обработка заключается в том, что новые данные получаются путем вычислений, выполненных над исходными данными.
Вычисление - лишь один из вариантов обработки информации. Новую информацию можно вывести не только путем математических расчетов. Вспомните истории Шерлока Холмса, героя книг Конан Дойля. Имея в качестве исходной информации часто очень запутанные показания свидетелей и косвенные улики, Холмс с помощью логических рассуждений прояснял всю картину событий и разоблачал преступника. Логические рассуждения - это еще один способ обработки информации.
Процесс обработки информации не всегда связан с получением каких-то новых сведений. Например, при переводе текста с одного языка на другой происходит обработка информации, изменяющая ее форму, но не содержание.
К этому же виду обработки относится кодирование информации. Кодирование - это преобразование представления информации из одной символьной формы в другую, удобную для ее хранения, передачи или обработки.
Особенно широко понятие кодирования стало употребляться с развитием технических средств хранения, передачи и обработки информации (телеграф, радио, компьютеры). Например, в начале XX века телеграфные сообщения кодировались и передавались с помощью азбуки Морзе. Иногда кодирование производится в целях засекречивания содержания текста. В таком случае его называют шифрованием.
|
|
|
Еще одной разновидностью обработки информации является ее сортировка (иногда говорят - упорядочение). Например, вы решили записать адреса и телефоны всех своих одноклассников на отдельные карточки. В каком порядке нужно сложить эти карточки, чтобы затем было удобно искать среди них нужные сведения? Скорее всего, вы сложите их в алфавитном порядке по фамилиям. В информатике организация данных по какому-либо правилу, связывающему ее в единое целое, называется структурированием.
2) Об алгоритмах
1. Определение алгоритма
Слово «Алгоритм» происходит от algorithmi - латинского написания имени
аль-Хорезми, под которым в средневековой Европе знали величайшего
математика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу,
жившего в 783-850 гг. В своей книге «Об индийском счете» он сформулировал
правила записи натуральных чисел с помощью арабских цифр и правила действий
над ними столбиком. В дальнейшем алгоритмом стали называть точное
предписание, определяющее последовательность действий, обеспечивающую
получение требуемого результата из исходных данных. Алгоритм может быть
предназначен для выполнения его человеком или автоматическим устройством.
Создание алгоритма, пусть даже самого простого, - процесс творческий. Он
доступен исключительно живым существам, а долгое время считалось, что
только человеку. Другое дело - реализация уже имеющегося алгоритма. Ее
можно поручить субъекту или объекту, который не обязан вникать в существо
дела, а возможно, и не способен его понять. Такой субъект или объект
принято называть формальным исполнителем. Примером формального исполнителя
|
|
|
может служить стиральная машина-автомат, которая неукоснительно исполняет
предписанные ей действия, даже если вы забыли положить в нее порошок.
Человек тоже может выступать в роли формального исполнителя, но в первую
очередь формальными исполнителями являются различные автоматические
устройства, и компьютер в том числе. Каждый алгоритм создается в расчете на
вполне конкретного исполнителя. Те действия, которые может совершать
исполнитель, называются его его допустимыми действиями. Совокупность
допустимых действий образует систему команд исполнителя. Алгоритм должен
содержать только те действия, которые допустимы для данного исполнителя.
2. Правила выполнения арифметических операций или геометрическихпостроений представляют собой алгоритмы. При этом остается без ответавопрос, чем же отличается понятие алгоритма от таких понятий, как «метод»,«способ», «правило». Можно даже встретить утверждение, что слова«алгоритм», «способ», «правило» выражают одно и то же (т.е. являютсясинонимами), хотя такое утверждение, очевидно, противоречит “свойствамалгоритма”.
3) Алгоритмические машины
Тео́рия алгори́тмов — наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п.
Развитие теории алгоритмов начинается с доказательства К. Гёделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 г. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем (в частности, проблемы выводимости в исчислении предикатов) вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были разработаны в 30-х годах XX века в работах А. Тьюринга, А. Чёрча и Э. Поста. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу. Основываясь на работах Гёделя, С. Клини ввел понятие рекурсивной функции, также оказавшееся эквивалентным вышеперечисленным.
|
|
|
Одним из наиболее удачных стандартизованных вариантов алгоритма является введённое А. А. Марковым понятие нормального алгорифма. Оно было разработано десятью годами позже работ Тьюринга, Поста, Чёрча и Клини в связи с доказательством алгоритмической неразрешимости ряда алгебраических проблем.
Следует отметить также немалый вклад в теорию алгоритмов, сделанный Д. Кнутом, A. Ахо и Дж. Ульманом. Следует упомянуть и 2 издание книги Алгоритмы: построение и анализ Томаса Х. Кормена, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн.
Алан Тьюринг высказал предположение (известное как Тезис Чёрча — Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.
В течение первого десятилетия истории теории алгоритмов неразрешимые массовые проблемы были обнаружены лишь внутри самой этой теории (сюда относится описанная выше проблема применимости), а также внутри математической логики (проблема выводимости в классическом исчислении предикатов). Поэтому считалось, что теория алгоритмов представляет собой обочину математики, не имеющую значения для таких её классических разделов, как алгебра или анализ. Положение изменилось после того, как А. А. Марков и Э. Л. Пост в 1947 году установили алгоритмическую неразрешимость известной в алгебре проблемы равенства для конечнопорождённых и конечноопределённых полугрупп (т. н. проблемы Туэ). Впоследствии была установлена алгоритмическая неразрешимость и многих других «чисто математических» массовых проблем. Одним из наиболее известных результатов в этой области является доказанная Ю. В. Матиясевичем алгоритмическая неразрешимость десятой проблемы Гильберта.
Домашнее задание: §9 стр. 46-50 вопросы устно.
|
|
|
