Разработки лекционных занятий (стр. 3 )

3,1415926 = 0, • 101

= 0,3-106

= 0, • 1010

Первая часть числа называется мантиссой, а вторая — характеристикой. Большую часть из 80 бит отводят для хранения мантиссы (вместе со знаком) и некоторое фиксированное количество разрядов отводят для хранения характеристики (тоже со знаком)

Информация в компьютере представлена в дво­ичном коде, алфавит которого состоит из двух цифр (0 и 1).

Важно, что каждая цифра машинного двоичного кода не­сет информацию в 1 бит. Таким образом, две цифры несут информацию в 2 бита, три цифры — в 3 бита и так далее. Количество информации в битах равно количеству цифр двоичного машинного кода.

Каждая цифра машинного двоичного кода несет количество информации, равное одному биту.

1. Почему человек использует десятичную систему счисления, а компьютер — двоичную?

10. Системы счисления

Для записи информации о количестве объектов использу­ются числа. Числа записываются с использованием особых знаковых систем, которые называются системами счисле­ния. Алфавит систем счисления состоит из символов, кото­рые называются цифрами. Например, в десятичной системе счисления числа записываются с помощью десяти всем хо­рошо известных цифр: 0, 1, 2, 3, 4, 5, б, 7, 8, 9.

Система счисления — это знаковая система, в ко­торой числа записываются по определенным пра­вилам с помощью символов некоторого алфавита, называемых цифрами

Все системы счисления делятся на две большие группы:

1.  позиционные (значение цифры зависит от ее положения в числе)

2.  непозиционные системы счисления (значение цифры не зависит от ее положения в числе)

Римская непозиционная система счисления. Самой рас­пространенной из непозиционных систем счисления являет­ся римская. В качестве цифр в ней используются: I (1), V (5), X (10), L (50), С (100), D (500), М (1000).

Значение цифры не зависит от ее положения в числе. На­пример, в числе XXX (30) цифра X встречается трижды и в каждом случае обозначает одну и ту же величину - число 10, три числа по 10 в сумме дают 30.

Величина числа в римской системе счисления определя­ется как сумма или разность цифр в числе. Если меньшая цифра стоит слева от большей, то она вычитается, если справа - прибавляется. Например, запись десятичного чис­ла 1998 в римской системе счисления будет выглядеть сле­дующим образом:

