Работа с информацией. Методы решения задач. Языки программирования и алгоритмизация. Базы данных и компьютерные сети

3.5.7 Объединение ЭТ

При работе с ЭТ часто возникает необходимость их объединения.

Среди инструментов объединения ЭТ отметим:

организацию межтабличных связей;

консолидацию ЭТ или их частей;

объединение файлов.

Организация межтабличных связей

Связи между таблицами осуществляются путем использования внешних ссылок (адресов ячеек), содержащих помимо имени столбца и номера строки имя файла, данные из которого используются. Например, в текущей таблице, расположенной на листе2, надо использовать данные из ячейки B3 на листе1. В нужную ячейку текущей таблицы можно записать ссылку следующим образом: Лист1!B3.Еще один пример, если надо использовать данные из ячейки С2 таблицы, расположенной на листе2, содержащемся в файле Exam.wq1, в нужную ячейку текущей таблицы можно записать внешнюю ссылку следующим образом: [Exam.wq1]Лист2!C2.

Консолидация электронных таблиц или их частей

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

Команда объединения файлов

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

Лекция 3.8 Электронные презентации

3.8.1 Программа Microsoft PowerPoint. Режимы PowerPoint

Для подготовки презентация разработано немалое количество программных продуктов. Наиболее широкое применение получила программа Microsoft PowerPoint, вошедшая в состав пакета Microsoft Office 2000.

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

Обычный режим

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

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

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

Область заметок. Область заметок служит для добавления заметок докладчика или сведений для аудитории. Если в заметках должен быть рисунок, добавлять заметки следует в режиме страниц заметок.

Эти три области также присутствуют при сохранении презентации как Web-страницы. Единственное отличие состоит в том, область структуры отображается как содержание, позволяющее перемещаться по презентации.

Режим сортировщика слайдов

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

При создании презентации в любой момент можно запустить показ слайдов и просмотреть презентацию, нажав кнопку Показ слайдов.

ДЕ4. Модели решения функциональных и вычислительных задач

Лекция 4.1 Моделирование как метод познания

4.1.1 Классификация задач, решаемых с помощью моделей

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

С точки зрения информатики, решение любой задачи представляют замкнутую технологическую последовательность (рис. 4.1.):

Рис. 4.1 Этапы решения задач

4.1.2 Основные понятия

Каждый элемент в этом ряду играет свою особую роль.

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

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

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

Теория моделирования рассматривает две группы способов моделирования: аналитическое и имитационное. Аналитическое моделирование заключается в построении модели, основанной на описании поведения объекта или системы объектов в виде аналитических выражений - формул. При таком моделировании объект описывается системой линейных или нелинейных алгебраических или дифференциальных уравнений, решение которых может дать представление о свойствах объекта. К полученной аналитической модели, с учетом вида и сложности формул применяются аналитические или приближенные численные методы. Численные методы обычно реализуются на вычислительных машинах. Применение аналитического моделирования ограничено сложностью получения и анализа выражений для большинства систем.

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

Цели моделирования

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

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

научиться управлять объектом (или процессом) и определять наилучшие способы управления при заданных целях и критериях (управление);

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

Лекция 4.2 Методы и технологии моделирования

4.1.2 Системный подход в моделировании систем

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

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

При системном моделировании, прежде всего, четко определяется цель моделирования. Создание модели полного аналоги оригинала дело трудоемкое и дорогое, поэтому модель создается под определенную цель.

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

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

Лекция 4.3 Классификация моделей

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

4.3.1 Классификация видов моделирования

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

По цели использования:

В научном эксперименте осуществляется исследование модели с применением различных средств получения данных об объекте, возможности влияния на ход процесса, с целью получения новых данных об объекте, процессе или явлении;

Комплексные испытания и производственный эксперимент используют натурное испытание физического объекта для получения высокой достоверности о его характеристиках;

Оптимизационные связаны с нахождением оптимальных показателей системы (например, нахождение минимальных затрат или определение максимальной прибыли).

По наличию воздействий на систему:

Детерминированные - в системах отсутствуют случайные воздействия;

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

Эти же модели классифицируют по способу оценки параметров системы: в детерминированных системах параметры модели оцениваются одним показателем для конкретных значений их исходных данных; в стохастических системах наличие вероятностных характеристик исходных данных, позволяет оценивать параметры системы несколькими показателями.

По отношению ко времени:

Статические модели описывают систему в определенный момент времени;

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

По возможности реализации:

Мысленные модели описывают систему, которую трудно или невозможно моделировать реально. Мысленные модели разделяются на:

