Основы Pascal. Типы данных. Структура программы на языке Pascal

Вид материала

Документы

Содержание Классификация информационных систем. Функции информационных систем. Структура информационных систем (подсистемы обеспечения). Техническое обеспечение Математическое обеспечение Энтропия как мера информации. Знания и три типа отношений знаков Понятие алгоритма и его свойства. Классы алгоритмических задач.

Подобный материал:

• Компоновать программы из отдельных частей отлаживать программы выполнять программы., 197.76kb.
• Borland Turbo Pascal, знать простые основные алгоритмы работы с простыми типами данных, 316.19kb.
• Программирование на языке высокого уровня, 59.92kb.
• Задачи работы Научиться создавать программы на языке Turbo Pascal с использованием, 598.05kb.
• Курс «Программирование на языке Turbo Pascal 0» Цель курса, 19.6kb.
• Borland Turbo Pascal, знать простые основные алгоритмы работы с простыми типами данных, 324.26kb.
• Правила преобразований из одного типа в другой и правила приведения типов в языке Object, 19.03kb.
• Информатика Ответы на вопросы, 913.15kb.
• Конспект урока по информатике для десятого класса по теме «Условный оператор в Turbo, 32.44kb.
• Доманская Юлия Георгиевна г. Вилейка 2006г пояснительная записка, 74.95kb.

Понятия информации, системы, автоматизированной информационной системы.

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

Система — образующая единое целое совокупность взаимодействующих объектов, объединенная некоторыми общими свойствами и условиями функционирования.

Информационная система (ИС) — система, предназначенная для получения, хранения, обработки и выдачи информации, т.е. система, основным предметом и продуктом функционирования которой является информация.

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

Методологию разработки АИС можно разделить на две составляющие. Апрагматическая методология – конструктивная часть методологии разработки АИС, которая отвечает на вопрос «что проектируется?» или «что моделируется?». В рамках данной методологии решаются задачи параметрического синтеза и анализа. Прагматическая методология   дескриптивная часть методологии, описывающая процесс разработки АИС, как систематической процедуры, отвечающая на вопрос «как проектировать?», «какую модель (модели) представления использовать?». С прагматической методологией, как правило, связаны такие исследования как инженерное проектирование, представление моделей знаний и технология разработки. При разработке АИС обычно начинают с определения желательных характеристик (апрагматическая составляющая методологии), а затем конструируют мыслительный процесс (прагматическая составляющая методологии), необходимый для получения нужного результата. Таким образом, о желательных свойствах результата обычно известно больше, чем о самом процессе.

Основным недостатком апрагматической методологии является её направленность на решение ограниченного круга выделенных технических проблем, связанных с формальным представлением именно объекта разработки как технической системы. В противовес технической, объектной «приземленности» апрагматической методологии прагматическая парадигма уходит в другую крайность – область теоретических концепций построения системы «идеальных» планов действий. Основной системой исследования является «система технологических действий», при этом объект разработки рассматривается как инертный выходной продукт процесса разработки.

9. Классификация информационных систем.
   

Большинство ИС в действительности являются системами обработки данных (СОД). По степени механизации процедур преобразования информации выделяют следующие виды СОД.

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

Механизированные СОД. В данном случае для выполнения некоторых процедур преобразования данных используются технические средства.

Автоматизированные СОД. Часть процедур преобразования данных выполняется без участия человека, причем механизируются не только отдельные процедуры преобразования, но и переходы от предыдущей процедуры к последующей.

Системы автоматической обработки данных. В таких системах все процедуры преобразования данных и переходы между ними выполняются автоматически, без участия человека.

По характеру использования результатной информации ИС делятся на:

информационно-поисковые, предназначенные для сбора, хранения и выдачи информации по запросу пользователя;

информационно-советующие, предлагающие пользователю определенные рекомендации для принятия решений;

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

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

9. Функции информационных систем.
   

В контексте процесса управления выделяют следующие основные функции ИС:

вычислительную — своевременное и качественное выполнение обработки информации во всех интересующих систему управления аспектах;

коммуникационную — обеспечение оперативной передачи информации в заданные пункты;

информирующую — обеспечение быстрого доступа, поиск и выдача необходимой информации всех видов;

запоминающую — выполнение непрерывного накопления, систематизации, хранения и обновления всей необходимой информации;

следящую — отслеживание и формирование всей необходимой для управления внешней и внутренней информации;

регулирующую — осуществление информационно-управляющих воздействий на объект управления при отклонении параметров его функционирования от заданных (запланированных) значений;

оптимизирующую — обеспечение оптимальных плановых расчетов и перерасчетов по мере изменения целей, критериев и условий функционирования объекта;

самоорганизующуюся — гибкое изменение структуры и параметров ИС для достижения вновь поставленных целей;

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

анализирующую — определение основных показателей функционирования объекта управления;

диагностическую — диагностики состояния объекта управления;

