1   2   3   4   5   6   7
Ім'я файлу: Информатика.doc
Розширення: doc
Розмір: 508кб.
Дата: 14.12.2020
скачати
Пов'язані файли:
реферат Правила торгівлі на ринках.doc
ПК науки.doc
науки.doc
Zadacha_1_ (3).doc

Информатика и компьютерные науки.

Информатика - это наука и техника, связанные с машинной обработкой, хранением и передачей информации. Поэтому центральное понятие в информатике - информация. Точное выяснение понятия "информация" существенно необходимо для понимания систем обработки информации. Вообще, понятие "информация" используется нами в разных смыслах. Мы обычно под информацией понимаем высказывания относительно событий, взаимосвязей или состояний реального мира. Н/р "Волга впадает в Каспийское море."

В информатике информацией называется абстрактное содержание какого-либо высказывания, описания, указания (оператора), сообщения. Необходимо отличать информацию, т.е. абстрактное содержание от изображения информации. Н/р математическое понятие "целое число" является абстрактным понятием. Мы изображаем целые числа в виде последовательности цифр из множества {0, 1,... 9}. Можно изобразить целое число римскими цифрами или палочками, насечками. Все это изображения, т.е. внешние формы информации - представления.

Опр. Информацией называют абстрактное содержание ("содержательное значние", "семантика") какого-либо высказывания, описания, указания сообщения или известия. Внешнюю форму изображения называют представлением.

Для машинной обработки информации существует много форм представления информации от условных знаков (сигналов) и произносимых слов до рисунков или последовательностей символов. Все представления (изображения) информации не будут иметь смысла, если не будет известно о значениях представлений. Н/р древние надписи и рисунки. Это внешняя форма. Однако нам неизвестны значения этих изображений, поэтому нам недоступен их смысл, т.е. абстрактное значение информации. Поэтому важно установить способ для выявления значения представления.

Опр. Переход от представления к абстрактной информации, т.е. к значению представления, называют интерпретацией.

Многие формы представления информации допускают различное толкование. Н/р "красный". Только в том случае, когда существуют единые, согласованные интерпретации, возможен обмен информацией. Н/р дорожные знаки.

С другой стороны одно и то же абстрактное содержание м.б. представлено различными способами. Н/р числа.

Выявление подходящих систем представления (языков) для определенных классов информации является одной из задач информатики.

Вопрос об отношении информации к реальности, т.е. является ли информация истинной не рассматривается и не решается в информатике, т.к. ответ на него зависит от субъективного восприятия. Итак, мы различаем в связи с информацией:

- ее представление или изображение (внешняя форма)

- ее значение (собственно "абстрактная" информация)

