Астахова Е.В. Теоретические основы информатики

Подождите немного. Документ загружается.

а) развилка б) коррекция

Рис. 6 Функциональные блоки команды ветвления

а) с предусловием б) с постусловием

Рис. 7 Функциональные блоки команды повторения

S Действие, выполняемое в цикле, должно влиять на условие.

S Приведенному фрагменту блок-схемы соответствует фрагмент программы …

a. ввод x, z

выбор

при x<100: y = x*z

при z>10: y = x+z

все

вывод y

b. ввод x, z

нц

пока (x<100) и (z>10)

y = x*z

y = x+z

вывод y

кц

c. ввод x, z

если (x<100)

то если (z>10)

то y = x+z

иначе y = x*z

все

иначе y = x*z

все

вывод y

d. ввод x, z

если (x<100)

то если (z>10)

то y = x*z

иначе y = x+z

все

иначе y = x+z

все

вывод y

S Любой алгоритм может быть построен с использованием только базовых конструкций:

следования, развилки и цикла.

Вво

x < 100 z > 10

Выво

y := x + z

y := x * z

ДА ДА

НЕТ

ДЕЙСТВИЕ

НЕТ

УСЛОВИЕ

ДЕЙСТВИЕ

ДА

НЕТ

УСЛОВИЕ

Действие 1 Действие 2

УСЛОВИЕ

ДА

НЕТ

Действие 1

УСЛОВИЕ

НЕТ

ДА

Построение алгоритма может происходить двумя путями:

1. Базовые элементы могут соединяться в последовательность, образуя

конструкцию следования.

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

внутри составных команд могут быть использованы другие составные команды.

 Алгоритм может развиваться как “вширь” подключением в цепочку новых конструкций,

так и “вглубь” включением одних конструкций в другие.

Алгоритм сначала формулируется в общих чертах, а затем уточняется путем

детализации более крупных действий через более мелкие. Это метод пошаговой

детализации или метод “сверху вниз”. При построении алгоритма по принципу «сверху

вниз» задача разбивается на более простые подзадачи. Если для какой-то подзадачи уже

построен алгоритм, то он может быть включен в разрабатываемый алгоритм.

Готовые алгоритмы, целиком включаемые в состав разрабатываемого алгоритма,

называют вспомогательными или подчиненными алгоритмами.

;

Подпрограммы — вспомогательные алгоритмы, записанные на языках

программирования.

S Для работы с целыми числами в языках программирования используются стандартные

функции div — деление нацело и mod — остаток от деления нацело.

S Результатом выполнения операции x div y будет целое число, округленное по

направлению к 0, например, 17 div 8 = 2, 3 div 5 = 0.

S Результатом выполнения операции x mod y = x – (x div y)*y будет целое число —

остаток от деления нацело x на y, например, 17 mod 8 = 1, 3 mod 5 = 3.

S Операции *, /, div, mod имеют одинаковый приоритет.

S Определить значения переменных a и b после вычисления выражений:

a := 15 div (16 mod 7), b := 34 mod a*5 – 29 mod 5*2. (Ответ: a = 7, b = 22)

4 СТРУКТУРЫ ДАННЫХ

Задачи, решаемые на ЭВМ — это математические модели процессов или явлений

реальной жизни, в которых отражены наиболее существенные связи между реальными

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

структуры данных. При решении задачи на ЭВМ структуры алгоритмов отображаются на

структуру машинного языка, а структуры данных отображаются на структуру машинной

памяти.

Память ЭВМ имеет дискретную структуру и состоит из линейной последовательности

элементов, называемых ячейками. Каждая ячейка может содержать одно значение — машинное

слово.

;

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

Каждая простая переменная характеризуется одним значением. При отображении

на память ЭВМ имени простой переменной ставится в соответствие номер ячейки памяти,

в которой хранится значение этой переменной.

;

Массив — структура, состоящая из множества элементов, упорядоченных в

соответствии со значениями индексов.

В зависимости от числа индексов различают массивы одномерные, двумерные и

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

обеспечивается прямой доступ к любому элементу массива.

;

Очередь — структура данных, организованная по принципу «первым пришел —

первым ушел».

Обработка элементов очереди ведется последовательно один за другим. Элемент,

который первым попал в очередь, первым и обрабатывается и при этом покидает очередь.

Добавление новых элементов производится в конец очереди.

;

Стек — структура данных, организованная по принципу «последним пришел —

первым ушел».

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

элементы продвигаются вниз без изменения порядка. При выборке из стека выбирается

