Кодирование информации

1. Система счисления – это:

1) подстановка чисел вместо букв;

2) способ перестановки чисел;

3) принятый способ записи чисел и сопоставление этим записям реальных значений чисел;

4) правила исчисления чисел.

2. Непозиционная система счисления – это:

1) двоичная;

2) восьмеричная;

3) шестнадцатеричная;

4) буквы латинского алфавита.

3. Основанием позиционной системы счисления называется:

1) основание логарифма из формулы перевода чисел в системе;

2) количество правил вычисления в системе;

3) целая часть чисел;

4) число отличных друг от друга знаков, которые используются для записи чисел.

4. Какая запись числа 729 в десятичной системе счисления будет верной:

1) 7*10^Ù 3 + 2*10^Ù2 + 9*10^Ù1;

2) 7*10^Ù 2 + 2*10^Ù1 + 9*10^Ù0;

3) 7*10^Ù 4 + 2*10^Ù2 + 9*10^Ù1;

4)7*10^Ù 2 + 2*10^Ù1 + 9*10^Ù1?

5. Сложите два числа в двоичной системе счисления: 1101+01 равно:

1) 1100;

2) 1110;

3) 1101;

4) 1011.

6. Умножьте два числа в двоичной системе счисления: 1101*01 равно:

1) 10101;

2) 011011;

3) 10100;

4) 00011.

7. Сложите два числа в двоичной системе счисления: 10101+1011:

1) 101010;

2) 010101;

3) 100000;

4) 111111.

8. Умножьте два числа в двоичной системе счисления: 01011 *101 равно:

1) 1011101;

2) 0101010;

3) 0101111;

4) 0110111.

9. При переводе числа 15 из десятичной системы счисления в двоичную получится число:

1) 1011;

2) 1101;

3) 1101;

4) 1111.

10. При переводе числа 27 из десятичной системы счисления в двоичную получится число:

1) 10011;

2) 11101;

3) 11011;

4) 11110.

11. При переводе числа 35 из десятичной системы счисления в двоичную получится число:

1) 110001;

2) 100011;

3) 111001;

4) 111111.

12. При переводе дробного числа 0,15 из десятичной системы счисления в двоичную получится число:

1) 0,00100110011…;

2) 0,001001001…;

3) 0,010101…;

4) 0,0000100… .

13. При переводе дробного числа 0,69 из десятичной системы счисления в двоичную получится число:

1) 0,11011…;

2) 0,010011;

3) 0,101100…;

4) 0,10111… .

14. При переводе числа 83,55 из десятичной системы счисления в восьмеричную получится число:

1) 123,4314…;

2) 321,4314…;

3) 123,4134;

4) 312,1432… .

15. При переводе дробного числа 14,25 из десятичной системы счисления в двоичную получится число:

1) 1110,01;

2) 1111,10;

3) 001,01;

4) 111,01.

16. При переводе дробного числа 43,32 из десятичной системы счисления в двоичную получится число:

1) 111011,1010…;

2) 101011,010100…;

3) 101011,111…;

4) 010100,0001… .

17. При переводе числа 63,42 из десятичной системы счисления в восьмеричную получится число:

1) 70,327;

2) 07,723;

3) 77,327;

4) 70,723.

Раздел 3. Алгоритмизация и программирование

Лекция 6. Алгоритмы

План

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

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

3. Описание алгоритмов в виде блок-схем.

4. Средства ввода-вывода информации.

5. Выбор действий в алгоритмах,

6. Повторение действий в алгоритмах.

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

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

Составление алгоритмов подразумевает существование определённых исполнителей, которые будут выполнять действия, которые предписываемые алгоритмами. В роли исполнителей алгоритмов могут выступать роботы, механические устройства, ЭВМ или люди.

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

Для описания алгоритмов мы будем использовать определённую форму записи. Запись алгоритма должна оформляться по следующим правилам.

На первой строке записывается слово алгоритм или его трёхбуквенное сокращение алг. Далее, за этим словом записывается название алгоритма. На второй строке записывается слово начало или его сокращение нач. Далее в столбик с небольшим отступом в 2-3 пробела записываются действия, составляющие алгоритм. Последней строкой описания алгоритма должно быть слово конец или сокращённо кон в той же позиции, что и слово начало.

Рассмотрим общую форму записи алгоритма. Справа записан ещё один пример алгоритма – алгоритм приветствия, исполнителем которого может быть ЭВМ:

Алг «название» алг « приветствие»

Начнач

<действие 1> вывод Добрый день

<действие 2> запрос Ваше имя, имя

<действие 3> вывод Рад встрече, имя

Конкон

В угловых скобках <…> при описании формы записи здесь и в последующем указывается содержание информации, которая должна записываться в данном месте.

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

Алг «написание сочинения»

Нач

Выбрать тему сочинения

Продумать и написать план

Написать черновик сочинения

Тщательно проверить черновик

Переписать сочинение начисто

Кон

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

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

Система уравнений: 3х +у =0, х +2у =1.

Исходные данные: a = 3, b = 1, e = 0, c = 1, d = 2, f = 1.

 

АЛГ «Решение системы уравнений» НАЧ D := a · d – b · c Dx := e · d - b · f Dy := a · f – c · e x := Dx / D y := Dy / D КОН

Результаты:   D = ad – bc = 5 Dx = ed – bf = - 1 Dy = af – ce = 3 x = Dx / D = - 0.2 y = Dy / D = 0.6

В записи вычислительных алгоритмов мы видим новое обозначение – знак :=. Этот знак читается «присваивается». Например, запись первой операции D:= a*b – b*c в этом алгоритме читается: переменной D присваивается значение выражения a*d – b*c. Смыслэтой операции состоит в следующем. Исполнитель – ЭВМ или человек – должен вычислить значение переменных a, b, c и d и присвоить это значение переменной D. Процесс выполнения этой операции можно описать цепочкой соотношений: D = a * d – b * c = 3 * 2 - 1 * 1

А конечный результат – равенством: D=5. Полученный результат указан справа от описания алгоритма. Здесь же приведено соотношение D = a*d – b*c, которое поясняет, какой результат будет получен после выполнения присваивания D: = a*d – b*c при произвольных значениях величин a, b, c, d. Соотношение справа – равенство, а в алгоритме записано присваивание. Введение новых обозначений для записи вычислительных операций связано с особенностью их выполнения в ЭВМ. Эта особенность состоит в том, что результаты всех вычислений, все исходные данные записываются и хранятся в памяти машины. Так, в рассматриваемом алгоритме решения системы уравнений в памяти должны находиться величины a, b, c, d, e, f, D, Dx, Dy, x и y. При этом каждая из них должна размещаться в отдельной ячейке памяти.

Выполнение ЭВМ присваивания D: = a*d – b*c состоит в следующем. ЭВМ извлекает из памяти значения переменных a, b, c, d, вычисляет по ним значение формулы a*d – b*c и записывает полученное по ним значение формулы.

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

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

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

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

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

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

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

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