3.12 Прикладное программное обеспечение

Прикладное программное обеспечение (ППО) составляют программы конечного пользователя. По назначению этих программ ППО разделяют на прикладные программы общего

и специального назначения (см. рис. 3.6).

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

Программы обработки текстов. Это текстовые редакторы и текстовые процессоры. Граница между ними весьма условна. Текстовые редакторы (NotePad) способны выполнять основные функции редактирования: набор, внесение исправлений, сохранение, работа с фрагментами. Текстовые процессоры (Word), кроме того, имеют возможности разнообразного оформления текста. Наконец, издательские системы отличаются расширенными средствами управления взаимодействия текста с параметрами страницы и графическими объектами.

Электронные таблицы. Их основное назначение – обработка различных типов данных, представленных в табличной форме (Excel, Lotus). Основное преимущество электронных таблиц по сравнению с текстовыми процессорами в том, что содержание одних ячеек может меняться автоматически в соответствии с содержанием других. Таким образом, в ячейках электронных таблиц могут храниться формулы. Эти таблицы находят широкое применение в бухучёте, анализе финансовых и торговых рынков, средствах обработки различных экспериментов в части автоматизации регулярно повторяемых вычислений больших объёмов данных, представляющих табличные структуры.

Системы управления базами данных (СУБД). Программы этого типа (Access) позволяют работать с большими объёмами структурированных данных. В функции СУБД входит: описание данных, доступ к ним, поиск и отбор данных по определённым критериям. Они составляют основу информационных систем и позволяют работать в компьютерных сетях.

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

Интегрированные программные средства. Наиболее распространённый продукт этого класса – пакет MS Office, который кроме текстового процессора MS Word, табличного процессора MS Excel и СУБД MS Access интегрирует в себе офисные программные средства – систему разработки презентаций MS Power Point, электронный организатор MS Outlook.

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

3.12.2. ППО специального назначения. Эти программы решают задачи профессионального характера в различных предметных областях. Информационные системы применяются для организации документооборота на предприятиях, бухгалтерском учёте, управлении финансовой деятельностью, анализе экономической и финансовой деятельности. Экспертные системы – это дальнейшее развитие систем управления базами данных. В отличие от СУБД экспертные системы производят логический анализ данных и имеют функцию самообучения. Системы автоматизированного проектирования предназначены для автоматизации процессов конструирования, могут создавать чертёжную документацию, имеют средства проверки расчётов.

4. Системы управления базами данных (СУБД)

4.1. Базы данных в структуре информационных систем

5. Основы алгоритмизации и технологии программирования

5.1. Алгоритм и его свойства

5.1.1. Различные подходы к понятию “алгоритм”. Алгоритм – одно из фундаментальных понятий информатики. Алгоритмизация наряду с моделированием выступает в качестве общего метода информатики. Особенность положения состоит в том, что при решении практических задач, предполагающих разработку алгоритмов для реализации на ЭВМ, почти всегда можно не опираться на высокую формализацию данного понятия. В таких случаях достаточно содержательного толкования понятия алгоритма и рассмотрения его основных свойств. При таком подходе алгоритмизация выступает как набор определенных практических приемов, особых навыков рационального мышления в рамках заданных языковых средств.

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

Алгоритм – это общий, единообразный, точно установленный способ решения любой задачи из данной массовой проблемы. Таким образом, алгоритм всегда связан с решением массовой проблемы. Задачи такого класса отличаются друг от друга значениями входящих в них параметров. Примеры алгоритмов: извлечение квадратного корня, предельный переход, нахождение производной и тому подобное. Приведенное понятие алгоритма нестрогое. В нем встречаются слова, точный смысл которых не установлен, например, “способ”. Тем не менее, даже при таком определении можно выделить некоторые характерные черты алгоритма:

• ) дискретность. Каждая последующая величина получается из значений предыдущих по определенному закону. Все величины получаются последовательно друг за другом;

• детерминированность. Между всеми величинами, получаемыми алгоритмом, существует жесткая причинная связь. Последующие значения зависят от предыдущих;

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

• массовость. Начальная система величин выбирается из некоторого множества. Начальные условия могут варьироваться в бесконечных пределах;

• результативность. Конечный результат всегда должен быть получен.

Описанные свойства алгоритма следует считать эмпирическими. Они выявлены на основе обобщения свойств алгоритмов различной природы и имеют прикладной характер. Слово “алгоритм” происходит от имени математика аль Хорезми^ (ал Горезми – алгоритм). Интуитивное понятие алгоритма работает, когда речь идет о найденном алгоритме решения конкретной задачи. Положение существенно меняется, если возникает алгоритмическая проблема, решение которой не найдено, и требуется установить, имеет ли она решение. В этом случае надо доказать либо существование алгоритма, либо его отсутствие. Первое можно сделать путем фактического описания процесса, решающего задачу. В этом случае достаточно и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс есть алгоритм. Доказать не существование алгоритма таким путем невозможно. Для этого необходимо точное формальное определение.