прогнозирующую — выявление основных тенденций, закономерностей и показателей развития объекта и окружающей среды;

документирующую — формирование всех необходимых видов документов.

9. Структура информационных систем (подсистемы обеспечения).
   

ИС может включать в себя различные подсистемы, состав и взаимодействие которых позволяет обеспечить реализацию её функций. Выделяют следующие виды подсистем: функциональные, обеспечивающие и организационные. Функциональные подсистемы ИС реализуют и поддерживают модели, методы и алгоритмы получения управляющей информации. Обеспечивающие подсистемы включают в себя следующие составляющие.

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

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

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

Математическое обеспечение — совокупность математических методов, моделей и алгоритмов обработки информации, используемых в системе.

Лингвистическое обеспечение — совокупность языковых средств, используемых в системе с целью повышения качества её разработки и облегчения общения человека с машиной.

Организационные подсистемы включают:

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

Эргономическое обеспечение — совокупность методов и средств, используемых при разработке и функционировании ИС, создающих оптимальные условия для деятельности персонала и быстрейшего освоения системы.

Правовое обеспечение — совокупность правовых норм, регламентирующих создание и функционирование ИС, а также порядок получения, преобразования и использования информации.

Организационное обеспечение — комплекс решений, регламентирующих процессы создания и функционирования как системы в целом, так и её персонала.

9. Энтропия как мера информации.
   

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

Определение количества информации на синтаксическом уровне основывается на понятии неопределенности состояния (энтропии) системы. Получение информации связано с изменением степени неосведомленности получателя о состоянии системы. До получения информации получатель мог иметь некоторые предварительные (априорные) сведения о системе α. Мера неосведомленности о системе H(α) и является для него мерой неопределенности состояния системы. После получения некоторого сообщения β получатель приобретает дополнительную информацию I_β(α), уменьшающую его априорную неосведомленность так, что апостериорная (после получения сообщения β) неопределенность состояния системы становится H(α/β). Тогда количество информации I_β(α) о системе α, полученное в сообщении β, определяется как I_β(α) = H(α)   H(α/β).

Если конечная неопределенность H(α/β) обратится в нуль, то первоначальное неполное знание заменится полным знанием и количество информации станет равно I_β(α) = H(α). Другими словами, энтропия системы H(α) может рассматриваться как мера недостающей информации. Энтропия системы H(α), имеющей N возможных состояний, согласно формуле Шеннона равна



где P_i — вероятность того, что система находится в i-м состоянии. Для случая, когда все состояния системы равновероятны, т.е. P_i=1/N, её энтропия равна



Пусть по каналу связи передается n-разрядное сообщение, использующее m различных символов, так что количество всевозможных кодовых комбинаций будет N=mⁿ. При равновероятном появлении любой кодовой комбинации количество информации в правильном сообщении выражается формулой Хартли: Если в качестве основания логарифма принять m, то I=n. В данном случае количество информации (при условии полного априорного незнания получателем содержания сообщения) будет равно объему данных, т.е. I=V_D. Для неравновероятных состояний системы всегда I=V_D, V_D=n.

Степень информативности сообщения Y определяется отношением количества информации к объему данных, т.е. Y=I/V_D, причем 0< Y <1. Y характеризует лаконичность сообщения. С увеличением Y уменьшаются объемы работы по преобразованию информации (данных) в системе.

9. Знания и три типа отношений знаков.
   

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

Укажем три типа отношений знаков и знаковых конструкций, фиксирующих и выражающих знания.

Семантические отношения - правила установления смысла и значения знака или знаковой конструкции. Знак и знаковая конструкция обозначают некую вещь, процесс, предмет, ситуацию, действие или систему действий, каждый знак или знаковая конструкция должны иметь смысл и значение, чтобы расцениваться как средство выражения знаний.

Синтаксические отношения – правила синтаксиса между знаковыми конструкциями. Они указывают, как из одних осмысленных выражений получить другие, тоже осмысленные, с более или менее определенным значением.

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

Одна из ключевых проблем, возникающих при разработке интеллектуальных информационных систем, состоит в необходимости выбора и реализации способа представления знаний. Модель (представления) знаний определяет способ формального описания знаний. К основным моделям представления знаний относятся: логические, продукционные, фреймовые, сетевые.

В логических моделях знания представляются в виде совокупности правильно построенных формул какой-либо формальной системы (ФС), которая задается четверкой (T, P, A, R), где T — множество базовых (терминальных) элементов, из которых формируются все выражения ФС, P — множество синтаксических правил, определяющих синтаксически правильные выражения из терминальных элементов ФС, A — множество аксиом ФС, соответствующих синтаксически правильным выражениям, которые в рамках данной ФС априорно считаются истинными, R — конечное множество правил вывода, позволяющих получать из одних синтаксически правильных выражений другие.