элемент из его вершины, а все остальные элементы без изменения порядка сдвигаются

вверх, так что в вершину попадает элемент, поступивший в стек предпоследним. Стек

можно отобразить на одномерный массив. Значение i = 0 перед чтением из стека служит

признаком того, что стек пуст, а значение i = n (n — размерность массива) перед записью в

стек — признаком того, что стек переполнен.

;

Строка — структура данных, описывающая последовательность символов из

некоторого алфавита.

S Дан фрагмент алгоритма, в котором переменные a, b, c имеют тип «строка»,

переменные i, k — тип «целое». Значения строк записываются в одинарных кавычках, например,

b:= ‘память’.

Используются функции:

Длина(а) — возвращает количество символов в строке а (тип «целое»).

Извлечь(a,i) — возвращает i-ый символ в

строке а, начиная слева (тип «строка»).

Склеить(a,b) — возвращает строку, в которой записаны подряд символы строки а, затем

строки b.

а:= ‘ИНФОРМАТИКА’

i:= Длина(а) – 5

k:= 1

b:=’A’

пока i > 2

нц

с:= Извлечь(a,i)

b:= Склеить(с,b)

i:= I – k

кц

Определить значение переменной b после завершения работы алгоритма. Заполнить

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

начала

цикла. Сколько раз выполнился цикл?

A i k c b

ИНФОРМАТИКА 6 1 А

… … … …

S Элементы массива D[1..5] равны соответственно 3, 4, 5, 1, 2. Определить значение

выражения D [D [5] ] – D [D [3] ]. (Ответ: 2)

S Дан фрагмент программы:

цел таб А[1..12,1..12]

нц

для i:=1 до 12

нц

для j:= 1 до 12

если mod(I + j, 2) = 0

то А[i, j] = 0

иначе А[i, j] = 1

кц

Определить значение суммы A[1, 6] + A[2, 7] + A[3, 8] + A[4, 9] + A[5, 10] после выполнения

фрагмента программы. (Ответ: 5)

Комментарий к решению. Для заполнения двумерного массива требуется два

цикла для:

внешний — для ввода по строке и внутренний (вложенный) — для ввода по столбцам. Заполнение

матрицы А[12, 12] происходит по правилу: если сумма индексов элемента матрицы четна, то

элементу присваивается значение 0, иначе — 1. После заполнения матрицы нечетные строки будут

иметь вид 0101…01, а четные — 1010…10. В вычисляемой сумме у всех входящих в нее элементов

сумма

индексов нечетна, поэтому все элементы равны 1. Сумма пяти единиц равна 5.

5 КОМАНДЫ И ПРОГРАММЫ

5.1 МАШИННЫЕ КОМАНДЫ

Решение задач на ЭВМ реализуется программным способом, то есть, путем

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

;

Операционная часть команды — это группа разрядов в команде, предназначенная

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

;

Адресная часть команды — это группа разрядов в команде, в которых

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

информации.

Часто эти адреса называются адресами операндов, т. е. чисел, участвующих в

операции.

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

безадресные, одно-, двух- и трехадресные.

Типовая структура трехадресной команды

КОП А1 А2 А3

КОП — код операции; А1 и А2 — адреса ячеек (регистров), где расположены

соответственно первое и второе числа, участвующие в операции; А3 — адрес ячейки

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

Типовая структура двухадресной команды

КОП А1 А2

А1 — обычно адрес ячейки (регистра), где хранится первое из чисел,

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

результат; А2 — обычно адрес ячейки (регистра), где хранится второе участвующее в

операции число.

Типовая структура одноадресной команды

КОП А1

А1 — в зависимости от модификации команды может обозначать либо адрес

ячейки (регистра), где хранится одно из чисел, участвующих в операции, либо адрес

ячейки (регистра), куда следует поместить число — результат операции.

 Безадресная команда содержит только код операции; информация для нее должна

быть заранее помещена в определенные регистры машины. Безадресные команды могут

использоваться только совместно с командами другой адресности.

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

• операции пересылки информации внутри ПК;

• арифметические операции над информацией;

• логические операции над информацией;

• операции обращения к внешним устройствам ПК;

• операции передачи управления;

• обслуживающие и вспомогательные операции.

 Операции передачи управления (ветвление программы) служат для изменения

естественного порядка выполнения команд. Бывают операции безусловной и условной передачи

управления.

 Операции безусловной передачи управления требуют выполнения не следующей по

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

 Операции условной передачи управления также требуют передачи управления по