В уточнении понятия алгоритма выделяются три направления:

• уточнение понятия эффективно вычислимой функции. Этим занимались А. Чёрч^ и К. Гёдель^. В результате был выделен класс частично рекурсивных функций, имеющих строгое математическое определение;

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

• направление, связанное с понятием нормальных алгоритмов из работ А. Маркова^.

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

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

Рекурсивные функции впервые описаны Гёделем, затем в 1936 году Чёрч пришел к такому же классу функций. Анализ идей, лежащих в основе определения рекурсивных функций, позволил Чёрчу высказать гипотезу о том, что класс рекурсивных функций тождественен с классом всюду определенных вычислимых функций. Эта гипотеза известна под именем тезиса Чёрча; доказать ее нельзя, так как понятие вычислимой функции точно не определено. В силу тезиса Черча вопрос о вычислимости функции равносилен вопросу о её рекурсивности. Понятие рекурсивной функции строгое. Поскольку в алгоритмических проблемах речь обычно идет не об алгоритмах, а о вычислимости некоторых, специальным образом подобранных решающих проблему функциях, то можно строго доказать, что решающая конкретную задачу функция не может быть рекурсивной, а, следовательно, не существует и алгоритма решения этой задачи. Именно этим путем Чёрч доказал неразрешимость алгоритмической проблемы логики предикатов.

Если первое направление уточняет понятие алгоритма через класс рекурсивных функций, то второе, связанное с машинной арифметикой, сначала уточняет понятие алгоритма, а затем определяет класс вычислимых функций. Это направление развито Э. Постом^ и А. Тьюрингом^. Основная идея этого направления заключается в том, что алгоритмические процессы – это процессы, которые могут имитироваться на подходяще построенных машинах, которые описываются в точных математических терминах. В результате оказывается, что сложные процессы можно моделировать на простых устройствах. Всякий алгоритм может быть задан некоторой функциональной схемой и реализован в соответствующей машине Тьюринга. Эта гипотеза называется тезисом Тьюринга. Его также нельзя доказать, по той же причине, что и тезис Чёрча. Все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.

Третье направление – теория нормальных алгоритмов Маркова.

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

Основное положение об “универсальности” нормальных алгоритмов – принцип нормализации: любой алгоритм над конечным алфавитом эквивалентен относительно некоторому нормальному алгоритму над . Этот принцип подобен тезисам Чёрча и Тьюринга и недоказуем из-за неопределенности формального понятия алгоритма. На практике достаточно ограничиться алгоритмами, действующими на последовательностях натуральных чисел и выдающих в качестве значений также последовательности натуральных чисел. Действия нормальных алгоритмов Маркова похожи на действия машин Тьюринга.

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

3.1.2. Графическое представление алгоритмов. Алгоритм, составленный для некоторого исполнителя, можно представить различными способами: с помощью графического или словесного описания, в виде таблицы, последовательностью формул, записанным на алгоритмическом языке. Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

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

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

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

Р ассмотрим подробнее некоторые конструкции, использующиеся для построения блок-схем (см. рис. 4.1 а-д). Блоки, характеризующие начало и конец алгоритма, изображаются прямоугольником со скругленными вершинами; обычным прямоугольником – блоки, предназначенные для описания отдельных действий. Аналогичным образом изображаются блоки для ввода/вывода с неопределенного носителя и вывода на печатающее устройство. Наконец, условный блок изображается в виде ромба. Вершины графа, представляющего блок-схему, могут быть одного из трех типов: функциональная вершина , имеющая один вход и один выход, предикатная вершина , имеющая один вход и два выхода, в этом случае функция передает управление по одной из ветвей в зависимости от значения , объединяющая вершина , обеспечивающая передачу управления от одного из двух входов к выходу. Особое значение для практики алгоритмизации имеют четыре блок-схемы: композиция или следование (рис. 3.2 а); альтернатива или ветвление (рис. 3.2 б); итерация или цикл с предусловием (рис. 3.2 в) или постусловием (рис. 3.2 г).

Доказано, что логическая структура любой программы может быть выражена комбинацией трех базовых структур: следования, ветвления и цикла (теорема Бема – Якопини^).

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

Ветвление – это структура, обеспечивающая выбор между двумя альтернативами. Выполняется проверка, а затем выбирается один из путей (см. рис. 3.2 б). Эта структура называется также ЕСЛИ – ТО – ИНАЧЕ. Каждый из двух путей ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.

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

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