Простейшей логической моделью является исчисление высказываний. Аксиоматический базис исчисления высказываний (множество A) составляет совокупность правильно построенных формул, являющихся тождественно истинными. В качестве правил вывода исчисления высказываний (множество R) обычно используют два: правило отделения (если X и X→Y — истинные формулы, то Y также истинна) и правило подстановки, разрешающее в правильно построенных формулах заменять все вхождения одного высказывания на другое. Как самостоятельная модель представления знаний логика высказываний бедна выразительными средствами: её возможностей достаточно лишь для описания связей между высказываниями, рассматриваемыми как неразделенное целое.

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

9. Основные этапы развития программного обеспечения.
   

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

Кодирование. Взаимодействие человека и ЭВМ осуществлялось посредством машинных кодов, т.е. на языке ЭВМ.

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

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

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

Интегрированные системы. Целью создания интегрированных систем является объединение наиболее часто используемых прикладных программ. Хорошая интегрированная система должна включать следующие прикладные системы общего назначения: пакет текстовой и графической обработки, электронные таблицы, базу данных, коммуникационный пакет.

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

9. Понятие алгоритма и его свойства. Классы алгоритмических задач.
   

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

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

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

реалистичность — возможность реализации алгоритма при заданных ограничениях: временных, программных, аппаратных;

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

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

дискретность — допустимость расчленения алгоритма на отдельные этапы с возможностью последовательной их реализации на машине;

экономичность — алгоритм должен обеспечивать необходимую и достаточную точность решения задачи.

Компьютер может реализовать только такие процедуры, которые представимы в виде алгоритмов. Исходному алгоритму решения задачи на компьютере соответствуют следующие «виды» алгоритмов: алгоритм, сформулированный на том или ином языке программирования, который затем трансформируется в набор предопределенных (встроенных) алгоритмов ОС, преобразуемых в заключении в последовательность элементарных операций процессора.

Все алгоритмические задачи принято делить на два больших класса: первый – это задачи, связанные с вычислением значения функции; второй – задачи, связанные с распознаванием принадлежности объекта заданному множеству (что равносильно получению ответа на вопрос: обладает ли объект заданным свойством?). Выделение двух классов задач приводит к двум важным понятиям теории алгоритмов – вычислимая функция и разрешимое множество. Функция называется вычислимой, если имеется алгоритм, позволяющий найти (вычислить) её значение. Множество называется разрешимым, если имеется алгоритм, который для любого объекта позволяет определить, принадлежит он данному множеству или нет.

(возможно след-е -а пункта не нужно)

Проблема алгоритмической разрешимости.

Имеются задачи, для которых алгоритм вообще не может быть построен. В связи с этим возникает вопрос: возможно ли, не решая задачи, доказать, что она алгоритмически неразрешима, т.е. что нельзя построить алгоритм, который обеспечил бы её общее решение? Ответ на этот вопрос важен и с практической точки зрения, поскольку бессмысленно пытаться решать задачу на компьютере и разрабатывать для неё программу, если доказано, что она алгоритмически неразрешима. Задача считается алгоритмически неразрешимой, если не существует алгоритмической модели, которая обеспечивает её решение.

В теории алгоритмов к алгоритмически неразрешимой относится «проблема остановки»: можно ли по описанию алгоритма и входным данным установить, завершится ли выполнение алгоритма результативной остановкой? Эта проблема имеет ясную программистскую интерпретацию. Часто ошибки разработки приводят к зацикливанию, т.е. ситуации, когда цикл не завершается и не происходит завершения работы программы и остановки. Неразрешимость проблемы остановки означает, что нельзя создать общий, т.е. пригодный для любой программы алгоритм отладки. Неразрешимой является и проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который для любых двух алгоритмов (программ) выяснял бы, всегда ли они приводят к одному и тому же результату или нет.

Важность доказательства алгоритмической неразрешимости в том, что если оно получено, то имеет смысл закона-запрета, позволяющего не тратить усилия на поиск решения. Однако алгоритмическая неразрешимость какой-либо задачи в общей постановке не исключает возможности того, что разрешимы какие-то частные её случаи. Справедливо и обратное утверждение: решение частного случая задачи еще не дает повода считать возможным её решение в самом общем случае, т.е. не свидетельствует о её общей алгоритмической разрешимости.

Понятие сложности алгоритма.

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

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

Задача считается трудноразрешимой, если для неё не удается построить полиномиального алгоритма. В общем случае эффективно исполняемыми можно считать полиномиальные алгоритмы с функциями сложности n, n² или n³. Например, при решении задачи поиска нужного данного из n имеющихся в худшем варианте сложность равна n. Задача ранжирования, т.е. расстановки в заданном порядке n однотипных данных приводит к полиному 2-й степени. Сложность задачи вычисления определителя системы n линейных уравнений с n неизвестными характеризуется полиномом 3-й степени. Повышение быстродействия элементов компьютера уменьшает время исполнения алгоритма, но не уменьшает степень полинома сложности.