Наглядные - при которых моделируемые процессы и явления протекают наглядно;

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

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

Реальные модели системы представлены либо реальным объектом, либо его частью. Эти модели делятся на:

натурные - проведение исследования на реальном объекте и последующая обработка результатов эксперимента с применением теории подобия;

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

Информационные модели реализуют информационные процессы (возникновение, передачу, обработку и использование информации) на компьютере.

По области применения:

Универсальные модели предназначены для использования многими системами;

Специализированные модели созданные для исследования конкретной системы.

Лекция 4.4 Интеллектуальные системы

Искусственный интеллект

Идеи моделирования человеческого разума известны с древнейших времен. Впервые об этом упоминается в сочинении философа и теолога Раймунда Луллия (около 1235 - 1315) «Великое искусство», который не только высказал идею логической машины для решения разнообразных задач, но и попытался ее реализовать. Рене Декарт (1596 - 1650) и Готфрид Вильгельм Лейбниц (1646 - 1716) независимо друг от друга развивали учение о прирожденной способности ума к познанию и всеобщих и необходимых истин логики и математики, работали над созданием универсального языка классификации всех знаний. Именно на этих идеях базируются теоретические основы создания искусственного интеллекта. Толчком к дальнейшему развитию модели человеческого мышления стало появление в 40-х гг. ХХ в. ЭВМ. В 1948 г. американский ученый Норберт Винер (1894 - 1964) сформулировал основные положения новой науки - кибернетики. В 1956 г. признано новое научное направление, связанное с машинным моделированием человеческих, интеллектуальных функций, и названное искусственным интеллектом.

Вскоре эта отрасль разделилась на два направления: нейрокибернетику и кибернетику «черного ящика».

Нейрокибернетика обратилась к структуре человеческого мозга, как единственно мыслящему объекту и занялась его аппаратным моделированием. Нейрокибернетика занимается созданием элементов, аналогичных нейронам (связанным друг с другом нервным клеткам, составляющим основу мозга), и их объединением в функционирующие системы, названные нейросетями. В середине 80-х гг. ХХ в. в Японии был создан первый нейрокомьютер, моделирующий структуру человеческого мозга. Его основная область применения - распознавание образов.

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

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

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

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

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

4.4.2 База знаний

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

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

Исследования процессов принятия решения человеком показали, что рассуждая и принимая решение, человек использует продукционные правила (от английского production - правило вывода, порождающее правило). Продукционная модель, основанная на правилах, позволяет представить знания в виде предложений: ЕСЛИ (список условий), ТО (следует выполнить перечень действий). Условие - это предложение, по которому происходит поиск в базе знаний, а действие есть некоторая операция, выполняемая при успешно осуществленном поиске. Действия могут быть как промежуточными, выступающими далее как условия, так и целевыми, завершающими работу ИС. В продукционной модели база знаний состоит из совокупности правил. Программа, управляющая перебором правил, называется машиной вывода. Механизм выводов связывает знания и создает из их последовательности заключение. Вывод бывает прямой (метод сопоставления, от данных к поиску цели) или обратный (метод генерации гипотезы и ее проверки, от цели к данным).

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

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

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

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

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

Важным свойством фреймов является наследование свойств, заимствованных из теории семантических сетей. Наследование происходит по АКО - связям (A-Kind-Of= это). Слот АКО указывает на фрейм более высокого уровня иерархии, откуда неявно наследуется, т.е. переносятся значения аналогичных слотов. Например, в сети фреймов на рис. 4.4.2. «конструктор» наследует свойства фреймов «инженер» и «человек», которые стоят на более высоком уровне иерархии. Модель фреймов достаточно универсальна, позволяет отобразить все многообразие знаний о мире через:

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

Фреймы - роли (студент, преподаватель, декан);

Фреймы - сценарии (сдача экзамена, празднование именин, получение стипендии);

Фреймы - ситуации (тревога, рабочий режим учебного дня) и др.

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

Обобщая анализ моделей представления знаний, можно сделать следующие выводы:

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

Наиболее мощными являются смешанные модели представления знаний.

4.4.3 Экспертные системы

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

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

Современные ЭС способны:

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

Выполнять задачи диагностических систем в исследовании явлений и процессов (например, для анализа крови; управления производством; изучения состояния недр земли, нефтяных полей, залежей угля и т.п.);

Распознавать речь, на данном этапе в ограниченной области применения;

Распознавать человеческие лица, отпечатки пальцев и др.

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