адресу, указанному в адресной части команды, в случае, если выполняется некоторое заранее

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

5.2 СВОЙСТВА ЦИФРОВЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИН

Основными свойствами цифровой вычислительной машины (ЦВМ) являются

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

скорость вычислений.

Сущность программного управления заключается в том, что сигналы управления

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

Источниками информации о требуемых типах сигналов на каждом шаге вычислений

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

последовательности команд, закодированных в цифровой форме, записывается в память

ЦВМ до начала вычислений. Поскольку команды программы внутри ЦВМ неотличимы от

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

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

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

S Принципы программного управления (фон Нейманом, 1945 г.)

1. Исходные данные и результаты кодируются обычно в двоичной форме и

разделяются на единицы информации — слова.

2. Правила вычисления используют операторы-преобразователи и операторы-

распознаватели. Первые обеспечивают выполнение операций над элементами

информации, вторые

— управление порядком выполнения операторов

посредством анализа элементов информации.

3. Каждый оператор кодируется командой.

;

Команда — это указание где расположены данные, над которыми должно быть

выполнено действие на аппаратном уровне.

;

Операнды — данные, над которыми выполняется операция.

;

Программа — последовательность команд.

4. Слова информации размещаются в ячейках памяти и определяются адресами

— номерами ячеек.

;

Алгоритмическая универсальность — способность ЦВМ решать

вычислительные и логические задачи из любой области человеческой деятельности.

Это достигается включением в состав набора операций, выполняемых машиной,

действий, необходимых для реализации любых алгоритмов преобразования цифровой

информации.

;

Точность вычислений — мера погрешности, определяемая абсолютными и

относительными ошибками.

;

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

зависит от структуры ЦВМ и быстродействие отдельных ее частей.

В ЦВМ кроме электронных элементов имеются электронно-механические

элементы с относительно низким быстродействием. Поэтому в структуре ЦВМ

необходимо согласовать потоки обрабатываемой информации так, чтобы скорость работы

машины определялась быстродействием наиболее ее быстродействующих элементов

S Общие принципы функционирования ЭВМ (по фон Нейману)

1. Принцип программного управления. Обеспечивает автоматизацию процессов

вычислений на ЭВМ.

2. Принцип однородности памяти. Отсутствие принципиальной разницы

между программой и данными дает возможность ЭВМ самой формировать

программу в соответствии с результатами вычислений.

3. Принцип адресности. Структурно основная память состоит из

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

ячейка.

4. Принцип двоичного кодирования. Вся информация, поступающая в ЭВМ

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

5.3 ТРАНСЛЯЦИЯ И ВЫПОЛНЕНИЕ ПРОГРАММ

;

Исходный модуль — текст алгоритма задачи, описанный средствами языка

программирования (ЯП).

;

Компиляция (интерпретация) — процедура перевода исходного модуля (ИМ) в

последовательность команд ЭВМ.

Компилятор транслирует весь текст ИМ в машинный (объектный) код за один

непрерывный процесс.

Компоновщик собирает программу из объектных модулей и стандартных

библиотечных модулей.

;

Исполняемый файл — это файл, который может быть выполнен компьютером без

предварительной трансляции.

Исполняемый файл получается в результате компиляции и компоновки объектных

модулей и содержит машинные команды и/или команды операционной системы.

Перед выполнением программы ее объектный модуль (ОМ) обрабатывается

редактором связей (РС), создающим загрузочный модуль (ЗМ). Загрузчик определяет для

ЗМ абсолютные адреса в ОП, после чего программа может выполняться.

ИМ→ компилятор с ЯП → ОМ → РС → ЗМ → загрузчик → выполняемый ЗМ

Интерпретатор выполняет ИМ программы в режиме «оператор за оператором»,

превращая каждый оператор ЯП в машинные команды.

Различия: присутствие в ОП компилятора после получения ОМ необязательно;

присутствие в ОП интерпретатора обязательно в период выполнения исходной

программы.

S При работе с программами существуют этапы:

a. компиляции,

b. компоновки,

c. интерпретации,

d. исполнения программы.

Выполнение каких этапов предполагает создание исполняемого файла из исходного

текста программы?

S Режим интерпретации можно использовать для ...

a. отладки программ на языке высокого уровня;

b. изменения синтаксиса языка программирования;

c. изменения семантики языка программирования;

d. компоновки программ на языке

высокого уровня.

S Для решения задачи на ЭВМ необходимо выполнить следующие этапы:

