- •Федеральное агентство по образованию
- •Содержание
- •Тема 1. Основные понятия информатики
- •1.1. Информатика, ее структура, задачи и функции
- •Предмет информатики составляют следующие понятия:
- •1.2. Понятие информации
- •1.3. Свойства информации
- •1.4. Виды информации
- •1.5. Экономическая информация
- •1.6. Классификация и кодирование информации
- •Кодирование и декодирование числовой информации
- •Международные системы байтового кодирования текстовой информации
- •Кодирование графических данных
- •1.7. Общая характеристика процессов сбора, передачи, обработки и накопления информации
- •Тесты для самопроверки
- •2.2. Свойства алгоритмов
- •2.3. Графическое представление алгоритмов
- •2.4. Технологии программирования Операционный подход
- •Структурный подход
- •Объектно-ориентированное программирование
- •Декларативный подход в программировании
- •Процедурно-ориентированное программирование
- •2.5. Понятие языка программирования
- •2.6. Грамматика языков программирования
- •2.7. Проектирование программ
- •2.8. Системы программирования
- •2.9. Языки программирования высокого уровня Язык программирования Паскаль
- •Основные элементы языка программирования Паскаль
- •Язык программирования Пролог
- •Тесты для самопроверки
- •3.3. Методы классификации компьютеров
- •Классификация по поколениям Первое поколение
- •Второе поколение
- •Третье поколение
- •Четвёртое поколение
- •Пятое поколение36
- •Классификация по условиям эксплуатации
- •Классификация по производительности и характеру использования
- •Основные разновидности портативных компьютеров
- •3.2. Архитектура эвм
- •Классическая архитектура (архитектура фон Неймана)
- •Многопроцессорная архитектура
- •Многомашинная вычислительная система
- •Архитектура с параллельными процессорами
- •3.2. Базовая аппаратная конфигурация пк
- •Системный блок
- •Видеосистема компьютера
- •Монитор на базе электронно-лучевой трубки
- •Последняя не должна быть ниже 85 Гц, иначе изображение будет мерцать. Жидкокристаллические мониторы
- •Сенсорный экран
- •Клавиатура
- •3.6. Внутренние устройства системного блока пк
- •Системная плата
- •Внешняя память
- •Накопители на гибких магнитных дисках
- •Накопители на жестких магнитных дисках
- •Оптические накопители cd-rom
- •Накопители на магнитной ленте (стримеры)
- •Flash-память
- •Платы расширения
- •Аудиоадаптер
- •Видеоадаптер и графический акселератор
- •Модем и факс-модем
- •3.7. Системы, расположенные на материнской плате пк Центральный процессор
- •Микропроцессорный комплект
- •Системные шины
- •Шина адреса
- •Шина данных
- •Шина команд
- •Шинные интерфейсы
- •Внутренняя память
- •Оперативная память
- •Постоянная память
- •3.8. Периферийные устройства пк Принтеры
- •Плоттер
- •Манипуляторы
- •Дигитайзер
- •4.2. Назначение и основные функции ос
- •4.3. Классификация ос
- •4.4. Понятие файловой системы
- •4.5. Сетевое по
- •4.6. Операционные среды и оболочки
- •4.7. Служебное по
- •Тесты для самопроверки
- •1. Драйверы - это
- •3. Форматированием диска называется процесс
- •5.2. Прикладное по общего назначения
- •Текстовые процессоры
- •Электронные таблицы
- •Средства создания презентаций
- •Система управления базами данных
- •Графические редакторы
- •Офисные системы
- •5.3. Проблемно-ориентированное по
- •5.4. Методо-ориентированное по
- •Тесты для самопроверки
- •Информатика
- •Часть 1
- •300600, Г. Тула, пр. Ленина, 92
- •300600, Г. Тула, ул. Болдина, 151
2.2. Свойства алгоритмов
Важнейшими свойствами алгоритма являются:
определенность (детерминированность). В алгоритме должна соблюдаться однозначность предписываемой последовательности действий, не допускающая произвольного ее толкования;
массовость. Алгоритм решения задачи разрабатывается в общем виде так, чтобы его можно было применить для решения задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, называемой областью применимости алгоритма;
дискретность. Алгоритм должен быть разделен на отдельные элементарные акты;
результативность (конечность). Алгоритм должен приводить к решению задачи за конечное число шагов;
инвариантность по отношению к исполнителю. Алгоритм может оставаться неизменным при выполнении предписываемых им команд человеком или машиной любого типа.
Последнее свойство не означает, что при разработке алгоритма можно полностью игнорировать характер вычислительных средств, которыми он будет реализовываться14. Однако, это относится не к принципиальным возможностям, а лишь к удобству реализации алгоритма тем или иным средством.
Для решения любой относительно сложной задачи, как правило, могут быть разработаны несколько различных алгоритмов. Естественно, что следует выбрать лучший из них. Но когда мы говорим лучший, то всегда возникает вопрос: «С какой точки зрения лучший?»
Рассмотрим основные критерии качества алгоритма.
Связанность алгоритма определяется количеством промежуточных результатов, которые должны одновременно храниться в памяти. Естественно, что алгоритм тем лучше, чем его связность меньше, так как при этом уменьшается количество ячеек, занятых в оперативной памяти.
Пример. Рассмотрим численный пример вычисления величины:
х=25/5+45/5-100/5+50/5
Сравним два алгоритма решения этой задачи, учитывая, что каждая операция выполняется в арифметическом устройстве не более чем над двумя числами (операндами).
Алгоритм А |
Алгоритм В | ||||
шаг |
операция |
результат |
шаг |
операция |
результат |
1 |
у1=25+45 |
70 |
1 |
у1=25/5 |
5 |
2 |
у2=70-100 |
-30 |
2 |
у2=45/5 |
9 |
3 |
у3=-30+50 |
20 |
3 |
у3=-100/5 |
-20 |
4 |
х4=20/5 |
4 |
4 |
у4=50/5 |
10 |
|
|
|
5 |
у5=5+9 |
14 |
|
|
|
6 |
у6=14-20 |
-6 |
|
|
|
7 |
х=-6+10 |
4 |
В алгоритме А все результаты должны храниться в памяти только до выполнения следующей операции, т.е. в течение одного шага. Общее количество шагов - четыре. В алгоритме В после второго шага количество результатов, хранящихся в памяти, составляет два, после третьего шага - три, после четвертого шага - четыре, после пятого шага - три, после шестого шага - два. А общее количество шагов - семь.
Таким образом, по связности алгоритм А значительно лучше. Кроме того, он еще и менее трудоемкий.
Объем алгоритма - это количество операций (шагов), которые необходимо выполнить для получения конечного результата. Чем меньше трудоемкость, т.е. чем меньше операций нужно предусмотреть на его написание и исполнение, тем выше качество алгоритма. Уменьшение количества шагов экономит не только время математика - составителя алгоритма, но и машинное время, сокращает длительность решения задачи на ЭВМ.
Длительность решения определяется количеством шагов алгоритма, а также сложностью этих шагов. Даже если все операции, как в примере выше, ограничиваются четырьмя арифметическими действиями, то все равно сказывается существенная разница во время их выполнения. Умножение и деление требуют затрат машинного времени в 3-4 раза больше, чем простейшие операции - сложение и вычитание
Разветвленность алгоритма характеризует логическую сложность и определяется количеством путей, по которым может реализовываться процесс вычислений. Значительная разветвленность увеличивает сложность алгоритма, а значит и трудоемкость его разработки.
Цикличность алгоритма заключается в том, что фактическое количество операций, которые должны быть выполнены в ходе вычислительного процесса, превышает количество операций, содержащихся в записи алгоритма. (Те или иные операции могут повторяться многократно – в цикле).