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, r2R называются семантически эквивалентными, если они несут одинаковую информацию: I[r1]=I[r2] Как правило, мы больше заинтересованы в информации, чем в ее представлении. Поэтому часто бывает удобным обходиться с представлением так, как если бы оно было непосредственно информацией. Например: классическая математика. Обработка информации означает, строго говоря, обработку или преобразование информации. Для этого необходимо, чтобы в применяемой информационной системе была представима любая информация. Пусть (A, R, I) - информационная система. Если I сюръективно, т.е. для каждой информации аА существует представление rR с I[r]=a, то каждая информация имеет представление. Обычно представляют интерес ИС обладающие этим свойством. Отображение на множестве представлений при определенных предположениях индуцирует и отображение информации. Пусть f: RR отображение на множестве представлений R. Если для всех x, yR справедливо: I[x]=I[y] I[f(x)]=I[f(y)] и I сюръективно, то вследствие интерпретации I:RA однозначным образом устанавливается отображение информации f' : AA по следующему правилу: f'(a)=b, если для rR справедливо 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 семантически эквивалентная НФ, то СНФ называется полной. Пусть SR - СНФ. Если любое множество изображений с одинаковой интерпретацией имеет единственную НФ, т.е. отображение 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* такого, что справедливо следующее: замена st является применением какого-либо правила из 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)iN из слов ti V*, для которых ti-->ti+1 есть применение правил замен из R для всех i N, называется незавершающимся (бесконечным) вычислением. Пример (вычисления по СТЗ). (1) Для системы текстовых замен Q над множеством символов {L, О}, которая состоит из следующих правил: LL е, О е, через последовательность LOLL LO L задается завершающееся вычисление для входного слова (2) Для СТЗ над {L, О}, состоящей из правил О OO, О L, для входа является завершающимся вычислением с выходом о ->. оо -> ооо ->. оооо ->... является незавершающимся вычислением. Система текстовых замен R в силу следующего предписания определяет алгоритм текстовых замен (АТЗ), который использует слова над V в качестве входа и выхода. Для входного слова t V* алгоритм работает следующим образом: "Если одно из правил множества R применимо к слову t (т. e. существует слово s V*, для которого имеет место: l -» s есть применение правила из R), то примени правило к t и затем примени снова этот же алгоритм к слову s; в противном случае прекрати выполнение алгоритма". Слово t служит входом для алгоритма; если (после конечного числа шагов) возникает терминальное слово, т. e. слово, к которому неприменимо никакое правило, то это слово является выходом (результатом вычислений). Если такая ситуация никогда не возникает, то алгоритм не завершается. Алгоритмы, определенные таким образом с помощью СТЗ, всегда являются последовательными. При этом выбор применяемого правила является недетермннистическим. Часто для АТЗ в качестве входов используют только слова совершенно определенной формы (нормальная форма). Определенные знаки не входят в эти слова (а также и в выходные слова) - эти знаки, используются исключительно как вспомогательные знаки в словах, возникающих в процессе вычислений. Примеры (алгоритмы текстовых замен). (1) Сложение двух натуральных чисел, представленных в виде количества штрихов Натуральное число представляется в виде количества штрихов с ограничительными скобками, т. e. число nN представляется словом <| |...|>, причем внутрь скобок входит 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 |