Лекция 1 ПРЕДМЕТ, МЕТОД, СТРУКТУРА И ОСНОВНЫЕ ЗАДАЧИ ДИСЦИПЛИНЫ «ТЕОРИЯ ЭКОНОМИЧЕСКИХ УЧЕНИЙ». ЭКОНОМИЧЕСКАЯ МЫСЛЬ ЭПОХИ НАТУРАЛЬНО-ХОЗЯЙСТВЕННЫХ ОТНОШЕНИЙ
Лекция 3: Кодирование и шифрование информации.
Рассматриваются основные понятия кодирования и шифрования информации, защиты информации и антивирусной защиты.
XVIII ).
Для изображения десятичных дробей используется подобная формула разложения по степеням основания.
Для перевода из 2-ной в 8-ную и наоборот, из 2-ной в 16-ную и наоборот, из 8-ной в 16-ную и обратно, используется таблица следующего вида:
ОСНОВАНИЕ СИСТЕМЫ
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
При переводе в 8-ную систему или из нее необходимо группировать в тройки биты, а при переводе в 16-ную или из нее – группировать их в четверки битов. Можно добавлять, если нужно, незначащие нули (слева от целой части и справа от мантиссы) или отбрасывать их.
Пример. Рассмотрим переводы в смешанных системах.
Из 2-ной системы в 8-ную (двоично-восьмеричное изображение):
из 8-ной системы в 2–ную (восьмерично-двоичное изображение):
из 2-ной системы в 16-ную (двоично-шестнадцатеричное изображение):
из 16-ной системы в 2-ную (шестнадцатерично-двоичное изображение):
Сложение в двоичной системе счисления осуществляется по правилам
0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 210 = 102 (единица идет в старший разряд).
Таблица вычитания в двоичной системе счисления имеет вид
Обратным кодом числа в системе с основанием р называется число в этой системе, получаемое заменой цифры, символа в каждом разряде числа на его дополнение до максимальной цифры в системе (то есть до р – 1).
Дополнительный код = обратный код + единица в младшем разряде.
Пример.
10011 двоичное число,
01100 обратный код этого двоичного числа,
01101 дополнительный код этого двоичного числа;
457 восьмеричное число,
321 дополнительный код;
А9 шестнадцатеричное число,
57 дополнительный код.
Вычитание с помощью дополнительного кода: найти дополнительный код вычитаемого такой же разрядности, как и уменьшаемое, и сложить этот код с уменьшаемым. Результатом вычитания будет полученная сумма без учета старшего разряда (отбрасывается).
Пример. Выполним вычитание напрямую и через сложение (через дополнительный код):
Целые числа в математике и их аналоги в n-разрядных арифметиках тождественны (по количеству) в рамках их представления с этой разрядностью. При этом можно отметить основные отличия представления чисел в поле памяти человека и в поле памяти n-разрядной арифметики:
бесконечное и счетное множество целых чисел представляется отрезком [–N; +N], где N – максимальное число, представимое в этой арифметике (многоточие – общее число единиц, равное n): N = (111 . . . 1)2 ;
бесконечное и несчетное множество действительных чисел , располагающееся на числовой оси равномерно и плотно, представляется в n-разрядной арифметике множеством с неравномерной плотностью (сгущение у нуля и сжатость со стороны меньших чисел);
нуль во множестве действительных чисел в любой своей окрестности имеет множество чисел, а нуль в n-разрядной арифметике представлен изолированно.
С точки зрения обычной арифметики, например, в интервале (–1; 1) имеется бесконечное множество "плотно" расположенных точек, причем в любой окрестности каждой такой точки имеется хотя бы одна точка из этого множества. Такую арифметику называют часто регулярной арифметикой. Машинная же арифметика имеет следующие особенности. Она нерегулярна – точки интервала сгущаются около нуля; кроме того, в этом интервале точка х "изолирована" – если взять любую ее окрестность (х – а; х + а), где а – число, которое не превосходит машинного нуля (наименьшего представимого в машине числа), то в этом интервале нет других точек (отличных от х). Говоря языком теории вероятности, плотности распределения чисел в регулярной и нерегулярной арифметике – различны, как, впрочем, плотности распределения целых и вещественных чисел в одной и той же арифметике. Множество вещественных чисел в машинной арифметике представляется как подмножество (определяемое разрядностью арифметики) множества рациональных чисел. Есть и другие особенности этих множеств (связанные, например, с выполнением операций), но указанные выше особенности – основные.
Различия в представлении чисел в обычной и в машинной (n-разрядной) арифметике ограничивают как "математические" возможности компьютера, так и "компьютерные" возможности математики, использование математических методов, алгоритмов в компьютерах.
Нужно всегда иметь в виду, что точность в теоретической математике – понятие абстрактное и в практической математике может возникать иллюзия точности там, где ее на самом деле нет, – если нет корректной договоренности о пределах возможных значений неизбежных погрешностей в рамках рассматриваемых вычислительных ресурсов, например, трудоемкости и времени, а также не оговорена стратегия управления этой погрешностью.
Так как диапазон n-разрядных чисел системы счисления с основанием p находится в пределах , то для представления дробных чисел этот диапазон еще снижается, поскольку часть разрядов необходимо отвести под изображение мантиссы. Таким образом, имеются так называемые "зоны нечувствительности" форм представления чисел в n-разрядных арифметиках.
В 1937 году Конрадом Цузе для увеличения диапазона чисел, представимых в арифметике двоичных чисел, а также для повышения точности этого представления чисел было предложено представление чисел в плавающей, нормализованной форме – число x представляется в виде: , где m – мантисса числа, k – целый порядок числа, .
Пусть даны два числа: и (). Тогда можно проверить, что результаты выполнения операций будут равны:
Если из n разрядов, отводимых под изображение чисел, m двоичных разрядов отвести под мантиссу, k – под порядок, один разряд – под знак числа и один разряд – под знак порядка (например, 0 – плюс, 1 – минус), то диапазон представимых в форме с плавающей запятой чисел резко увеличивается (m + k + 2 = n):
(многоточие соответствует k единицам).
Числа, меньшие нижней границы положительных чисел и большие верхней границы отрицательных чисел, считаются равными нулю, не различаются между собой. Числа, большие верхней границы положительных чисел, полагаются равными положительной бесконечности (меньшие нижней границы отрицательных – отрицательной бесконечности). Сравнение двух разных по величине чисел в арифметике с ограниченной разрядностью может поэтому приводить к неверному результату, как и сравнение двух равных в таких системах чисел с точки зрения математической.
Такое представление очень удобно для хранения в ЭВМ, так как на самом деле необходимо хранить не само число, а его знак, мантиссу, порядок и знак порядка, и все операции с числами сводятся к операциям с этими объектами. Операции же с этими объектами просты: сравнение знаков, увеличение, уменьшение порядка, сложение мантисс, нормализация, то есть в конечном итоге сводятся к достаточно просто реализуемым операциям сдвига, выравнивания, сравнения разрядов.
Лекция 5: Высказывания и предикаты Рассматриваются основные понятия и сведения алгебры высказываний и предикатов – высказывания, предикаты, аксиомы, логические выражения и функции, эквивалентные выражения и приведение к эквивалентному выражению, другие сопутствующие понятия и факты логики, а также инфологические задачи.
Информатика, как было рассмотрено выше, изучает знаковые (алфавитные) системы. Алгебра – наиболее адекватный математический аппарат описания действий в них, поэтому алгебраический аппарат наилучшим образом подходит для описания информационных систем общей природы, отвлеченно от их предметной направленности. Информационные процессы хорошо формализуются с помощью различных алгебраических структур.
Алгеброй A называется некоторая совокупность определенных элементов X, с заданными над ними определенными операциями f (часто определяемые по сходству с операциями сложения и умножения чисел), которые удовлетворяют определенным свойствам – аксиомам алгебры .
Операция f называется n-местной, если она связывает n операндов (объектов – участников этой операции).
Совокупность операций алгебры A называется ее сигнатурой , а совокупность элементов алгебры – носителем алгебры.
Утверждение (высказывательная форма) – основная единица, неделимая с точки зрения отражения смысла информации (семантики).
Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать ("сразу посмотрев на него"), истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "истина" и "ложь", "true" и "fаlse" или "1" и "0".
Переменная, значениями которой могут быть лишь значения "1" или "0", называется логической переменной или булевой переменной.
Пример. Рассмотрим словосочетания:
Москва – столица США.
Житель города Москва.
5 – 7 + 8.
5 – 9 + 28 = 4.
В пятую неделю зимы было очень холодно.
В Антарктиде живут тигры.
Высказывание должно быть однозначно истинным или однозначно ложным, поэтому высказываниями являются только утверждения 1), 4), 6).
Предикат – высказывательная форма с логическими переменными (множество значений этих переменных вполне определено), имеющая смысл при любых допустимых значениях этих переменных. Количество переменных в записи предиката называется его местностью.
Простые высказывания или предикаты не зависят от других высказываний или предикатов ("не разбиваемы на более простые"), а сложные – зависит хотя бы от двух простых.
Логической (булевой) функцией f(х) называется некоторая функциональная зависимость, в которой аргумент х – логическая переменная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}.
Операции импликации и эквиваленции, хотя и являются часто используемыми, но не базовые, ибо они определяемы через три введенные выше базовые операции. Нетрудно определить их таблицы истинности (проделайте это самостоятельно с помощью правых частей приведенных равенств).
При выполнении логических операций в компьютере они сводятся к поразрядному сравнению битовых комбинаций. Эти операции достаточно быстро (аппаратно) выполняемы, так как сводятся к выяснению совпадения или несовпадения битов.
В логических формулах определено старшинство операций, например: скобки, отрицание, конъюнкция, дизъюнкция (остальные, небазовые операции пока не учитываем).
Всегда истинные формулы называют тавтологиями .
Логические функции эквивалентны, если совпадают их таблицы истинности, то есть совпадают области определения и значения, а также сами значения функции при одних и тех же наборах переменных из числа всех допустимых значений. Если это совпадение происходит на части множества допустимых значений, то формулы называются эквивалентными лишь на этой части (на этом подмножестве).
Задача упрощения логического выражения состоит в преобразовании его к более простому (по числу переменных, операций или операндов) эквивалентному выражению. Наиболее простой вид получается при сведении функции к постоянной – 1 (истина) или 0 (ложь).
Информационно-логическая (инфологическая) задача – это задача, в которой необходимо установить некоторые информационные или логические связи и сделать необходимые причинно-следственные логические выводы. Эти задачи возникают в различных областях и часто являются плохо формализованными и структурированными. Их нужно хорошо формализовать и структурировать. Насколько хорошо будет возможно это сделать – настолько хорошо и полно будет решена рассматриваемая проблема или задача. Рассмотрим пример информационно-логической задачи (например, решаемой следователем, знакомым с алгеброй предикатов).
6. Лекция: Логические вентили, схемы, структуры Рассматриваются основные теоретические (математические, логические) понятия и сведения, касающиеся базовых логических элементов и структур – логических вентилей, логических (переключательных) схем, логической базы аппаратуры ЭВМ и их оптимальной структуры, оптимизации их структур.
Любой, самый примитивный компьютер – сложнейшее техническое устройство. Но даже такое сложное устройство, как и все в природе и в технике, состоит их простейших элементов. Любой компьютер, точнее, любой его электронный логический блок состоит из десятков и сотен тысяч так называемых вентилей (логических устройств, базовых логических схем), объединяемых по правилам и законам (аксиомам) алгебры вентилей в схемы, модули.
Логический вентиль (далее – просто вентиль) – это своего рода атом, из которого состоят электронные узлы ЭВМ. Он работает по принципу крана (отсюда и название), открывая или закрывая путь сигналам.
Логические схемы предназначены для реализации различных функций алгебры логики и реализуются с помощью трех базовых логических элементов (вентилей, логических схем или так называемых переключательных схем). Они воспроизводят функции полупроводниковых схем.
Работу вентильных, логических схем мы, как и принято, будем рассматривать в двоичной системе и на математическом, логическом уровне, не затрагивая технические аспекты (аспекты микроэлектроники, системотехники, хотя они и очень важны в технической информатике).
Логические функции отрицания, дизъюнкции и конъюнкции реализуют, соответственно, логические схемы, называемые инвертором, дизъюнктором и конъюнктором.
Логическая функция "инверсия", или отрицание, реализуется логической схемой (вентилем), называемой инвертор.
Принцип его работы можно условно описать следующим образом: если, например, "0" или "ложь" отождествить с тем, что на вход этого устройства скачкообразно поступило напряжение в 0 вольт, то на выходе получается 1 или "истина", которую можно также отождествить с тем, что на выходе снимается напряжение в 1 вольт.
Аналогично, если предположить, что на входе инвертора будет напряжение в 1 вольт ("истина"), то на выходе инвертора будет сниматься 0 вольт, то есть "ложь" (схемы на рисунках 6.1 а, б).
Принцип работы инвертора
Функцию отрицания можно условно отождествить с электрической схемой соединения в цепи с лампочкой (рис. 6.2), в которой замкнутая цепь соответствует 1 ("истина") или х = 1, а размыкание цепи соответствует 0 ("ложь") или х = 0.
Из указанных простейших базовых логических элементов собирают, конструируют сложные логические схемы ЭВМ, например, сумматоры, шифраторы, дешифраторы и др. Большие (БИС) и сверхбольшие (СБИС) интегральные схемы содержат в своем составе (на кристалле кремния площадью в несколько квадратных сантиметров) десятки тысяч вентилей. Это возможно еще и потому, что базовый набор логических схем (инвертор, конъюнктор, дизъюнктор) является функционально полным (любую логическую функцию можно представить через эти базовые вентили), представление логических констант в них одинаково (одинаковы электрические сигналы, представляющие 1 и 0) и различные схемы можно "соединять" и "вкладывать" друг в друга (осуществлять композицию и суперпозицию схем).
Таким способом конструируются более сложные узлы ЭВМ – ячейки памяти, регистры, шифраторы, дешифраторы, а также сложнейшие интегральные схемы.
7. Лекция: Базовые алгоритмические структуры Рассматриваются основные понятия об алгоритме в программах и алгоритмизации решения задач.
"Алгоритм" является базовым основополагающим понятием информатики, а алгоритмизация (программирование) – основным разделом курса информатики (ядром курса). Понятие алгоритма, как и понятие информации, точно определить невозможно. Поэтому встречаются самые разнообразные определения – от "наивно-интуитивных" ("алгоритм – это план решения задачи") до "строго формализованных" (нормальные алгоритмы Маркова).
В качестве рабочего определения алгоритма возьмем следующее определение.
Алгоритм – это упорядоченная совокупность точных (формализованных) и полных команд исполнителю алгоритма (человек, ЭВМ), задающих порядок и содержание действий, которые он должен выполнить для нахождения решения любой задачи из рассматриваемого класса задач.
Алгоритм удовлетворяет следующим основным свойствам:
Конечность (дискретность) команд и выполняемых по ним действий алгоритма.
Выполнимость в определенной операционной среде (в определенном классе исполнителей).
Результативность отдельных команд и всего алгоритма.
Применимость алгоритма ко всем возможным входным данным конкретного класса задач.
Определенность (детерминированность) команд и всего алгоритма для всех входных данных.
Формализованное, конструктивное описание (представление) команд алгоритма.
Минимальная полнота системы команд алгоритм.
Непротиворечивость любых команд алгоритма на любом наборе входных данных.
Любой алгоритм ориентирован на некоторый общий метод решения класса задач и представляет собой формализованную запись метода, процедуры.
Алгоритм, записанный на некотором алгоритмическом, формальном языке, состоит из заголовка алгоритма (описания параметров, спецификаций класса задач) и тела алгоритма (последовательности команд исполнителя, преобразующих входные параметры в выходные).
Для записи, исполнения, обмена и хранения алгоритмов существуют различные средства, языки, псевдокоды – блок-схемы, структурограммы (схемы Нэсси-Шнайдермана), Р-схемы, школьный алгоритмический язык (ШАЯ), различные языки программирования.
В качестве языка описания алгоритмов нами используется далее язык программирования Паскаль, так как он наиболее подходит для целей обучения и часто (обоснованно) используется в обучении.
На алгоритмическом языке Паскаль любой алгоритм простой (не модульной, не составной) структуры имеет следующий стандартный вид:
Program <имя (заголовок) алгоритма>;
Uses <список подключаемых библиотек, если они нужны>; { комментарии, если нужны }
Label <список меток (имен участков программ), если они нужны>; { комментарии }
Const <список констант (не изменяемых величин), если они нужны>; { комментарии }
Type <список имен и типов структур данных, если они нужны>; { комментарии }
Var <список имен и типов переменных, если они нужны>; { комментарии }
{ < условия задачи и применимости алгоритма > }
{ < цель составления и выполнения алгоритма > }
Begin
<команды ввода входных данных, если они нужны>; { комментарии }
<тело алгоритма (команды управления и преобразования алгоритма)>; { комментарии }
<команды вывода результатов (выходных данных), если они нужны>; { комментарии }
End.
Приведем таблицу наиболее часто используемых в языке Паскаль функций и процедур.
Обычная запись
Паскаль
Квадрат числа х
sqr(x)
Корень квадратный из x
sqrt (x)
Модуль |х|
abs (x)
sin x
sin(x)
cos x
cos(x)
tg x
tg(x)
ctg x
ctg(x)
arcsin x
arcsin (x)
arccos x
arccos(x)
arctg x
arctg(x)
Натуральный логарифм ln x
ln(x)
Степень числа е = 2, 7... или еx
exp(x)
Остаток от деления целого х на целое у
x mod y
Частное от деления целого х на целое y
x div y
Целая часть числа х (вещественного)
int(x)
Случайное число от 0 до х
rnd(x)
Длина текста х в символах
length (x)
Рассмотрим базовые простые команды языка Паскаль.
Команда описания (заголовка) алгоритма (программы) :
Program <имя алгоритма>;,
где <имя алгоритма> – имя, задаваемое составителем программы (краткое, полное, грамотное отражение сути алгоритма).
Ввод – команда ввода в рассмотрение (в тело алгоритма) тех или иных входных параметров:
Read (<список вводимых параметров>);
или
ReadLn (<список вводимых параметров>);.
Первая команда вводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.
Вывод – команда вывода на экран тех или иных входных или выходных параметров алгоритма:
Write (<список выводимых параметров>);
или
WriteLn (<список выводимых параметров>);.
Первая команда выводит данные с текущей позиции экрана (где стоит курсор), вторая – с новой строки экрана.
Присваивание – команда изменения текущего значения переменной вида:
<идентификатор> := <выражение>;,
где <идентификатор> соответствует имени переменной, <выражение> – корректно записанное выражение. Знак ":=" означает последовательное выполнение двух действий: определение текущего значения <выражения> и замена текущего значения переменной, имя которой задано <идентификатором>, на новое значение, равное значению <выражения>.
Команда начала алгоритма (блока) – команда Begin.
Команда завершения алгоритма (блока) – команда End.
Команда вставки комментариев в текст алгоритма имеет вид:
<комментируемое в программе> <текст комментария>.
Комментировать можно любой объект в программе. Обычно комментируют переменную, структуру данных, команду, группу команд.
Различают три базовые алгоритмические структуры: следование, ветвление, повторение.
Структура следование состоит из двух команд с указанной очередностью их выполнения и имеет вид:
<команда – предшественник>;
<команда – преемник>.
Структура типа ветвления в полной форме состоит из некоторого условия, проверяемого на истинность при выполнении структуры, команды, выполняемой при выполнении проверяемого условия, и команды, выполняемой при невыполнении условия. Структура имеет вид
if <условие>
then <команда, выполняемая при выполнении условия>
else <команда, выполняемая при невыполнении условия>;.
Ключевые (служебные) слова Паскаля – if (если), then (то), else (иначе). Ключевые слова нельзя изменять, заменять, так как их эталоны закреплены в переводчике с языка Паскаль (о нем подробнее – ниже).
(при х <= y) текущее значение x заменяем на текущее значение y }.
Структура типа ветвления в неполной форме – частный случай ветвления в полной форме, в которой, при невыполнении условия, управление просто передается следующей команде и больше никаких действий команда ветвления не осуществляет. Эта структура имеет вид
if <условие>
then <команда, выполняемая при исполнении условия>; .
Структура повторения (цикл) служит для компактной записи одного и того же набора команд, повторяемых для различных значений параметров команд.
Структура повторения типа "пока (while)" записывается в виде:
while <условие продолжения повторения> do
<повторяемая команда>;
или
while <условие продолжения повторения> do
begin
<повторяемая команда номер 1>;
<повторяемая команда номер 2>;
. . .
<повторяемая команда номер N>
end;.
Ключевые слова Паскаля – while (пока), do (выполнять), begin (начало), end (конец).
Телом цикла называется последовательность повторяемых команд, которая может быть и пустой (редко встречаемый случай).
Часть команды цикла "while <условие продолжения повторения>" – заголовок цикла.
Данный цикл выполняется по правилу: если условие повторения для текущих его параметров не выполнено, то повторение команд (тела) цикла на этом завершается; если же оно выполнено, то выполняется тело цикла и опять проверяется условие повторения команд тела цикла.
Пример. Пусть необходимо находить сумму всех нечетных элементов натурального ряда чисел до тех пор, пока эта сумма не превысит значение n. Слагаемое, при котором эта сумма превысит n – включать в сумму.
"Забудем" временно чисто математическое решение этой задачи – с использованием суммы арифметической прогрессии с шагом 2. Алгоритмпрограмма) имеет вид
Вторая форма повторения – цикл типа "до" (for), которая имеет вид
for <переменная> := <начальное значение переменной> to <конечное ее значение> do
<команда>;
или
for <переменная> := <начальное значение переменной> to <конечное ее значение> do
begin
<повторяемая команда номер 1>;
<повторяемая команда номер 2>;
. . .
<повторяемая команда номер N>
end;.
Здесь <переменная> – имя, идентификатор пересчитываемой переменной.
Ключевые слова Паскаля – for (для), to (к).
Этот цикл выполняется по правилу: для начального значения переменной выполняются команды тела цикла по порядку и затем проверяется, превысило ли текущее значение переменной ее заданного конечного значения; если превысило – цикл заканчивается, иначе значение переменной увеличивается на единицу и снова повторяется тело цикла и т.д.
8. Лекция: Данные, их типы, структуры и обработка Рассматриваются основные понятия о данных к алгоритмам, их базовые типы и структуры, вопросы их использования в алгоритмизации задач.
Любая актуализация информации опирается на какие-то данные, любые данные могут быть каким-то образом актуализированы.
Данные – это некоторые сообщения, слова в некотором заданном алфавите.
Пример. Число 123 – данное, представляющее собой слово в алфавите из десяти натуральных цифр; число 12,34 – данное, представляющее собой слово в алфавите из десяти натуральных цифр и десятичной запятой; текст "математика и информатика – нужные дисциплины", – данное в алфавите из символов русского языка и знаков препинания, включая пробел.
Текущее (то есть рассматриваемое в данный момент времени) состояние данных называют текущим значением данных или просто значением .
До разработки алгоритма (программы) необходимо выбрать оптимальную для реализации задачи структуру данных. Неудачный выбор данных и их описания может не только усложнить решаемую задачу и сделать ее плохо понимаемой, но и привести к неверным результатам. На структуру данных влияет и выбранный метод решения.
Пример. При решении системы линейных алгебраических уравнений можно воспользоваться методом Крамера (с помощью определителей) или методом Гаусса (с помощью последовательных исключений неизвестных). Метод Крамера потребует при реализации примерно в 3 раза больше операций, чем метод Гаусса, и поэтому им никогда не пользуются при расчетах на ЭВМ.
Тип данных характеризует область определения значений данных.
Задаются типы данных простым перечислением значений типа, например как в простых типах данных , либо объединением (структурированием) ранее определенных каких-то типов – структурированные типы данных .
Пример. Зададим простые типы данных "специальность", "студент", "вуз" следующим перечислением:
специальность = (филолог, историк, математик, медик);
студент = (Петров, Николаев, Семенов, Иванова, Петрова);
вуз = (МГУ, РГУ, КБГУ).
Значением типа "студент" может быть Петров.
Пример. Опишем структурированный тип данных "специальность_студента":
специальность_студента=(специальность, студент).
Значением типа "специальность_студента" может быть пара (историк, Семенов).
Для обозначения текущих значений данных используются константы – числовые, текстовые, логические.
Часто (в зависимости от задачи) рассматривают данные, которые имеют не только "линейную" (как приведенные выше), но и иерархическую структуру.
Пример. Структуру "вуз" можно задать иерархической структурой, состоящей, например, из следующих уровней: "Ректорат", "Деканаты и подразделения", "Кафедры", "Отделы", "Преподаватели и сотрудники".
В алгоритмических языках есть стандартные типы, например, целые, вещественные, символьные, тестовые и логические типы. Они в этих языках не уточняются (не определяются, описываются явно) и имеют соответствующие описания с помощью служебных слов.
Пример. В школьном алгоритмическом языке (ШАЯ), например, целые, вещественные, символьные, текстовые (литерные, стринговые) и логические типы данных описываются ключевыми словами цел, вещ, сим, лит, лог. В языке Паскаль – аналогичными ключевыми словами integer, real, char, string, boolean.
Каждый тип данных допускает использование определенных операций со значениями типа ("с типом").
Пример. Для целого типа данных назовем операции ":=", "+", "–", "*", "=" (сравнение на равенство), "", "<", ">", "", "".. Для вещественного типа данных еще и операция "/" (деление). Для символьного типа данных – только ":=", "=", "", "<", ">", "", "". Например, сравнение "а"<"b" означает, что символ "а" предшествует символу "b" то есть код буквы "a" меньше кода буквы "b" (коды символов приводятся, например, в таблице ASCII – Аmerican Standard Code for Information Interchange, американский стандарт кодирования для обмена данными). Для текстового (литерного) типа данных можно использовать еще и операцию конкатенации (присоединения справа) текстов "+". Например, "аб"+"ба" даст новый текст "абба". Для данных логического типа определены логические операции и отношения сравнения. Например, на Паскале для логических переменных a, b, c можно записать корректное выражение: a and b or (c not a).
Для описания переменных, значениями которых могут быть лишь символы, тексты, используются соответствующие ключевые слова: на ШАЯ – сим, лит, на Паскале – char, string.
Текстовые (символьные) константы обычно заключают в апострофы.
Наиболее часто используемая структура данных – массив.
Одномерный массив (вектор, ряд, линейная таблица) – это совокупность значений некоторого простого типа (целого, вещественного, символьного, текстового или логического типа), перенумерованных в каком-то порядке и имеющих общее имя. Для выделения конкретного элемента массива необходимо указать его порядковый номер в этом ряду.
Пример. Последовательность чисел 89, –65, 9, 0, –1.7 может образовывать одномерный вещественный массив размерности 5, например, с именем x вида: x[1] = 89, x[2] = –65, x[3] = 9, x[4] = 0, x[5] = –1.7.
Значение порядкового номера элемента массива называется индексом элемента.
Пример. Можно ссылаться на элемент х[4], элемент х[i], элемент x[4+j] массива х. При текущих значениях переменных i = 2 и j = 1 эти индексы определяют, соответственно, 4-й, 2-й и 5-й элементы массива.
Для обозначения (нового типа объектов) массивов в алгоритмических языках обычно вводится специальное служебное слово.
Пример. В ШАЯ – это слово "таб", после которого приводится имя массива и в квадратных скобках его размерность, например, для одномерного массива – в виде [m:n], где m – номер первого элемента массива (часто 1), n – номер последнего элемента (шаг перебора элементов равен 1). На Паскале имеется соответствующее слово array. Вышеуказанная последовательность из пяти чисел описывается на ШАЯ в виде: вещ таб x[1:7], а на Паскале (в рамках рассматриваемого нами его ядра) необходимо указывать предельную величину размерности:
x: array [1..100] of real;.
Двумерный массив (матрица, прямоугольная таблица) – совокупность одномерных векторов, рассматриваемых либо "горизонтально" (векторов-строк), либо "вертикально" (векторов-столбцов) и имеющих одинаковую размерность, одинаковый тип и общее имя.
Матрицы, как и векторы, должны быть в алгоритме описаны служебным словом (например, таб или array), но в отличие от вектора, матрица имеет описание двух индексов, разделяемых запятыми: первый определяет начальное и конечное значение номеров строк, а второй – столбцов.
Пример. Если матрица x описана в виде
x: array [1..5, 1..3] of real; ,
то определяется таблицу из 5 строк (от 1-й до 5-й строки) и 3 столбцов (от 1-го до 3-го столбца) вида:
(столбец 1)
(столбец 2)
(столбец 3)
x11
x12
х13
(строка 1)
x21
x22
х23
(строка 2)
х31
х32
х33
(строка 3)
х41
x42
х43
(строка 4)
х51
x52
х53
(строка 5)
Для актуализации элемента двумерного массива нужны два его индекса – номер строки и номер столбца, на пересечении которых стоит этот элемент.
9. Лекция: Методы разработки и анализа алгоритмов Рассматриваются основные понятия о методах проектирования (нисходящем, восходящем, модульном, структурном) и разработки алгоритмов (программ), тестирование и верификация алгоритма, трассировка алгоритма.
Нисходящим проектированием алгоритмов, проектированием алгоритмов "сверху вниз" или методом последовательной (пошаговой) нисходящей разработки алгоритмов называется такой метод составления алгоритмов, когда исходная задача (алгоритм) разбивается на ряд вспомогательных подзадач (подалгоритмов), формулируемых и решаемых в терминах более простых и элементарных операций (процедур). Последние, в свою очередь, вновь разбиваются на более простые и элементарные, и так до тех пор, пока не дойдём до команд исполнителя. В терминах этих команд можно представить и выполнить полученные на последнем шаге разбиений подалгоритмы (команд системы команд исполнителя).
Восходящий метод , наоборот, опираясь на некоторый, заранее определяемый корректный набор подалгоритмов, строит функционально завершенные подзадачи более общего назначения, от них переходит к более общим, и так далее, до тех пор, пока не дойдем до уровня, на котором можно записать решение поставленной задачи. Этот метод известен как метод проектирования "снизу вверх".
Структурные принципы алгоритмизации (структурные методы алгоритмизации) – это принципы формирования алгоритмов из базовых структурных алгоритмических единиц (следование, ветвление, повторение), используя их последовательное соединение или вложение друг в друга с соблюдением определённых правил, гарантирующих читабельность и исполняемость алгоритма сверху вниз и последовательно.
Структурированный алгоритм – это алгоритм, представленный как следования и вложения базовых алгоритмических структур. У структурированного алгоритма статическое состояние (до актуализации алгоритма) и динамическое состояние (после актуализации) имеют одинаковую логическую структуру, которая прослеживается сверху вниз ("как читается, так и исполняется"). При структурированной разработке алгоритмов правильность алгоритма можно проследить на каждом этапе его построения и выполнения.
Теорема (о структурировании). Любой алгоритм может быть эквивалентно представлен структурированным алгоритмом, состоящим из базовых алгоритмических структур.
Одним из широко используемых методов проектирования и разработки алгоритмов (программ) является модульный метод (модульная технология).
Модуль – это некоторый алгоритм или некоторый его блок, имеющий конкретное наименование, по которому его можно выделить и актуализировать. Иногда модуль называется вспомогательным алгоритмом, хотя все алгоритмы носят вспомогательный характер. Это название имеет смысл, когда рассматривается динамическое состояние алгоритма; в этом случае можно назвать вспомогательным любой алгоритм, используемый данным в качестве блока (составной части) тела этого динамического алгоритма. Используют и другое название модуля – подалгоритм. В программировании используются синонимы – процедура, подпрограмма.
Свойства модулей:
функциональная целостность и завершенность (каждый модуль реализует одну функцию, но реализует хорошо и полностью);
автономность и независимость от других модулей (независимость работы модуля-преемника от работы модуля-предшественника; при этом их связь осуществляется только на уровне передачи/приема параметров и управления);
эволюционируемость (развиваемость);
открытость для пользователей и разработчиков (для модернизации и использования);
корректность и надежность;
ссылка на тело модуля происходит только по имени модуля, то есть вызов и актуализация модуля возможны только через его заголовок.
Свойства (преимущества) модульного проектирования алгоритмов:
возможность разработки алгоритма большого объема (алгоритмического комплекса) различными исполнителями;
возможность создания и ведения библиотеки наиболее часто используемых алгоритмов (подалгоритмов);
облегчение тестирования алгоритмов и обоснования их правильности ;
упрощение проектирования и модификации алгоритмов ;
уменьшение сложности разработки (проектирования) алгоритмов (или комплексов алгоритмов);
наблюдаемость вычислительного процесса при реализации алгоритмов.
Тестирование алгоритма – это проверка правильности или неправильности работы алгоритма на специально заданных тестах или тестовых примерах – задачах с известными входными данными и результатами (иногда достаточны их приближения). Тестовый набор должен быть минимальным и полным, то есть обеспечивающим проверку каждого отдельного типа наборов входных данных, особенно исключительных случаев.
Тестирование алгоритма не может дать полной (100%-ой) гарантии правильности алгоритма для всех возможных наборов входных данных, особенно для достаточно сложных алгоритмов.
Полную гарантию правильности алгоритма может дать описание работы и результатов алгоритма с помощью системы аксиом и правил вывода или верификация алгоритма.
Для несложных алгоритмов грамотный подбор тестов и полное тестирование может дать полную картину работоспособности (неработоспособности).
Трассировка – это метод пошаговой фиксации динамического состояния алгоритма на некотором тесте. Часто осуществляется с помощью трассировочных таблиц, в которых каждая строка соответствует определённому состоянию алгоритма, а столбец – определённому состоянию параметров алгоритма (входных, выходных и промежуточных). Трассировка облегчает отладку и понимание алгоритма.
Процесс поиска и исправления (явных или неявных) ошибок в алгоритме называется отладкой алгоритма.
Некоторые (скрытые, труднообнаруживаемые) ошибки в сложных программных комплексах могут выявиться только в процессе их эксплуатации, на последнем этапе поиска и исправления ошибок – этапе сопровождения. На этом этапе также уточняют и улучшают документацию, обучают персонал использованию алгорима (программы).
В заключение данного раздела приведем общую структуру алгоритмического обеспечения. Критерии, по которым алгоритмы могут быть классифицированы, бывают разными, поэтому предлагаемая ниже схема отражает основные элементы структуры и в некоторых случаях является условной, в том смысле, что блоки приведенной на рис. 9.1 структуры могут "перекрываться".
Основные формы использования алгоритмов – автономное, библиотечное, пакетное.
Автономный алгоритм определяется решаемой задачей, структурой используемых данных, структурой логических связей частей (модулей) алгоритма и языком псевдокодов, на котором представлен, описан алгоритм.
Библиотека алгоритмов определяется множеством задач, решаемых с помощью библиотеки, множеством алгоритмов для решения типовых задач некоторой предметной области и структурой используемых данных.
Пакет алгоритмов, как и библиотека, определяется множеством задач, решаемых с помощью пакета, множеством алгоритмов для решения типовых задач или их составных частей из некоторой предметной области, структурой используемых данных и обменов данными между задачами (модулями), специальным языком, на котором формулируется задание (последовательность этапов решаемой задачи, последовательность задач задания).
10. Лекция: Исполнители алгоритмов - человек и автомат Рассматриваются основные понятия о базовых исполнителях алгоритмов – человеке и конечном автомате, об их управляющих и исполняющих подсистемах, структурах.
Исполнителем называется некоторая биологическая, техническая или смешанная структура, способная исполнять (покомандно или программно) некоторый класс алгоритмов в некоторой операционной среде (некотором множестве допустимых "инструментов" и "команд").
Наиболее используемые типы исполнителя алгоритмов – человек или автомат (компьютер).
Человек как исполнитель алгоритмов – совокупность исполняющих подсистем (мышечная, двигательная, зрительная, обонятельная и др.) и управляющей подсистемы (нервная, нейронная).
Нервная система передает информацию, получаемую от нервных окончаний кожи, глаз, ушей и других органов, к нервным центрам для ее последующей интеграции, обработки и выработке адекватной реакции. Нервная система – совокупность взаимодействующих нервных клеток или нейронов. У человека их – громадное количество.
Нейроны служат для передачи информации за счет нервных импульсов, которая расшифровывается в соответствующих областях коры головного мозга.
В непосредственную (сенсорную) память человека поступает информация от различных сенсоров: зрительных, слуховых, обонятельных и т.д. Затем эта информация переводится в оперативную память (память сознания). Далее она пересылается в долговременную память с привлечением подсознания ("укладывается на полочки" с соответствующими названиями "Формы поведения", "Объекты и образы", "Правила и процедуры обнаружения и идентификации объектов", "Правила выборки и организации информации", "Жизненный опыт", "Бытовые навыки и умения", "Профессиональные навыки и умения" и др.).
В живом организме передача, хранение или обработка информации происходит с помощью биохимических реакций и сообщений – сигнальных молекулярных систем и их превращений за счет химических реакций катализа и разностей концентрации химических веществ. Разность потенциалов действий (электрические сигналы) проводят нервные волокна, с помощью центральной нервной системы. При этом используется и генная информация, которая передается от ДНК к РНК, от РНК – к белку, определяя новую белковую структуру, ее функции.
Второй важный тип исполнителей – конечные автоматы , автоматические (то есть функционирующие определенный промежуток времени без участия человека) устройства, вход, выход и состояния которых можно описать конечными последовательностями сообщений (слов над конечными алфавитами).
Любой конечный автомат реализует некий непустой класс алгоритмов и состоит из совокупности управляющего автомата, который определяет порядок выполнения действий, и операционного автомата, реализующего сами действия, выполняемые автоматом.
Компьютер можно рассматривать как совокупность взаимодействующих конечных автоматов. Рассмотрим такую структуру подробнее.
Память компьютера – последовательность ячеек памяти, то есть физических устройств, куда можно записывать или считывать последовательность битов, каждый из которых хранится в нужном разряде.
Команды, как и числа, размещаются (в битовом изображении) в специальных электронных устройствах – так называемых регистрах.
Регистр – электронное устройство, как и ячейка памяти, запомнающее и хранящее (временно) последовательность битов определенной длины. Регистры реализуются более дорогими и чувствительными физическими устройствами и поэтому, по сравнению с основной памятью компьютера, регистровая память или так называемая кэш-память – невелика.
Джон фон Нейман предложил ряд принципов, которые легли в основу фон Неймановской или классической архитектуры компьютера :
память состоит из однородных ячеек памяти с адресами;
программа состоит из последовательных команд;
хранение программы и обрабатываемых ею данных – одинаковое, в битовом виде;
команды выполняются последовательно, данные извлекаются в соответствии с командами;
процессор – один и имеет централизованное управление и доступ к памяти.
Арифметико-логическое устройство (АЛУ) выполняет арифметические, логические операции.
Обмен информацией с компьютером осуществляется устройствами ввода и устройствами вывода.
11. Лекция: Программное и техническое обеспечение: версия для печати и PDA Рассматриваются основные понятия о вычислительной системе – совокупности программного и технического обеспечения, их структура.
Любой компьютер состоит из технического обеспечения (hardware) и функционирует, решает задачи с помощью программного обеспечения (software).
Структура программного обеспечения достаточно сложна и неоднозначна (в том смысле, что все программы не могут быть отнесены к тому или иному классу этой структуры однозначно, односложно). Эта структура несколько условная и производит классификацию программного обеспечения нестрого и только по назначению программ, хотя есть и другие критерии эффективности программного обеспечения (дружественность пользователю, тип использования и т.д.).
Приведем эту структуру.
Базовое программное обеспечение (ПО).
Системное ПО программы обеспечения взаимодействия пользователя и компьютера).
Операционные системы (ОС) - программы ОС (отладчики, загрузчики и т.д.).
Программы обеспечения связи с устройствами (драйверы), тестирования их.
Инструментальное ПО (программы для массовой разработки других программ).
Трансляторы с языков программирования.
Интерфейсные системы – программы обеспечения дружественного интерфейса.
Проблемно-ориентированные инструментальные системы (САПР, АСУ, АРМ и др.).
Прикладное ПО - программы обеспечения решения прикладных задач пользователя).
Автономные программы (программы, не связываемые с другими из прикладного ПО).
Библиотеки программ (программы, организованные по принципу библиотек книг).
Пакеты прикладных программ, ППП (проблемно-ориентированные прикладные системы).
Интегрированные пакеты прикладных программ - системы, состоящие из связываемых ППП).
Специальное (уникальное) ПО - программы, используемые для решения уникальных проблем).
Наиболее сложный и важный элемент ПО – это ОС.
ОС – совокупность программ, которые обеспечивают нормальную работу всех основных устройств компьютера, всех программ и данных, используемых на компьютере при решении задач.
ОС состоит из двух основных частей – управляющие программы и обрабатывающие программы и включает в себя следующие основные программы:
диспетчер – управляющая программа для координации работы различных устройств ЭВМ, планирования использования и распределения машинного времени, аппаратуры между программами, пересылка программ из ВЗУ в ОЗУ и наоборот, распределение данных в памяти, ввод программ в выделенные участки ОЗУ, управление выполнением задачи, принятие решений в аварийных ситуациях, обнаружение и классификация ошибок и др.;
супервизор – управляющая программа для контроля координации используемых ресурсов и последовательности действий процессора;
отладчик – обрабатывающая программа для отладки программы;
редактор связей – программа для формирования непосредственно выполняемой в памяти программы на машинном языке.
Основными функциями ОС являются:
выполнение очередного по приоритету задания и отслеживание очередности;
управление распределением данных в памяти и извлечением их из памяти;
управление устройствами, их актуализация по мере необходимости (по требованиям программ);
восстановление работоспособности при сбоях;
управление работой арифметико-логического командного устройства процессора.
Данные, привлекаемые при решении задач, ОС с помощью специальных программ отображает на реальные физические структуры, носители данных. [u4]Для этих целей используется так называемая файловая система обмена данными между программами пользователя и ОС.
Файл – именованный структурированный набор однотипных последовательностей данных, обычно хранимый на внешнем
XVIII ).
Для изображения десятичных дробей используется подобная формула разложения по степеням основания.
Для перевода из 2-ной в 8-ную и наоборот, из 2-ной в 16-ную и наоборот, из 8-ной в 16-ную и обратно, используется таблица следующего вида:
двоичное число,
, располагающееся на числовой оси равномерно и плотно, представляется в n-разрядной арифметике множеством с неравномерной плотностью (сгущение у нуля и сжатость со стороны меньших чисел);
, то для представления дробных чисел этот диапазон еще снижается, поскольку часть разрядов необходимо отвести под изображение мантиссы. Таким образом, имеются так называемые "зоны нечувствительности" форм представления чисел в n-разрядных арифметиках.
, где m – мантисса числа, k – целый порядок числа, 
.
(
). Тогда можно проверить, что результаты выполнения операций будут равны:
