1. Основы алгоритмизации

При работе с данным разделом Вам предстоит:

1. Изучить три темы:

• специфика решения задачи с использованием компьютера;

• понятие алгоритма;

• примеры классических алгоритмов.

2. Ответить на вопросы для самоконтроля по каждой теме.

3. Выполнить одну практическую работу.

1. Специфика решения задачи с использованием компьютера

   1. Роль моделирования при решении сложных задач

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

Рис. 1.1 Классификация моделей по степени формализации

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

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

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

4. Полученные формальные модели могут быть преобразованы в математические:

• аналитические модели (показатели эффективности выражаются в виде функций относительно параметров системы),

• имитационные модели (моделирование при помощи алгоритмов и программ, имитирующих функционирование исследуемой системы).

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

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

В процессе решения задачи с применением компьютера исследователь проходит ряд этапов (рис. 1.2).

Рис. 1.2 Этапы решения задачи на компьютере

2. Устройство компьютера как инструмента решения задач

На всех этапах подготовки задачи к решению и при ее решении на компьютере необходимо учитывать особенности работы вычислительной техники:

• огромное быстродействие компьютера и абсолютную исполнительность;

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

• отсутствие у компьютера интуиции и чувства здравого смысла;

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

Упрощенная схема взаимодействия процессора с памятью и внешними устройствами представлена на рис. 1.3.

Рис. 1.3 Упрощенная схема взаимодействия процессора с памятью и внешними устройствами

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

В цифровой вычислительной технике транзисторы используются как электронные переключатели. В процессоре компьютера транзисторы сгруппированы в микроэлементы, называемые триггерами. Триггеры имеют два устойчивых состояния (открыт – закрыт) и переключаются из одного состояния в другое электрическими сигналами. Этим устойчивым состояниям соответствуют математические понятия 0 или 1. Поступающие в процессор команды – электрические сигналы – двоичные числа.

Машинный код процессора – это последовательность двоичных чисел. Для понимания процесса составления машинного кода следует ориентироваться на структуру оперативной памяти компьютера, в которой хранятся данные и программы.

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

Рис. 1.4 Структура оперативной памяти (ОЗУ) компьютера

Формирование двоичного машинного кода иллюстрируется на рис. 1.5.

Рис. 1.5 Пример образования машинного кода

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

Таблица 1.1 Содержимое дискретов памяти

№ п/п	Дискрет памяти	Содержимое дискрета памяти
1	Бит	1. Число 0 или 1 2. Логическая величина ДА (если 1), НЕТ (если 0)
2	Байт (8 бит)	1. Числа без знака (положительные) от 0 до 255 2. Числа со знаком (положительные и отрицательные) от -127 до +128 3. Один символ (его числовой код от 0 до 255)
3	Слово (2 байта)	1. Числа без знака (положительные) от 0 до 65535 2. Числа со знаком (положительные и отрицательные) от -32767 до +32768
4	2 слова	1. Целые числа без знака (положительные) более 65535 2. Дробные числа

Устройства ввода-вывода предназначены для организации взаимодействия человека с компьютером.

Для ввода данных в компьютер используется:

• клавиатура (набор данных вручную);

• жесткий диск (ввод данных из файла).

Для вывода данных из компьютера используется:

• экран монитора (для визуализации);

• принтер (для документирования);

• жесткий диск (для сохранения данных в файле).