ДЕ5. Алгоритмизация и программирование. Языки программирования высокого уровня

Лекция 5.1 Алгоритмизация

5.1.1 Понятие алгоритма

Слово «алгоритм» происходит от «algorithmi» - латинской формы описания имени великого узбекского математика IХ в. аль - Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом и понимали только правила выполнения четырех арифметических действий над многозначными числами.

Понятие алгоритма - одно из фундаментальных понятий информатики.

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

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

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

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

Дискретность (разрывность) - это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий. Говорят: «Делится на шаги».

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

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

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

Формальность - это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.

5.1.3 Способы описания алгоритмов

Существуют несколько способов описания алгоритма: словесное, псевдокод, блок-схема, программа.

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

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

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

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

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

Лекция 5.2 Блок-схемы алгоритма

5.2.1 Алгоритмы решения задач

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

Линейная структура (следование) самая важная из структур. Она означает, что действия могут быть выполнены друг за другом.

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

Пример 5.2.1.

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

Псевдокод:

Ввод двух чисел a, b

Вычисляем сумму

S = a + b

Вывод S

Конец.

Ветвление (развилка) - это структура, обеспечивающая выбор между двумя альтернативами. Выполняется проверка условия, а затем выбирается один из путей.

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

Такая структура называется «неполным ветвлением» или «неполной развилкой».

Пример 5.2.2.

Вывести значение наибольшего числа из двух чисел (рис. 5.2.5).

Псевдокод:

Ввод двух чисел a, b

ЕСЛИ a>b, ТО «выводим a»,

ИНАЧЕ «выводим b»

Конец.

Цикл (или повторение) предусматривает повторное выполнение некоторого набора команд алгоритма. Циклы позволяют записать длинные последовательности операций обработки данных с помощью небольшого числа повторяющихся команд. Различают два типа циклов: «цикл с предусловием» и «цикл с постусловием».

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

Пример 5.2.3.

Вычислить сумму 100 чисел (рис. 5.2.7).

Псевдокод:

НАЧ

I =1; S = 0

ПОКА i<=100 делать

НЦ

Ввести ai

S = S + ai

i = i + 1

КЦ

Вывод S

Конец.

НЕТ

ДА

Цикл с постусловием («До»).

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

Пример 5.2.4.

Вывести максимальное значение из 100 натуральных чисел (рис. 5.2.9).

Псевдокод:

Начало

Ввести a1

max = a1; i = 2

НЦ

Ввести ai

ЕСЛИ max < ai ТО max = ai

i = i + 1

ДО I>100;

КЦ

Вывести max.

Конец.

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

5.3.1 Языки программирования

Языки программирования - это искусственные языки. От естественных они отличаются ограниченным числом «слов», значение которых понятно транслятору, и очень строгими правилами записи команд (операторов).

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

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

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

5.3.2 Уровни языков программирования

Разные типы процессов имеют разные наборы команд. Если язык программирования ориентирован на конкретный тип процессора и учитывает его особенности, то он называется языком программирования низкого уровня. В данном случае «низкий» не значит «плохой». Имеется ввиду, что операторы языка близки к машинному коду и ориентированы на конкретные команды процессора. Языком низкого уровня является язык ассемблера, который просто представляет каждую команду машинного кода, но не в виде чисел, а с помощью символьных, условных обозначений, называемых мнемониками. Однозначное преобразование одной машинной инструкции в одну команду ассемблера называют транслитерацией. Так как наборы инструкций для каждой модели процессора отличаются, конкретной компьютерной архитектуре соответствует свой язык ассемблера, написанная на нем программа может быть использована только в этой среде.

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

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

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

5.3.3 Поколение языков программирования

Языки программирования принято делить на пять поколений. В первое входят языки, созданные в начале 50-х годов, когда первые компьютеры только появились на свет. Это был первый язык ассемблера, созданный по принципу «одна инструкция - одна строка».

Расцвет второго поколения языков программирования пришелся на конец 50-х начало 60-х годов. Тогда был разработан символический ассемблер, в котором появилось понятие переменной. Он стал первым полноценным языком программирования. Благодаря его возникновению заметно возросли скорость разработки и надежность программ.

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

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

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

ДЕ6. Программное обеспечение и технологии программирования

Лекция 6.1 Системы программирования

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

Составление исходного кода программ (рис. 6.1) на языке программирования;

Этап трансляции, необходимый для создания объектного кода программы;

Построение загрузочного модуля, готового к исполнению.