- ее отношение к реальному миру (связь абстрактной информации с

действительностью.

Информатика включает в себя науку о машинной обработке информации и поэтому в ней рассматриваются вопросы:

- схематизированного представления (изображения) информации: структуры объектов и данных, а также их взаимосвязи;

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

Оба эти пункта тесно связаны между собой. Программа, например, в качестве своей внешней формы имеет текстовую или графическую структуру. Эта структура, в свою очередь, является объектом для информационной обработки. Но программа, также, представляет собой предписание для обработки информации. При ее выполнении в компьютере протекает процесс действий, который преобразует определенные исходные данные в определенный результат.

В информатике рассматриваются информационные системы вида (A, R, I). Где R - множество представлений с интерпретацией I во множестве A элементов (информаций). Т.о. интерпретации соответствует отображение: I : R -> A (интерпретация I ставит в соответствие данному представлению r некоторое абстрактное информационное содержание I[r].) R также называют системой представления, а A - семантической моделью.

Пример (система представления для натуральных чисел). Пусть N - множество нат. чисел (включая число "нуль"), представляемых числом штрихов, т.е.:

, , ,  …

где через  обозначена пустая последовательность. Интерпретацией I будет отображение десятичного представления в последовательность штрихов.

I : {0, 1, …, 9}+  N

I[0]=, 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.

Итак информация представляется не непосредственно, а лишь изображается каким-либо образом. Однако не все эквивалентные изображения определенной информации одинаково легко интерпретируются или обрабатываются.

Пример: 1/2^i, 0.(9), 0!, 1

Все эти термы имеют значение "один". Однако они различаются с точки зрения простоты, чтения, интерпретации и понимания.

Простота конкретного изображения информации имеет важное значение. Часто подмножество S (изображений простой внешней формы) изображений R выделяется как множество нормальных форм. Тогда S называют системой нормальных форм(СНФ). Если в такой системе для каждого изображения существует по меньшей мере 1 семантически эквивалентная НФ, то СНФ называется полной.

Пусть SR - СНФ. Если любое множество изображений с одинаковой интерпретацией имеет единственную НФ, т.е. отображение IS - инъективно, то СНФ называется однозначной.

Т.к. на множестве однозначных НФ интерпретация есть инъективное отображение, то соответствующую информацию по мере надобности можно отождествить с ее НФ.

Формальное понятие алгоритма. Рекурсивные функции. Системы текстовых замен.(СТЗ)

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

Опр. Алгоритм - это способ с точным (т.е. выраженным в точно определенном языке) конечным описанием применения эффективных (т.е. практически выполнимых) элементарных шагов (переработки).

Это интуитивное понятие алгоритма.

Алгоритмы типичным образом решают не только частные задачи, но и классы задач. Подлежащие решению частные задачи, выделяемые по мере надобности из рассматриваемого класса, определяются с помощью параметров. Параметры играют роль исходных данных для алгоритма. Алгоритмы, как правило, по этим исходным данным доставляют результаты. Эти результаты в случае задач информационной обработки могут быть информацией (вернее, представлением информации) или последовательностью указаний (управляющих сигналов), по которым осуществляются определенные преобразования.

Независимо от формы описания для алгоритмов важно различать следующие аспекты:

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

специфичный способ, каким решается задача, при этом для алгоритма различают:

а) элементарные шаги обработки, которые имеются в распоряжении;

б) описание выбора отдельных подлежащих выполнению шагов.

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

Массовость.

Дискретность - алгоритм представляется в виде конечной последовательности шагов.

Конечность.

Определенность.

Эффективность.

Пример: алгоритм Евклида.

если а=в то НОД(а, в)=а

если а>в то НОД(а, в)=НОД(а-в, в)

если а<в то НОД(а, в)=НОД(а, в-а)

Формальное понятие алгоритмов тесно связано с понятиями рекурсивных функций, машин Тьюринга, нормальных алгоритмов Маркова (или СТЗ).

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

Существование или не существование алгоритма может быть установлено, если найти такой математический объект, который будет существовать в точности тогда, когда и алгоритм. Таким математическим объектом может быть рекурсивная функция. Функция определяется однозначно, если известен закон, по которому каждому набору х1, …, хn ставится в соответствие 1 значение функции y. Закон может быть произвольным, в т.ч. это может быть алгоритм вычисления значения функции. В этом случае функцию называют вычислимой, а алгоритм, по которому вычисляется функция, называется алгоритмом, сопутствующим рекурсивной функции. Рекурсивные функции являются частным классом вычислимых функций.

РФ строится здесь на множестве целых неотрицательных чисел следующим образом: задаются 3 базовые РФ, для которых сопутствующие алгоритмы - одношаговые. Затем используются 3 приема, называемые операторами подстановки, рекурсии и минимизации, с помощью которых на основе базовых функций строятся более сложные РФ. По существу эти операторы - алгоритмы, комбинируя которые получают более сложные алгоритмы.

Простейшие базовые функции:

Функция произвольного количества аргументов тождественно =0. Знак функции n - где n - количество аргументов.
Сопутствующий алгоритм: если знак функции n то значение функции 0.
Например: 1(3)=0, 3(4, 56, 78)=0;

Тождественная функция. Знак функции n,i . 0Например: 3,2(3,22,54)=22;

Функция получения последователя. Функция одного независимого аргумента. Знак функции - . Сопутствующий алгоритм: если знак функции  то значение функции - число, следующее за значением аргумента.
Например: (5)=6 или 5'=6.

3 приема построения сложных РФ.