MCMXCVIII = 1000 + (1+ (+ 5 + 1 + 1 + 1.

Позиционные системы счисления.

Первая позиционная система счисления была придумана еще в Древнем Вавило­не, причем вавилонская нумерация была шестидесятеричной, то есть в ней использовалось шестьдесят цифр! Инте­ресно, что до сих пор при измерении времени мы используем основание, равное 60 (в 1 минуте содержится 60 секунд, а в 1 часе — 60 минут).

В XIX веке довольно широкое распространение получи­ла двенадцатеричная система счисления. До сих пор мы ча­сто употребляем дюжину (число 12): в сутках две дюжины часов, круг содержит тридцать дюжин градусов и так да­лее.

Наиболее распространенными в настоящее время позици­онными системами счисления являются десятичная, двоич­ная, восьмеричная и шестнадцатеричная. Каждая позицион­ная система имеет определенный алфавит цифр и основание.

В позиционных системах счисления основание системы равно количеству цифр (знаков в ее ал­фавите) и определяет, во сколько раз различают­ся значения одинаковых цифр, стоящих в сосед­них позициях числа.

Десятичная система счисления имеет алфавит цифр, кото­рый состоит из десяти всем известных, так называемых араб­ских, цифр, и основание, равное 10, двоичная — две цифры и основание 2, восьмеричная — восемь цифр и основание 8, шестнадцатеричная — шестнадцать цифр (в качестве цифр используются и буквы латинского алфавита) и основание 16 (табл. 2.2).

Таблица 2.2. Позиционные системы счисления

Система счисления	Основание	Алфавит цифр
Десятичная	10	0, 1,2,3,4,5,6,7,8,9
Двоичная	2	0, 1
Восьмеричная	8	0, 1,2,3,4,5,6,7
Шестнадцатеричная	16	0, 1 , 2, 3, 4, 5, 6, 7, 8, 9, А (10), В (11 ), C(12),D(13),E(14),F(15)

Десятичная система счисления. Рассмотрим в качестве примера десятичное число 555. Цифра 5 встречается триж­ды, причем самая правая цифра 5 обозначает пять единиц, вторая справа — пять десятков и, наконец, третья справа — пять сотен.

Позиция цифры в числе называется разрядом. Разряд числа возрастает справа налево, от младших разрядов к старшим. В десятичной системе цифра, находящаяся в крайней справа позиции (разряде), обозначает количество единиц, цифра, смещенная на одну позицию влево, — коли­чество десятков, еще левее — сотен, затем тысяч и так да­лее. Соответственно имеем разряд единиц, разряд десятков и так далее.

Число 555 записано в привычной для нас свернутой фор­ме. Мы настолько привыкли к такой форме записи, что уже не замечаем, как в уме умножаем цифры числа на различ­ные степени числа 10.

В развернутой форме записи числа такое умножение за­писывается в явной форме. Так, в развернутой форме запись числа 555 в десятичной системе будет выглядеть следую­щим образом:

55510 = 5-102 + 5-101 + 5-100.

Как видно из примера, число в позиционной системе счисления записывается в виде суммы числового ряда степе­ней основания (в данном случае 10), в качестве коэффициен­тов которых выступают цифры данного числа.

Для записи десятичных дробей используются отрицатель­ные значения степеней основания. Например, число 555,55 в развернутой форме записывается следующим образом: 555,5510 = 5-102 + 5-101 + 5-10°+ 5-10-1 + 5-10-2.

ЛЕКЦИЯ №3. «АЛГОРИТМ. СВОЙСТВА АЛГОРИТМА. ОСНОВНЫЕ ТИПЫ АЛГОРИТМИЧЕСКИХ СТРУКТУР»

План.

Понятие алгоритма Способы задания (описания) алгоритмов Свойства алгоритма Основные типы алгоритмических структур

1. Понятие алгоритма

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

Итак, алгоритм — это метод (способ) решения зада­чи, записанный по определенным правилам, обеспечи­вающим однозначность его понимания и механическо­го исполнения при всех значениях исходных данных (из некоторого множества значений).

Для сравнения в толковом словаре по информатике (1991 г.) дано такое определение: алгоритм — точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомо­му результату.

1. Способы задания (описания) алгоритмов

Известны три наиболее распространенных способа описания алгоритмов.

Первый способ —

Описание алгоритма словами и формулами

В IX в. великий арабский математик аль-Хорезми сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметичес­ких действий над многозначными числами. Само сло­во «алгоритм» происходит от Algorithmi — латинской формы написания его имени.

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

Любой человек ежедневно встречается с множеством задач: от самых простых и хорошо известных до очень сложных. Для многих задач существуют определенные правила (инструкции, предписания), объясняющие ис­полнителю, как решать данную задачу. Эти правила че­ловек может изучить заранее или сформулировать сам в процессе решения задачи. Чем точнее будут описаны правила решения задач, тем быстрее человек овладеет ими и будет эффективнее их применять.

Например:

Давайте вспомним простейшие правила (алгоритм) перехода пешеходом перекрестка, регулируемого свето­фором.

1. Если горит красный свет, идти нельзя.

2. Если горит желтый свет, идти нельзя, но нужно приго­товиться к переходу улицы.

3. Если горит зеленый свет, можно переходить улицу.

Из примера с алгоритмом для пешехода видно, что запись алгоритма распадается на отдельные указания исполнителю (в нашем примере пешеходу) выполнить некоторое законченное действие. Каждое такое действие называется командой. Команды алгоритма выполняются последовательно одна за другой в строгом порядке.

Важ­но, что на каждом шаге алгоритма исполнителю точно известно, какая команда должна выполняться следую­щей. Эту мысль иллюстрирует следующий пример.

Пример 1.

Найти площадь круга, если известен его радиус.

Решение:

1. Ввести значение радиуса R, перейти в п. 2.

2. Вычислить S= pr2, перейти в п. 3.

3. Вывести (отпечатать) значение S, перейти в п. 4.

4. Вычисления прекратить.

Пояснения:

Это предписание является алгоритмом. Для челове­ка, выполняющего действия алгоритма, такая запись до­статочна и не нуждается в пояснении, поскольку фор­ма записи его очень естественна.

При составлении алгоритма нужно ориентироваться на исполнителя, на операции, известные ему. Так, в на­шем примере предусматривается, что исполнителю зна­комо число «пи», знакома операция возведения в сте­пень. Если это не так, то п.2 алгоритма следует разбить на три более мелких этапа.

2а. Ввести значение величины п, перейти в п. 2б.

2б. Умножить значение радиуса r само на себя дважды,

перейти в п. 2в.

2в. Перемножить я и предшествующий результат, перейти в п. 3.

Принцип расчленения сложного процесса решения задачи на элементарные действия имеет важное значе­ние для построения алгоритмов. Поэтому, если нужно составить программу для ЭВМ, то в алгоритме должны предусматриваться те операции, которые ЭВМ способ­на выполнить.

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

Второй способ —

Описание алгоритма на алгоритмическом языке

Алгоритмический язык — это средство для записи ал­горитмов в аналитическом виде, промежуточном между записью алгоритма на естественном (человеческом) язы­ке и записью на языке ЭВМ (языке программирования).

Например:

Задача на расчет площади круга (при исходных дан­ных г = 8 м) на алгоритмическом языке будет выглядеть:

алг ПЛОЩАДЬ КРУГА (цел R, вещ Р, S)

арг R, Р

рез S

нач

S = Р*R^2

кон

Надо признаться, что алгоритмический язык (или еще его называют школьный алгоритмический язык) — это отечественное изобретение. Во всем остальном мире отдают предпочтение алгоритмическим языкам про­граммирования.

Алгоритмический язык программиро­вания (например, Бейсик) — это средство для записи алгоритма решения задачи в виде, понятном как для ЭВМ, так и для человека. Алгоритмы посредством этих языков записываются в программы.

Например:

Алгоритм-программа на языке ВА51С

10R1 = 8

20 Р = 3.14

30 R2 = К1 * К1

40S = Р*R2

50 РRINT S

60 END

Третий способ —

Графическое описание алгоритма

Поочередное выполнение команд алгоритма за ко­нечное число шагов приводит к решению задачи и дос­тижению цели.

Каждый алгоритм строится в расчете на некоторого исполнителя. Для того чтобы исполнитель мог решать задачу по заданному алгоритму, необходимо, чтобы он был в состоянии выполнить каждое действие, предпи­сываемое командами алгоритма, а для этого нужно сде­лать алгоритм однозначно понятным.

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

При графическом описании алгоритма каждая гео­метрическая фигура называется блоком. Внутри блока записывается действие (операция), которую этот блок отождествляет. Блокам могут присваиваться индивиду­альные номера. Строгого правила на тот предмет, как размещать блоки внутри схемы, не существует. Однако лучше их размещать сверху вниз, в порядке исполнения. Порядок выполнения этапов решения задачи от блока к блоку указывается стрелками, соединяющими блоки. Стрелки не могут исходить и возвращаться в один и тот же блок, минуя другие блоки. В каждый блок может вхо­дить сколько угодно стрелок. Но выходить может толь­ко одна стрелка, кроме блока выбора. Из блока выбора всегда выходит две стрелки в зависимости от решения, принятого по некоторому условию, записанному внут­ри этого блока. Решений может быть только два: «Да» или «Нет». Поэтому стрелки, выходящие из блока вы­бора, обязательно подписываются «Да» или «Нет». Ре­шение «Да» принимается, если условию в блоке выбора соответствует сравниваемая величина. «Нет» — если не соответствует. Каждый алгоритм начинается и заканчивается специальными блоками — «Пуск» и «Остановка». Если нужно перенести часть схемы на другой лист или связать между собой разные схемы алгоритмов, исполь­зуют соединитель. Для начертания пояснений к опреде­ленным местам схемы алгоритма применяют комментарий.

Операция	Символ	Название и функциональное назначение
Присваивание		Процесс – выполнение операции или группы операций
Условный переход		Выбор (решение), логический блок – определяет выбор направления выполнения алгоритма в зависимости от некоторого условия, записанного внутри блока. Направления обозначаются символами «да» или «Нет» над каждой выходящей линией.
Цикл		Модификация (подготовка) – определяет циклический вычислительный процесс. Внутри записывается заголовок цикла.
Старт, завершение		Пуск – начало, останов - конец
Ввод, вывод		Блок ввод
		Блок вывод
		Ручной ввод – вывод данных с клавиатуры
		Печать (Документ) – вывод, печать информации на бумажный носитель
		Линии потока – изображение связи между символами. Линии без стрелки указывают направление потока слева направо или сверху вниз.
		Соединитель (узел) – указание связи между прорывными линиями потока
		Комментарий – пояснения к операции данного блока
		Дисплей – вывод информации на экран дисплея (монитора)

Посмотрим теперь на схему (иначе еще назы­вают блок-схема) алгоритма нашей задачи. Сравним раз­ные записи алгоритмов. Из всех примеров видно, что запись ал­горитма на алгоязыке (алго­ритмическом языке) в чем-то близка к его словесно-формульному описанию. Разница между ними состоит в том, что в алго­языке используется ограничен­ный набор терминов, более строгие правила записи опера­ций и т. д. с целью обеспечения однозначности понимания алгоритма. Особенно это было актуально в нашей стране тогда, когда разные версии алгоритмических языков программирования (например, Бейсика) были плохо совместимы либо не совместимы вовсе. Тогда ЭВМ раз­ных марок зачастую не понимали программы, написан­ные для других ЭВМ.

Наглядность описания алгоритмов алгоязыком невы­сока, особенно алгоритмов сложной структуры. Одна­ко алгоязык может быть полезен как средство компак­тной записи алгоритмов.

Сам собою напрашивается вывод.

Вывод: Наиболее наглядный способ описания алгоритмов — схемы алгоритмов (блок-схемы).

3. Свойства алгоритмов

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

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

Первое свойство — определенность (однозначность, понятность, точность) алгоритма

Под этим свойством понимается единственность тол­кования правил выполнения действий и порядка их вы­полнения. Это свойство означает, что каждая команда алгоритма (предписание, выданное на каждом шаге дей­ствия) должна быть понятна исполнителю, не оставляя места для ее неоднозначного толкования и неопределен­ного исполнения. Описание алгоритма должно быть таким, чтобы его мог выполнить любой подготовленный исполнитель, а каждый грамотный пользователь был способен создать компьютерную программу по этому алгоритму.

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

Второе свойство — дискретность и конечность алгоритма

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

Третье свойство — результативность алгоритма

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

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

Четвертое свойство — массовость алгоритма

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

Совокупность этих свойств алгоритма рождает новое его свойство — правильность. Правильность — производное, а не первоосновное свойство алгоритма. Поэтому его наличие не обязатель­но. Смысловое содержание этого свойства таково, что оно отделимо от понятия алгоритма, в отличие от четы­рех перечисленных.

Когда мы говорим, что алгоритм правильный, то имеем в виду, что его выполнение дает правильные результаты решения поставленных задач. Соответственно, мы говорим, что алгоритм содержит ошибки, когда мож­но указать такие допустимые исходные данные или ус­ловия, при которых выполнение алгоритма либо не за­вершается вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся не­правильными.

4. Основные типы алгоритмических структур

Несмотря на очевидное разнообразие алгоритмов, с которыми приходится сталкиваться человеку в процессе решения множества различных задач, все же можно вы­делить три основных вида алгоритмов по их структуре:

— линейные алгоритмы;

— разветвляющиеся алгоритмы;

— циклические алгоритмы.

Линейные алгоритмы

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

Пример.

Найти силу тяготения F двух тел с массами m1 и т2 находящихся на расстоянии между собой.

Решение:

По закону всемирного тяготения: , где
G = 6, Н-м2/кг2.

Разветвляющиеся алгоритмы

Разветвляющимися называются такие алгоритмы, в которых выбирается один из нескольких возможных пу­тей (вариантов) вычислительного процесса. Каждый по­добный путь называется ветвью алгоритма. Признаком разветвляющегося алгоритма является наличие хотя бы одной операции проверки условия. В схеме алгоритма операцию проверки условия выполняет логический блок. Он изображается ромбом, внутри которого указы­вается проверяемое условие (отношение), и имеет два выхода: «Да» и «Нет». Если условие (отношение) истин­но (выполняется), то выходим из блока по выходу «Да», если ложно (не выполняется) — по выходу «Нет». Усло­вие (отношение), содержащееся в логическом блоке, может быть заменено на противоположное: А ≠ В => В = А; х£ уÞ у> х. При этом «Да» и «Нет» меняют­ся местами. Логический блок может содержать лишь одно условие.

Пример.

Определить кислотность раствора. Для этого капнуть на индикатор — лакмусовую бумажку — каплю раство­ра. Если лакмусовая бумажка под каплей раствора не из­менит цвета, значит, это нейтральный раствор. Если ин­дикатор покраснеет, значит, раствор кислый. Если бумажка посинеет, раствор щелочной.

Циклические алгоритмы

Циклическими называются такие алгоритмы, в кото­рых получение результата обеспечивается многократ-1ным выполнением одних и тех же операций. Любой Циклический алгоритм определяется тремя наборами формул и одним условием. Первый по порядку должен идти блок присваивания переменным начальных значе­ний. Вторым — рабочий блок (вычисление результатов). Третий — проверка окончания цикла (отношение, логи­ческое выражение). Далее один из путей должен вести к блоку изменения переменных, а от него, замыкая цикл, к рабочему блоку.

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

1.  Дайте определение алгоритма

2.  Назовите свойства алгоритма

3.  Назовите способы задания алгоритма

4.  Назовите основные структуры алгоритма

ЛЕКЦИЯ №4. «ЯЗЫКИ ПРОГРАММИРОВАНИЯ. АЛФАВИТ. ВЕЛИЧИНЫ. ТИПЫ ДАННЫХ ЯЗЫКА ПРОГРАММИРОВАНИЯ ПАСКАЛЬ»

План.

Понятие о программировании Языки программирования Трансляторы Общие сведения о языке программирования PASCAL; Алфавит языка программирования Паскаль; Величины; Типы данных.

1. Понятие о программировании

Когда компьютер включается, в нем оживает множество программ. Сначала начинают работать программы, постоянно хранящиеся в памяти (в постоянном запоминающем устройстве - ПЗУ), которые проверяют неисправность и работоспособность жесткого диска, монитора, клавиатуры и других периферийных устройств. Если все оборудование исправно, то начинается загрузка с жесткого диска в оперативную память компьютера операционной системы - тоже программы, только большой и сложной. Во время этой загрузки могу запускаться различные драйверы периферийных устройств (программы, ответственные за организацию стандартного доступа к этим устройствам из операционной системы) и всевозможные системные утилиты, автоматически выполняющие служебные функции и помогающие пользователю в работе (это могут быть, например, нестандартные, но удобные в работе русификаторы). После того как операционная система загрузилась, можно запускать всевозможные прикладные программы - текстовые редакторы, электронные таблицы, базы данных, игры и т. д.