Все перечисленные выше действия требуют наличия специальных программных средств.

Совокупность этих программных средств, входит в состав системы программирования:

Текстовый редактор (необходимый для создания и редактирования исходного кода программы на языке программирования);

Компилятор;

Редактор связей;

Отладчик;

Библиотеки функций;

Справочная система.

6.1.1 Классификация языков программирования

Многие языки, первоначально разработанные для больших и малых ЭВМ, в дальнейшем были приспособлены к персональным компьютерам. Хорошо вписались в ПК не только Паскаль, Бейсик, Си, Лого, но и ЛИСП, ПРОЛОГ - языки искусственного интеллекта.

В течение многих лет программное обеспечение строилось на основе операционных и процедурных языков, таких как Фортран, Бейсик, Паскаль, Ада, Си. И сегодня современные версии этих и им подобных языков (Модула, Форт и др.) доминируют при разработке прикладных программных средств. Однако по мере эволюции языков программирования получили широкое распространение и другие, принципиально иные, подходы к созданию программ.

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

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

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

6.1.2 Обзор языков программирования высокого уровня

Fortran (Фортран ). Первый компилируемый язык, созданный Джимом Бэкусом в 50-е годы. Основным критерием при разработке компиляторов Фортрана является эффективность исполняемого кода. В Фортране впервые был реализован ряд важнейших понятий программирования, но создание программы не очень удобно. Однако для этого языка было создано огромное количество библиотек, поэтому Фортран продолжает активно использоваться во многих организациях. Сейчас ведутся работы над очередным стандартом Фортрана (HPF) для параллельных суперкомпьютеров, со множеством процессоров.

Cobol (Кобол). Это компилируемый язык для применения в экономической области и решения бизнес задач, разработанный в начале 60-х годов. Отличается большой «многословностью»- его операторы иногда выглядят как обычные английские фразы. В Коболе были реализованы очень мощные средства работы с большими объемами данных, хранящихся на различных внешних носителях. На этом языке создано очень много приложений, которые активно эксплуатируются и сегодня. Достаточно сказать, что наибольшую зарплату в США получают программисты на Коболе.

Algol (Алгол). Компилируемый язык, созданный в 1960 году. Был признан заменить Фортран, но из-за более сложной структуры не получил широкого распространения. В 1968 г. была создана версия Алгол-68, по своим возможностям и сегодня опережающая многие языки программирования, однако из-за отсутствия достаточно эффективных компьютеров для нее не удалось своевременно создать хорошие компиляторы.

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

Basic (Бейсик). Для этого языка имеются и компиляторы, и интерпретаторы, а по популярности он занимает первое место в мире. Он создан в 60-х годах в качестве учебного языка и очень прост в изучении.

С (си). Был создан в лаборатории Bell и первоначально не рассматривался как массовый. Он планировался для замены Ассемблера. Си во многом похож на Паскаль и имеет дополнительные средства для прямой работы с памятью (указатели). На этом языке в 70-х годах написано множество прикладных и системных программ и ряд известных OC (Unix).

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

Java (Джава, Ява). Этот язык был создан компанией Sun в начале 90-х годов на основе Cu++ путем исключения из него низкоуровневых возможностей, главная особенность этого языка компиляция не в машинный код, а в платформно - независимый байт-код (каждая команда занимает один байт). Этот байт-код может выполняться с помощью интерпретатора виртуальной Java -машины JVM (Java virtual machine), версии которой созданы сегодня для любых платформ. Благодаря наличию множества Java-машин программы на Java можно переносить не только на уровне исходных текстов, но и на уровне двоичного байт-кода, поэтому по популярности язык Ява сегодня занимает второе место в мире после Бейсика.

Особое внимание в развитии этого языка уделяется двум направлениям: поддержке всевозможных мобильных устройств и микрокомпьютеров, встраиваемых в бытовую технику (технология Jini) и создание платформно - независимых программных модулей, способных работать на серверах в глобальных и локальных сетях с различными ОС (технология Java Bens). Пока основной недостаток этого языка - невысокое быстродействие, т.к. язык Ява интерпретируемый.

6.1.3 Языки программирования БД

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

6.1.4 Языки программирования для Интернета

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

Вопросы для самоконтроля

Какие языки программирования высокого уровня вы знаете?

Какие языки программирования активно используются и сегодня?

Лекция 6.2 Стратегии решения задач

6.2.1 Этапы подготовки и решения задач на компьютере

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

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

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

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

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

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

Составление программы - алгоритм решения переводится на конкретный язык программирования;

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