Оператор подстановки. F(f1, …, fn).
Вычисляются значения функций f1, …, fn и используются как аргументы при вычислении F.
(y)= ((y))= (y')=y''.

Оператор рекурсии R. f::= R[f1, f2, x(y)].

f - функция n аргументов, f1 - n-1 аргумента, f2 - n+1 аргумента, причем n-1 аргументов функций совпадают, а 2 следующих аргументов называются дополнительными. Один из них - х - называется главным доп. аргументом(ГДЭ). Он войдет в определяющую функцию. Другой y - вспомогательный доп. аргумент(ВДЭ), использующийся при построении новой функции.

Говорят, что оператор рекурсии строит новую функцию по 2 условиям:

f(0)=f1, f(i')=f2(i, f(i)).

Значением искомой функции при нулевом значении ГДЭ считать значение функции f1, а значением новой функции для каждого последующего значения ГДЭ считать значение функции f2 для предыдущего значения ГДЭ и для значения ВДЭ, совпадающего со значением искомой функции на предыдущем шаге.

Например:

PR(x) ::= R[0,2,1(x,y),x(y)]

PR(0) = 0 = 0

PR(1) = 2,1(0,PR(0))= 0

PR(2) = 2,1(1,PR(1)) = 1

Оператор минимизации или построение по первому нулю.

f ::=[f1, (x)] f(x1, …, xn)=(f1(x1, …, xn, y), (y))

с помощью функции f1 n+1 аргументов и дополнительного исчезающего аргумента.

Придавать последнему аргументу значения начиная с нуля, вычисляя при этом значение функции f1. Как только значение функции f1=0 значение дополнительного аргумента принимаем за значение искомой функции для тех главных аргументов, для которых вычислялось значение функции f1.

Например:

r(x)::=(2,1(x, y), (y)]

r(0)=0

r(i) = 2,1(i, y) - не определено для i<>0.

Все базовые функции и построенные без оператора минимизации определены для всех значений дополнительных аргументов. Функции, построенные с помощью оператора минимизации могут быть определены не для всех значений исходных данных. Большинство известных математических функций - рекурсивные.

Например:

y=x+1 - совпадает с базовой.

w=x+y - подстановка в (z+1) вместо z функции 3,3 (x, y, z). Получим f*(x, y, z)

Затем воспользуемся следующим:

S(x, y) ::= f1[1,1(x), f*(x, y, z); y(z)]

S(x, 0) =1,1 (x) = x

s(x, 1) = f*(x, 0, S(x, 0)) = s(x, 0) + 1

Класс вычислимых функций исчерпывается классом РФ. Каков бы ни был алгоритм, перерабатывающий последовательность целых неотрицательных чисел в целые неотрицательные числа найдется сопутствующий некоторой РФ алгоритм, эквивалентный данному и наоборот. Если нельзя построить РФ, то нельзя разработать алгоритм решения задачи.
. Формальное описание алгоритма через замену текстов

Для точного описания алгоритма (которое допускает машинную обработку, переработку и выполнение) требуется формальный язык (подмножество из V* с заданным набором знаков V) для записи алгоритмов и точное определение понятия эффективности (выполнимости) элементарных шагов переработки. В простейшем случае алгоритмы в качестве входа и выхода используют слова над некоторым набором знаков. Поскольку в виде слов может быть представлена самая различная информация, можно считать, что алгоритмы всегда оперирует со словами.

Одной из простейших концепций элементарных шагов переработки последовательностей знаков является замена определенных подслов (образцов) в обрабатываемом слове другими словами. Эта концепция ведет к алгоритмам в форме систем текстовых замен на последовательнос­тях знаков.

Пусть V - запас знаков. Пара (v, w) e V* х V* называется заменой над V. Замена часто записывается в виде

v  w

Конечное множество R замен будем в дальнейшем называть системой текстовых замен (СТЗ) над V. Элементы этой системы будем называть также правилами текстовых замен (ПТЗ). СТЗ служат для представления алгоритмов. Отдельные шаги этих алгоритмов состоят, таким образом, в применении правил замен.

Замена

s  t

называется применением правила v  w, если имеются слова a, v, w, z  V* такие, что справедливо

s = а ° v ° z, t = а ° w ° z.

Слово s  V* называется терминальным (или терминалом} в R, если не существует слова t  V* такого, что справедливо следующее: замена

st

является применением какого-либо правила из R. Таким образом, к терминальному слову s нельзя больше применить никакого правила замены.

Через повторное применение ПТЗ, исходя из начально заданного слова t0, возникают вычисления. Если t0, t1, ..., tn принадлежат V* и

ti-->ti+1

есть применение правила г из R для всех i,0<=i<=n, то последо­вательность (tj) 1<=i<=n называют (конечным) вычислением (последовательностью вычислении) над R для t0. Часто вычисление записывается следующим образом:

t0  t1 … tn

Слово t0 называется также входом для вычисления. Если tn есть терминал, то вычисление называется завершающимся (конечным) с результатом tn. Слово tn называется также выходом для R при входе t0. Бесконечное вычисление (последовательность вычислений) (ti)iN из слов ti V*, для которых ti-->ti+1 есть применение правил замен из R для всех i  N, называется незавершающимся (бесконечным) вычислением.

Пример (вычисления по СТЗ).

(1) Для системы текстовых замен Q над множеством символов {L, О}, которая состоит из следующих правил:

LL  е, О  е, через последовательность

LOLL  LO  L

задается завершающееся вычисление для входного слова с результатом .

(2) Для СТЗ над {L, О}, состоящей из правил О  OO, О L,

для входа последовательность вычислений О  OO  OL  LL

является завершающимся вычислением с выходом , а последовательность

о ->. оо -> ооо ->. оооо ->...

является незавершающимся вычислением.

Система текстовых замен R в силу следующего предписания определяет алгоритм текстовых замен (АТЗ), который использует слова над V в качестве входа и выхода. Для входного слова t  V* алгоритм работает следующим образом:

"Если одно из правил множества R применимо к слову t (т. e. существует слово s  V*, для которого имеет место: l -» s есть применение правила из R), то примени правило к t и затем примени снова этот же алгоритм к слову s; в противном случае прекрати выполнение алгоритма".

Слово t служит входом для алгоритма; если (после конечного числа шагов) возникает терминальное слово, т. e. слово, к которому неприменимо никакое правило, то это слово является выходом (результатом вычислений). Если такая ситуация никогда не возникает, то алгоритм не завершается. Алгоритмы, определенные таким образом с помощью СТЗ, всегда являются последовательными. При этом выбор применяемого правила является недетермннистическим.

Часто для АТЗ в качестве входов используют только слова совершенно определенной формы (нормальная форма). Определенные знаки не входят в эти слова (а также и в выходные слова) - эти знаки, используются исключительно как вспомогательные знаки в словах, возникающих в процессе вычислений.

Примеры (алгоритмы текстовых замен).

(1) Сложение двух натуральных чисел, представленных в виде количества штрихов

Натуральное число представляется в виде количества штрихов с ограничительными скобками, т. e. число nN представляется словом <| |...|>, причем внутрь скобок входит n штрихов. В этом случае алгоритм состоит из одного единственного правила замены (е обозначает пустое слово):

> + <  е

Для входа <|...|> + <|...|> алгоритм дает сумму штрихов.

(2) Умножение двух натуральных чисел (в таком же представлении)

Применяются вспомогательные знаки d, e, m. Алгоритм состоит из следующих правил замен:

|>*<  >*
d| . |md

dm  md

d>  >

<>*< 
e|  e

em  |e

e>  >

Для входного слова <|...|> * <|...|> с п1 штрихами в первом операнде и п2 штрихами во втором операнде алгоритм дает выходное слово <|...1> с п1 * п2 штрихами.

Последовательности, образованные из вспомагательных знаков, пред­ставляют вполне определенные ситуации в вычислениях. Возникающие слова могут трактоваться снова как (усложненные) представления чисел.

Для входа <||> * <|||> возникает показанный на рисунке граф возможных вычислении. Все вычисления заканчиваются получением слова <|||||| >. Этот алгоритм подстановки недетерминистический, но детерминированный, т. е. дает, несмотря на различные вычисления, всегда один и тот же результат.


  1   2   3   4   5   6   7

скачати

© Усі права захищені
написати до нас