1. Формализация данных (определяются исходные данные).

2. Создание математической модели (модель решения).

3. Детальное описание алгоритма (блок-схема).

4. Реализация на языке программирования.

5. Отладка (устранение явных некорректных ситуаций реализации алгоритма).

6. Тестирование программы (устранение скрытых и явных недостатков исходной задачи).

7. Анализ результатов работы (

исследование полученных результатов).

6 КЛАССЫ МОДЕЛЕЙ. МОДЕЛИРОВАНИЕ

6.1 КЛАССИФИКАЦИЯ МОДЕЛЕЙ

;

Модель — это упрощенное подобие реального объекта, процесса или явления, его

образец.

 Слово «модель» происходит от латинского «modulus», что в переводе означает

«образец».

Модель должна отражать существенные черты объекта, процесса или явления,

чтобы сделанные по модели выводы можно было применить ко всему объекту, процессу

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

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

Модели делятся на универсальные и специализированные. К универсальным

относятся базы данных, системы управления базами данных, автоматизированные системы

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

предназначены для описания конкретных систем. Модели также можно разделить на

предметные (материальные) и информационные.

Предметные модели воспроизводят физические, геометрические,

функциональные свойства объектов в материальной форме и связаны с конкретными

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

;

Информационная модель — это связанная совокупность информационных

объектов, описывающих информационные процессы в исследуемой предметной

области.

Информационные модели представляют объекты в образной (фотографии,

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

формах. Знаковые модели можно подразделить на группы:

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

объекте-оригинале, например, милицейский протокол);

• табличные (например, таблица с данными о планетах Солнечной системы,

хроника событий);

• математические;

• компьютерные.

Указать объекты, относящиеся к информационным/предметным моделям:

1. декорации театральной постановки;

2. эскизы костюмов для олимпийской сборной;

3. географический атлас;

4. объемная модель молекулы воды;

5. уравнение Больцмана;

6. макет скелета динозавра;

7. формула площади квадрата;

8. расписание движения поездов;

9. схема метрополитена;

10. игрушечный вездеход.

По фактору времени различают динамические и статические модели.

Динамические модели используют для описания развития объектов, процессов,

явлений во времени. Например, химическая реакция, движение планет.

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

времени. Например, строение кристалла замороженной воды.

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

игровые (модель самолета

), учебные (модель-тренажер автомобиля).

;

Модель «материальная точка» — это абстракция, позволяющая изучать

движение объекта без учета его размеров.

S В рамках механики материальная точка может быть моделью как песчинки, так и слона

или планеты Земля.

Термин «черный ящик» используется в точных науках для обозначения системы

со сложным или неизвестным механизмом работы.

 Модель «черного ящика» была предложена У. Р. Эшби.

Рис. 5 Модель «черного ящика»

«Черный ящик» позволяет изучать реакцию системы на различные внешние

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

устроена.

S Основной принцип, лежащий в основе моделей типа «черный ящик» — реакция на

заданные входные данные.

 «Гелиоцентрическая модель мира» принадлежит Н. Копернику, сформулирована в

семи утверждениях и является описательной информационной моделью.

6.2 МОДЕЛИРОВАНИЕ

;

Моделирование — это процедура построения моделей для исследования и изучения

объектов, процессов, явлений.

;

Моделирование — это процесс замены объекта, процесса, явления моделью,

отражающей его существенные признаки.

В моделировании используют инструменты познания (понимание устройства и

поведения объекта), прогнозирования (предположение характеристик и поведения

объекта), планирования и управления (воздействия, позволяющие достичь цель).

Имитационное моделирование используется для воспроизведения алгоритма

функционирования системы во времени. По сведениям о состоянии системы в

определенные моменты времени можно оценить характеристики системы в целом.

Например, имитация ядерных процессов позволяет исследовать характер ядерного взрыва

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

Геоинформационное моделирование предполагает создание многослойных

электронных карт. Опорный слой описывает географию некоторой территории. Вторичные

слои объектов (городов, дорог, численности населения) отражают состояние этой

территории.

Натурное моделирование выполняется на реальном объекте при специально

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

подобия.

При натурном моделировании в модели узнается моделируемый объект. Натурная

модель всегда имеет визуальное сходство с объектом-оригиналом.

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

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

• комплексные испытания (серия испытаний, например, на безотказную

работу компьютера);

• производственный эксперимент (обобщение опыта, накопленного в ходе

производственного процесса).

«Черный ящик»

Ввод исходных

данных

Результат

(

зависит от входа

)

