Информатика и компьютерные науки (стр. 1 из 14)
Информатика и компьютерные науки.
Информатика - это наука и техника, связанные с машинной обработкой, хранением и передачей информации. Поэтому центральное понятие в информатике - информация. Точное выяснение понятия "информация" существенно необходимо для понимания систем обработки информации. Вообще, понятие "информация" используется нами в разных смыслах. Мы обычно под информацией понимаем высказывания относительно событий, взаимосвязей или состояний реального мира. Н/р "Волга впадает в Каспийское море."
В информатике информацией называется абстрактное содержание какого-либо высказывания, описания, указания (оператора), сообщения. Необходимо отличать информацию, т.е. абстрактное содержание от изображения информации. Н/р математическое понятие "целое число" является абстрактным понятием. Мы изображаем целые числа в виде последовательности цифр из множества {0, 1,... 9}. Можно изобразить целое число римскими цифрами или палочками, насечками. Все это изображения, т.е. внешние формы информации - представления.
Опр. Информацией называют абстрактное содержание ("содержательное значние", "семантика") какого-либо высказывания, описания, указания сообщения или известия. Внешнюю форму изображения называют представлением.
Для машинной обработки информации существует много форм представления информации от условных знаков (сигналов) и произносимых слов до рисунков или последовательностей символов. Все представления (изображения) информации не будут иметь смысла, если не будет известно о значениях представлений. Н/р древние надписи и рисунки. Это внешняя форма. Однако нам неизвестны значения этих изображений, поэтому нам недоступен их смысл, т.е. абстрактное значение информации. Поэтому важно установить способ для выявления значения представления.
Опр. Переход от представления к абстрактной информации, т.е. к значению представления, называют интерпретацией.
Многие формы представления информации допускают различное толкование. Н/р "красный". Только в том случае, когда существуют единые, согласованные интерпретации, возможен обмен информацией. Н/р дорожные знаки.
С другой стороны одно и то же абстрактное содержание м.б. представлено различными способами. Н/р числа.
Выявление подходящих систем представления (языков) для определенных классов информации является одной из задач информатики.
Вопрос об отношении информации к реальности, т.е. является ли информация истинной не рассматривается и не решается в информатике, т.к. ответ на него зависит от субъективного восприятия. Итак, мы различаем в связи с информацией:
- ее представление или изображение (внешняя форма)
- ее значение (собственно "абстрактная" информация)
- ее отношение к реальному миру (связь абстрактной информации с
действительностью.
Информатика включает в себя науку о машинной обработке информации и поэтому в ней рассматриваются вопросы:
- схематизированного представления (изображения) информации: структуры объектов и данных, а также их взаимосвязи;
- правил и предписаний для обработки информации (алгоритмы, вычислительные предписания) и их представления, включая описание протекания работы (процессы).
Оба эти пункта тесно связаны между собой. Программа, например, в качестве своей внешней формы имеет текстовую или графическую структуру. Эта структура, в свою очередь, является объектом для информационной обработки. Но программа, также, представляет собой предписание для обработки информации. При ее выполнении в компьютере протекает процесс действий, который преобразует определенные исходные данные в определенный результат.
В информатике рассматриваются информационные системы вида (A, R, I). Где R - множество представлений с интерпретацией I во множестве A элементов (информаций). Т.о. интерпретации соответствует отображение: I : R -> A (интерпретация I ставит в соответствие данному представлению r некоторое абстрактное информационное содержание I[r].) R также называют системой представления, а A - семантической моделью.
Пример (система представления для натуральных чисел). Пусть N - множество нат. чисел (включая число "нуль"), представляемых числом штрихов, т.е.:
e, ½, ½½, ½½½ …
где через e обозначена пустая последовательность. Интерпретацией I будет отображение десятичного представления в последовательность штрихов.
I : {0, 1, …, 9}+ ® N
I[0]=e, I[1]= ½, I[2]= ½½, …
Этот пример демонстрирует фундаментальную проблему информационной обработки: информация в ее абстрактном виде не может быть записано непосредственно, она всегда может быть только изображена.
Часто в какой-нибудь системе представления имеется много различных изображений одной и той же информации. Эти изображения называются эквивалентными. Точнее говоря, в информационной системе (A, R, I) справедливо: два изображения r1, r2ÎR называются семантически эквивалентными, если они несут одинаковую информацию: I[r1]=I[r2]
Как правило, мы больше заинтересованы в информации, чем в ее представлении. Поэтому часто бывает удобным обходиться с представлением так, как если бы оно было непосредственно информацией. Например: классическая математика.
Обработка информации означает, строго говоря, обработку или преобразование информации. Для этого необходимо, чтобы в применяемой информационной системе была представима любая информация.
Пусть (A, R, I) - информационная система. Если I сюръективно, т.е. для каждой информации аÎА существует представление rÎR с I[r]=a, то каждая информация имеет представление. Обычно представляют интерес ИС обладающие этим свойством.
Отображение на множестве представлений при определенных предположениях индуцирует и отображение информации. Пусть f: R®R отображение на множестве представлений R. Если для всех x, yÎR справедливо:
I[x]=I[y] ® I[f(x)]=I[f(y)] и I сюръективно, то вследствие интерпретации I:R®A однозначным образом устанавливается отображение информации f' : A®A по следующему правилу:
f'(a)=b, если для rÎR справедливо I[r]=a и I[f(r)]=b.
Связь между f и f' и интерпретацией пояснить коммутирующей диаграммой:
R I A  |  |
f f'
R I AТакже справедливо I[f(r)]=f'(I[r]). f' называют абстракцией f.
Итак информация представляется не непосредственно, а лишь изображается каким-либо образом. Однако не все эквивалентные изображения определенной информации одинаково легко интерпретируются или обрабатываются.
Пример: S1/2^i, 0.(9), 0!, 1
Все эти термы имеют значение "один". Однако они различаются с точки зрения простоты, чтения, интерпретации и понимания.
Простота конкретного изображения информации имеет важное значение. Часто подмножество S (изображений простой внешней формы) изображений R выделяется как множество нормальных форм. Тогда S называют системой нормальных форм(СНФ). Если в такой системе для каждого изображения существует по меньшей мере 1 семантически эквивалентная НФ, то СНФ называется полной.
Пусть SÍR - СНФ. Если любое множество изображений с одинаковой интерпретацией имеет единственную НФ, т.е. отображение IS - инъективно, то СНФ называется однозначной.
Т.к. на множестве однозначных НФ интерпретация есть инъективное отображение, то соответствующую информацию по мере надобности можно отождествить с ее НФ.
Формальное понятие алгоритма. Рекурсивные функции. Системы текстовых замен.(СТЗ)
Алгоритмами являются способы решения, описанные с помощью предписаний по обработке, которые удовлетворяют определенным требованиям.
Опр. Алгоритм - это способ с точным (т.е. выраженным в точно определенном языке) конечным описанием применения эффективных (т.е. практически выполнимых) элементарных шагов (переработки).
Это интуитивное понятие алгоритма.
Алгоритмы типичным образом решают не только частные задачи, но и классы задач. Подлежащие решению частные задачи, выделяемые по мере надобности из рассматриваемого класса, определяются с помощью параметров. Параметры играют роль исходных данных для алгоритма. Алгоритмы, как правило, по этим исходным данным доставляют результаты. Эти результаты в случае задач информационной обработки могут быть информацией (вернее, представлением информации) или последовательностью указаний (управляющих сигналов), по которым осуществляются определенные преобразования.
Независимо от формы описания для алгоритмов важно различать следующие аспекты:
постановку задачи, которая должна быть решена с помощью алгоритма;
специфичный способ, каким решается задача, при этом для алгоритма различают:
а) элементарные шаги обработки, которые имеются в распоряжении;
б) описание выбора отдельных подлежащих выполнению шагов.
Свойства алгоритма.
Массовость.
Дискретность - алгоритм представляется в виде конечной последовательности шагов.
Конечность.
Определенность.
Эффективность.
Пример: алгоритм Евклида.
если а=в то НОД(а, в)=а
если а>в то НОД(а, в)=НОД(а-в, в)
если а<в то НОД(а, в)=НОД(а, в-а)
Формальное понятие алгоритмов тесно связано с понятиями рекурсивных функций, машин Тьюринга, нормальных алгоритмов Маркова (или СТЗ).
Алгоритм называется терминистическим, если он завершается за конечное число шагов. Детерминистическим, если нет свободы в выборе очередного шага алгоритма. Детерминированным, если независимо от последовательности выполняемых шагов, результат определяется однозначно.
Существование или не существование алгоритма может быть установлено, если найти такой математический объект, который будет существовать в точности тогда, когда и алгоритм. Таким математическим объектом может быть рекурсивная функция. Функция определяется однозначно, если известен закон, по которому каждому набору х1, …, хn ставится в соответствие 1 значение функции y. Закон может быть произвольным, в т.ч. это может быть алгоритм вычисления значения функции. В этом случае функцию называют вычислимой, а алгоритм, по которому вычисляется функция, называется алгоритмом, сопутствующим рекурсивной функции. Рекурсивные функции являются частным классом вычислимых функций.