Свойства алгоритмов - раздел Информатика, ИНФОРМАТИКА Важнейшими Свойствами Алгоритма Являются:
· Определенность (Д...
Важнейшими свойствами алгоритма являются:
· определенность (детерминированность). В алгоритме должна соблюдаться однозначность предписываемой последовательности действий, не допускающая произвольного ее толкования;
· массовость. Алгоритм решения задачи разрабатывается в общем виде так, чтобы его можно было применить для решения задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, называемой областью применимости алгоритма;
· дискретность. Алгоритм должен быть разделен на отдельные элементарные акты;
· результативность (конечность). Алгоритм должен приводить к решению задачи за конечное число шагов;
· инвариантность по отношению к исполнителю. Алгоритм может оставаться неизменным при выполнении предписываемых им команд человеком или машиной любого типа.
Последнее свойство не означает, что при разработке алгоритма можно полностью игнорировать характер вычислительных средств, которыми он будет реализовываться[14]. Однако, это относится не к принципиальным возможностям, а лишь к удобству реализации алгоритма тем или иным средством.
Для решения любой относительно сложной задачи, как правило, могут быть разработаны несколько различных алгоритмов. Естественно, что следует выбрать лучший из них. Но когда мы говорим лучший, то всегда возникает вопрос: «С какой точки зрения лучший?»
Рассмотрим основные критерии качества алгоритма.
· Связанность алгоритма определяется количеством промежуточных результатов, которые должны одновременно храниться в памяти. Естественно, что алгоритм тем лучше, чем его связность меньше, так как при этом уменьшается количество ячеек, занятых в оперативной памяти.
Пример. Рассмотрим численный пример вычисления величины:
х=25/5+45/5-100/5+50/5
Сравним два алгоритма решения этой задачи, учитывая, что каждая операция выполняется в арифметическом устройстве не более чем над двумя числами (операндами).
| Алгоритм А
| Алгоритм В
|
| шаг
| операция
| результат
| шаг
| операция
| результат
|
|
| у1=25+45
|
|
| у1=25/5
|
|
|
| у2=70-100
| -30
|
| у2=45/5
|
|
|
| у3=-30+50
|
|
| у3=-100/5
| -20
|
|
| х4=20/5
|
|
| у4=50/5
|
|
|
|
|
|
| у5=5+9
|
|
|
|
|
|
| у6=14-20
| -6
|
|
|
|
|
| х=-6+10
|
|
В алгоритме А все результаты должны храниться в памяти только до выполнения следующей операции, т.е. в течение одного шага. Общее количество шагов - четыре. В алгоритме В после второго шага количество результатов, хранящихся в памяти, составляет два, после третьего шага - три, после четвертого шага - четыре, после пятого шага - три, после шестого шага - два. А общее количество шагов - семь.
Таким образом, по связности алгоритм А значительно лучше. Кроме того, он еще и менее трудоемкий.
· Объем алгоритма - это количество операций (шагов), которые необходимо выполнить для получения конечного результата. Чем меньше трудоемкость, т.е. чем меньше операций нужно предусмотреть на его написание и исполнение, тем выше качество алгоритма. Уменьшение количества шагов экономит не только время математика - составителя алгоритма, но и машинное время, сокращает длительность решения задачи на ЭВМ.
· Длительность решения определяется количеством шагов алгоритма, а также сложностью этих шагов. Даже если все операции, как в примере выше, ограничиваются четырьмя арифметическими действиями, то все равно сказывается существенная разница во время их выполнения. Умножение и деление требуют затрат машинного времени в 3-4 раза больше, чем простейшие операции - сложение и вычитание
· Разветвленность алгоритма характеризует логическую сложность и определяется количеством путей, по которым может реализовываться процесс вычислений. Значительная разветвленность увеличивает сложность алгоритма, а значит и трудоемкость его разработки.
· Цикличность алгоритма заключается в том, что фактическое количество операций, которые должны быть выполнены в ходе вычислительного процесса, превышает количество операций, содержащихся в записи алгоритма. (Те или иные операции могут повторяться многократно – в цикле).
Все темы данного раздела:
Часть 1
УЧЕБНОЕ ПОСОБИЕ
Издательство ТулГУ
Тула 2006
УДК 004 (075.9)
Информатика. Часть 1: Учеб. п
Информатика, ее структура, задачи и функции
Информационное общество - общество, в котором большинство работников занято производством, хранением, переработкой и реализацией информации, особенно высшей ее формы - з
Понятие информации
Информация[2] – это мера устранения неопределенности в отношении исхода интересующего нас события.
Данные[3]
Свойства информации
Информация характеризуется тремя категориями свойств: атрибутивными, прагматическими и динамическими.
Атрибутивные свойства- необходимые свойства, те, без которых информация не може
Виды информации
Информацию можно классифицировать по различным признакам (табл.1.1).
Таблица 1.1.
Виды информации
Классификационный признак
Виды
Экономическая информация
Экономическая информация (ЭИ) – это информация, отражающая и обслуживающая процессы производства, распределения, обмена и потребления материальных благ. Или экономиче
Кодирование и декодирование числовой информации
При кодировании числовой информации используют системы счисления.
Система счисления - способ наименования и изображения чисел с помощью символов, имеющих определенные
Международные системы байтового кодирования текстовой информации
Наиболее распространены две системы кодирования EBCDIC (Extended Binary Coded Decimal Interchange Code) и ASCII (American Standard Code for Information Interchange - стандартный код информационного
Кодирование графических данных
Растр (raster) - форма представления изображения в виде элементов (точек), упорядоченных в строки и столбцы.
Общепринятым на сегодняшний день считается представ
Общая характеристика процессов сбора, передачи, обработки и накопления информации
Обработка данных включает в себя множество различных операций (рис.1.10), к основным из которых относятся:
· сбор данных – накопление информации с целью обеспечения достаточной полн
Понятие алгоритма
Определение алгоритма[11] в сжатом виде было сформулировано известным русским математиком Марковым.
Алгоритмом называется точное предписание, задающее преобразо
Графическое представление алгоритмов
Схема алгоритма – это ориентированный граф, указывающий порядок исполнения алгоритма.
Схема алгоритма содержит условные графические фигуры[15]. Они обозначают с
Операционный подход
На начальных этапах развития вычислительной техники, когда машинное время было дорого, а возможности ЭВМ малы основными требованиями к алгоритму и программе были:
1) использование наименьш
Структурный подход
В основе структурного подхода лежит утверждение о том, что логическая структура любого алгоритма может быть выражена комбинацией трех канонических (базовых) структур (рис.2.2).
· Следов
Объектно-ориентированное программирование
Объектно-ориентированное программирование основано на концепции объединения данных и процедур их обработки в единое целое.
Объект – совокупность свойств (структ
Понятие языка программирования
Язык программирования[19] - формальный язык для описания алгоритма решения задачи на компьютере.
Каждый язык программирования имеет:
·
Грамматика языков программирования
Несмотря на значительные различия между языками программирования, ряд фундаментальных понятий в большинстве из них схожи.
Оператор – законченная фраза языка, определяющая однозначно тракту
Проектирование программ
Современный подход к проектированию программ основан на декомпозиции задачи. Целью декомпозиции является создание модулей, которые представляют собой небольшие, относительно самостоятельные програм
Системы программирования
Система программирования — это система для разработки новых программ на конкретном языке программирования.
Современные системы программирования обычно предоставляют по
Язык программирования Пролог
Является представителем семейств языков логического программирования. Его особенности в сравнении с традиционными алгоритмическими языками:
· программа на Прологе не является алгоритмом, а
Офисная техника
Офисная техника – неотъемлемая часть технического оборудования любого офиса. К офисной технике[35] можно отнести любые технические средства, облегчающие работу в офисе, начиная от карандашей и авто
История развития средств вычислительной техники
История счётных устройств насчитывает много веков. Приведем некоторые наиболее значимые события этой истории.
1642 г. Французский ученый Блез Паскаль приступил к созданию
Основные разновидности портативных компьютеров
Портативные компьютеры обычно нужны руководителям предприятий, менеджерам, учёным, журналистам, которым приходится работать вне офиса — дома, на презентациях или во время командировок.
Архитектура ЭВМ
При рассмотрении компьютерных устройств принято различать их архитектуру и структуру.
Архитектурой компьютера называется его описание на некотором общем уровне,
Многомашинная вычислительная система
Здесь несколько процессоров, входящих в вычислительную систему, не имеют общей оперативной памяти, а имеют каждый свою (локальную). Каждый компьютер в многомашинной системе имеет классическую архит
Архитектура с параллельными процессорами
Здесь несколько АЛУ работают под управлением одного УУ. Это означает, что множество данных может обрабатываться по одной программе — то есть по одному потоку команд. Высокое быстродействие такой ар
Базовая аппаратная конфигурация ПК
Персональным компьютером (ПК) называют сравнительно недорогой универсальный микрокомпьютер, рассчитанный на одного пользователя. Персональные компьютеры обычно проектируются на основе принципа откр
Системный блок
Системный блок представляет собой основной узел, внутри которого установлены наиболее важные компоненты. Устройства, находящиеся внутри системного блока называются внутренними, а устройства,
Видеосистема компьютера
Видеосистема компьютера состоит из трех компонент:
· монитор (называемый также дисплеем);
· видеоадаптер;
· программное обеспечение (драйверы видеосистемы).
Виде
Последняя не должна быть ниже 85 Гц, иначе изображение будет мерцать.
Жидкокристаллические мониторы
Жидкие кристаллы — это особое состояние некоторых органических веществ, в котором они обладают текучестью и свойством образо
Клавиатура
Клавиатура компьютера — устройство для ввода информации в компьютер и подачи управляющих сигналов. Содержит стандартный набор клавиш печатной машинки и некоторые дополни
Системная плата
Системная плата является основной в системном блоке. Она содержит компоненты, определяющие архитектуру компьютера:
· центральный процессор;
· постоянную (ROM) и оперативную (RAM)
Внешняя память
Внешняя память (ВЗУ) предназначена для длительного хранения программ и данных, и целостность её содержимого не зависит от того, включен или выключен компьютер. В отличие от оперативной памяти, внеш
Оптические накопители CD-ROM
Первоначально носителем информации на таких устройствах являлись CD-ROM (Сompact Disk Read-Only Memory - компакт диск, из которого можно только читать). Эти диски записывались («прожигались») однок
Flash-память
Flash (флэш)-память относится к статической энергонезависимой памяти. По устройству чип flash-памяти напоминает микросхему динамической энергозависимой памяти, только вместо конденсаторов ячейками
Платы расширения
Для того, чтобы соединить друг с другом различные устройства компьютера, они должны иметь одинаковый интерфейс (англ. interface от inter — между, и face — лицо).
Интерфейс
Центральный процессор
Центральный процессор (CPU, от англ. Central Processing Unit) — это основной рабочий компонент компьютера, который выполняет арифметические и логические операции, заданные программой, управляет выч
Системные шины
Обмен данными и командами между внутренними устройствами ПК происходит по проводникам многожильного кабеля – системным шинам. Основной задачей системной шины является передача данных между процессо
Внутренняя память
Память компьютера построена из двоичных запоминающих элементов—битов, объединенных в группы по 8 битов, которые называются байтами. (Единицы измерения памяти совпадают с единицами
Принтеры
Принтер — печатающее устройство. Осуществляет вывод из компьютера закодированной информации в виде печатных копий текста или графики.
Основных виды принтеров: матричны
Плоттер
Плоттер (графопостроитель) — устройство, которое чертит графики, рисунки или диаграммы под управлением компьютера.
Плоттеры используются для получения сложных конструкторски
Манипуляторы
Манипуляторы (мышь, джойстик и др.) — это специальные устройства, которые используются для управления курсором.
Джойстик — обычно это стержень-ручка, отклонение котор
Принцип записи данных на перезаписываемые компакт диски заключается в
а) прожигании рабочего слоя диска лазером
б) размагничивании поверхности диска
в) намагничивании поверхности диска
г) просвечивании лазером поверхности диска
д)
Назначение и основные функции ОС
Операционная система (ОС) — система программ, предназначенная для управления ресурсами ЭВМ и процессами, которые используют эти ресурсы, а также для обеспечения пользовательского интерфейса.
Понятие файловой системы
Любые данные, представленные в виде совокупности нулей и единиц, хранятся в памяти компьютера в виде файлов.
Файл (переводится как досье, картотека - file) - по
Сетевое ПО
Сетевое программное обеспечение является составной частью системного ПО и предназначено для управления общими ресурсами в распределенных вычислительных системах. Общими ресурсами, как правило, явля
Операционные среды и оболочки
Операционная среда — система, изменяющая и дополняющая как пользовательский, так и программный интерфейс. Операционная среда создает для пользователя и прикладных
Служебное ПО
Утилиты дополняют интерфейс пользователя и используются в тех случаях, когда программного обеспечения, представленного в ОС, недостаточно для обслуживания пользователем компьютера.
Они обе
Драйверы - это
а) программы для ознакомления пользователя с принципами устройства компьютера
б) технические устройства
в) системы автоматизированного проектирования
г) программы для сог
Понятие прикладного ПО и пакета прикладных программ
Прикладное программное обеспечение предназначено для решения конкретных задач из выбранной пользователем проблемной области. Характер решаемых пользователем задач во многом определяет состав прикла
Текстовые процессоры
Текстовый процессор (система подготовки текстов) - программное средство, обеспечивающее ввод, хранение, просмотр, редактирование, форматирование и печать текстов.
Электронные таблицы
Электронные таблицы (табличные процессоры) являются комплексным средством хранения и обработки разных типов данных (текстовые, числовые, финансовые, дата, время и др.). Электронные таблицы (ЭТ) вкл
Средства создания презентаций
Средства создания презентаций используются для наглядного отображения конкретных прикладных процессов с использованием текста, графики, звука, видео или анимации. Презентация представляет собой наб
Графические редакторы
Средствами работы с графикой являются графические редакторы, предназначенные для создания и обработки графических изображений. В зависимости от способа представления графического изображения различ
Офисные системы
Примером пакета прикладных программ общего назначения является пакет Microsoft Office. Пакет Microsoft Office прошел путь от набора офисных продуктов для одного пользователя (Microsoft Office 95, M
Проблемно-ориентированное ПО
Прикладные программы, которые используются для решения более узких задач, нежели рассмотренные, образуют группы проблемно-ориентированного, методо-ориентированного и оригинального ПО (рис. 4.2).
Методо-ориентированное ПО
Методо-ориентированное ПО реализует определенные методы решения задач в различных областях знаний, например, поиск оптимальных решений, статистическая обработка данных, прогнозирование и т.д.
Тесты для самопроверки
1. Чем сопровождается объединение программных средств в пакеты?
а) единым стилем взаимодействия пользователя с системой
б) многообразным представлением информации
Библиографический список
1. Информатика: Учебник / Под ред. проф. Н.В. Макаровой. - М.: Финансы и статистика, 2002. – 768 с.
2. Экономическая информатика: Учебник / Под ред. В.П.Косарева и Л.В. Еремина. – М.: Фина
Часть 1
Редакция авторов
Изд. лиц. ЛР № 020300 от 12.02.97. Подписано в печать ___________.
Форма бумаги 60х80 1/16.
Новости и инфо для студентов