S Статистическое моделирование используется, например, для получения прогноза

загруженности автобусного маршрута в течение дня.

S Технология решения задачи при помощи компьютерного моделирования

предполагает выполнение таких этапов как:

1. Постановка задачи. Описание исходной задачи, исходных данных,

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

2. Разработка концептуальной модели. Формулировка представлений и

упрощений, выделение существенных элементов и взаимосвязей в виде схем, диаграмм

или сжатого лаконичного описания.

3. Разработка математической модели (формализация). Описание

концептуальной модели на математическом («формальном») языке.

4. Алгоритмизация задачи. Разработка алгоритма, представляющего

математическую модель в виде последовательности операций.

5. Кодирование алгоритма. Переложение алгоритма на язык программных

средств.

6. Тестирование (отладка). Выявление и устранение ошибок.

7. Использование компьютера для анализа функционирования модели,

прогнозирования ее поведения, принятия решений.

8. Интерпретация результатов. Формулировка выводов и следствий

полученных прогнозов.

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

итерационным (циклическим).

 В середине 80-х гг. XX века в Японии был создан первый нейрокомпьютер,

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

распознавание образов.

 Идею мысленного эксперимента к воображаемому телу, свободному от всех внешних

воздействий, впервые выдвинул и применил Г. Галилей (1564-1642) — итальянский физик,

механик, астроном, философ и математик.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Сущность компьютеризации и информатизации общества.

2. Какая элементная база была у разных поколений ЭВМ?

3. Что такое мера информации?

4. Какова связь количества информации и энтропии, хаоса в системе?

5. Какие виды комбинаций конечного счетного множества элементов

рассматриваются в комбинаторике?

6. Назовите базовые логические операции булевой алгебры.

7. В чем заключается формализация высказываний?

8. Перечислить основные особенности алгоритма.

9. Как происходит выборка данных из стека?

10. Назвать типовые структуры машинных команд.

11. В каких формах представляются информационные модели?

12. Для чего используется имитационное моделирование?

Модуль 2

ПРЕДСТАВЛЕНИЕ ИНФОРМАЦИИ В ЭВМ

1 СИСТЕМЫ СЧИСЛЕНИЯ ........................................................................................................................................ 31

1.1 Основные понятия ........................................................................................................................................ 31

1.2 Перевод чисел ................................................................................................................................................ 32

2 СПОСОБЫ ПРЕДСТАВЛЕНИЯ ЧИСЕЛ В ЭВМ .................................................................................................... 34

2.1 Формы представления чисел ....................................................................................................................... 34

2.2 Представление информации в эвм ............................................................................................................. 35

3 АРИФМЕТИЧЕСКИЕ ОСНОВЫ .............................................................................................................................. 36

3.1 Двоичная арифметика .................................................................................................................................. 36

3.2 Прямой, обратный, дополнительный коды ................................................................................................ 38

3.3 Модифицированные коды ............................................................................................................................. 40

3.4 Сложение по модулю ..................................................................................................................................... 41

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

ПОСЛЕ ИЗУЧЕНИЯ МОДУЛЯ ВЫ ДОЛЖНЫ ЗНАТЬ:

¾ Представление чисел в позиционных системах счисления.

¾ Что означает однородность системы счисления.

¾ Чем разряд отличается от разрядности.

¾ Как нумеруются разряды.

¾ Правило перевода целых чисел из одной системы счисления в другую.

¾ Правило перевода правильной дроби из одной системы счисления в другую.

¾ Правило перевода смешанных чисел из

одной системы счисления в другую.

¾ Представление чисел в формате с фиксированной точкой.

¾ Представление чисел в формате с плавающей точкой.

¾ Что означает процедура нормализации числа.

¾ Представление двоично-кодированных десятичных чисел в упакованном и распакованном

форматах.

¾ Правила выполнения арифметических действий в различных системах счисления.

¾ Для чего

нужны обратный и дополнительный коды.

¾ В каком случае возникает переполнение разрядной сетки.

¾ В чем заключается модификация обратного и дополнительного кодов.

¾ Правила суммирования чисел в прямом, обратном, дополнительном и модифицированных

кодах.

¾ Правило сложения по модулю.

РЕЗУЛЬТАТ:

¾ Получение представления о различных системах счислеия, преобразованиях чисел и

выполнении над ними арифметических операций.

¾ Формирование начальной профессиональной базы для успешного овладения такими

дисциплинами как «Организация ЭВМ и систем».

¾ Пополнение профессионального словарного запаса.