Презентации к каждой лекции 8 класс

СИСТЕМЫ СЧИСЛЕНИЯ

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

Ключевые слова

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

Общие сведения

Система счисления - это знаковая система, в которой приняты определённые правила записи чисел.

Цифры - знаки, при помощи которых записываются числа.

Алфавит системы счисления - совокупность цифр.

Вавилонская система счисления

Египетская система счисления

Древнеславянская система счисления

Узловые и алгоритмические числа

Узловые числа обозначаются цифрами.

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

 100 +

 10 +

=

Унарная система счисления

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

Узелки, дощечки

Узелковое письмо «кипу»

Примеры узлов «кипу»

Зарубки

Камушки

Непозиционная система счисления

Система счисления называется непозиционной , если количественный эквивалент (количественное значение) цифры в числе не зависит от её положения в записи числа.

Римская система счисления

1

5

I

V

100

10

C

500

X

50

D

L

1000

M

Здесь алгоритмические числа получаются путём сложения и вычитания узловых чисел с учётом следующего правила:

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

1935

M

V

I

I

I

V

X

X

28

X

X

X

M

C

X

40

L

=

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

Система счисления называется позиционной , если количественный эквивалент цифры в числе зависит от её положения в записи числа.

Основание позиционной системы счисления равно количеству цифр, составляющих её алфавит.

Алфавит десятичной системы составляют цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Десятичная система счисления

Цифры 1234567890 сложились в Индии около 400 г. н. э.

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

Примерно в 1200 г. н. э. эту нумерацию начали применять в Европе.

Основная формула

В позиционной системе счисления с основанием q любое число может быть представлено в виде:

A q =±(a n–1  q n–1 + a n–2  q n–2 +…+ a 0  q 0 + a –1  q –1 +…+ a –m  q –m )

Здесь:

А — число;

q — основание системы счисления;

a i — цифры, принадлежащие алфавиту данной системы счисления;

n — количество целых разрядов числа;

m — количество дробных разрядов числа;

q i — «вес» i -го разряда.

Такая запись числа называется развёрнутой формой записи.

Развёрнутая форма

A q =±(a n–1  q n–1 + a n–2  q n–2 +…+ a 0  q 0 + a –1  q –1 +…+ a –m  q –m )

Примеры записи чисел в развёрнутой форме:

2012=2  10 3 +0  10 2 +1  10 1 +2  10 0

0,125=1  10 -1 +2  10 -2 +5  10 –3

14351,1=1  10 4 +4  10 3 +3  10 2 +5  10 1 +1  10 0 +1  10 –1

Двоичная система счисления

Двоичной системой счисления называется позиционная система счисления с основанием 2 .

Двоичный алфавит : 0 и 1.

Для целых двоичных чисел можно записать:

a n–1 a n–2 …a 1 a 0 = a n–1  2 n–1 + a n–2  2 n–2 +…+ a 0  2 0

Например:

10011 2 =1  2 4 +0  2 3 +0  2 2 +1  2 1 +1  2 0 = 2 4 +2 1 + 2 0 =19 10

Правило перевода двоичных чисел в десятичную систему счисления:

Вычислить сумму степеней двойки, соответствующих единицам в свёрнутой форме записи двоичного числа

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

a n–1  2 n–1 +a n–2  2 n–2 +… a 1  2 1 +a 0

= a n–1  2 n–2 +…+ a 1 (остаток a 0 )

2

a n–1  2 n–1 +a n–2  2 n–2 +… a 1

= a n–1  2 n–3 +…+ a 2 (остаток a 1 )

2

a n–1  2 n–1 +a n–2  2 n–2 +… a 2

= a n–1  2 n–4 +…+ a 3 (остаток a 2 )

2

. . .

На n -м шаге получим набор цифр: a 0 a 1 a 2 …a n–1

Компактное оформление

363

181

1

90

1

45

0

1

22

11

0

5

1

2

1

0

1

1

363 10 = 101101011 2

314

0

157

78

1

39

0

1

19

1

9

1

4

0

2

1

0

1

314 10 = 100111010 2

Восьмеричная система счисления

Восьмеричной системой счисления называется позиционная система счисления с основанием 8.

Алфавит: 0, 1, 2, 3, 4, 5, 6, 7.

a n–1 a n–2 …a 1 a 0 = a n–1  8 n–1 +a n–2  8 n–2 +…+a 0  8 0

Пример : 1063 8 =1  8 3 +0  8 2 +6  8 1 +3  8 0 =563 10 .

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

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

Шестнадцатеричная система счисления

Основание : q = 16.

Алфавит : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

3АF 16 =3  16 2 +10  16 1 +15  16 0 =768+160+15=943 10 .

Переведём десятичное число 154 в шестнадцатеричную систему счисления:

154

16

9

-144

16

10

9

0

(А)

154 10 = 9А 16

Правило перевода целых десятичных чисел в систему счисления с основанием q

1) последовательно выполнять деление данного числа и получаемых целых частных на основание новой системы счисления до тех пор, пока не получим частное, равное нулю;

2) полученные остатки, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления;

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

Цифровые весы

Таблица соответствия 10-х, 2-х, 8-х и 16-х чисел от 1 до 16

Десятичная система

Двоичная система

1

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

1

2

Шестнадцатеричная система

1

10

3

4

1

2

11

5

100

3

2

3

6

4

101

5

4

7

110

5

6

111

8

9

6

7

1000

10

1001

7

10

8

11

1010

11

9

12

1011

12

A

13

13

1100

1101

14

14

B

C

15

15

1110

1111

16

16

D

E

17

10000

17

F

20

10001

18

10

21

10010

11

22

12

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

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



+

0

0

0

0

1

0

1

1

0

1

1

0

1

0

10

1

Арифметика одноразрядных двоичных чисел

Арифметика многоразрядных двоичных чисел

Умножение и деление двоичных чисел

«Компьютерные» системы счисления

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

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

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

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

Самое главное

Система счисления — это знаковая система, в которой приняты определённые правила записи чисел.

Система счисления называется позиционной , если количественный эквивалент цифры в числе зависит от её положения в записи числа.

В позиционной системе счисления с основанием q любое число может быть представлено в виде:

A q =±(a n–1  q n–1 + a n–2  q n–2 +…+ a 0  q 0 + a –1  q –1 +…+ a –m  q –m )

Здесь:

А — число;

q — основание системы счисления;

a i — цифры, принадлежащие алфавиту данной системы счисления;

n — количество целых разрядов числа;

m — количество дробных разрядов числа;

q i — «вес» i -го разряда.

Вопросы и задания

Переведите целые числа из десятичной системы счисления в восьмеричную:

а) 513

б) 600

в) 2010

Выполните операцию умножения над двоичными числами:

а) 1010 · 11

б) 111 · 101

в) 1010 · 111

Запишите десятичные эквиваленты следующих чисел:

а) 172 8

б) 2ЕА 16

в) 101010 2

г) 10,1 2

д) 243 6

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

а) 89

б) 600

в) 2010

Переведите целые числа из десятичной системы счисления в шестнадцатеричную:

а) 513

б) 600

в) 2010

Какое минимальное основание имеет система счисления, если в ней записаны числа 123, 222, 111, 241? Определите десятичный эквивалент данных чисел в найденной системе счисления.

Запишите в развёрнутом виде числа:

а) 143,511 10

б) 143511 8

в) 143511 16

г) 1435,11 8

Укажите, какое из чисел 110011 2 , 111 4 ,35 8 и1В 16 является:

а) наибольшим

б) наименьшим

Как от свёрнутой формы записи десятичного числа перейти к его развёрнутой форме?

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

а) 1100 ? 11 ? 100 = 100000;

б) 1100 ? 10 ? 10 = 100;

в) 1100 ? 11 ? 100 = 0.

Найдите основание х системы счисления, если:

а) 14 x =9 10

б) 2002 x =130 10

Объясните, почему позиционные системы счисления с основаниями 5, 10, 12 и 20 называют системами счисления анатомического происхождения.

Цифры каких систем счисления приведены на рисунке?

Чем различаются унарные, позиционные и непозиционные системы счисления?

Выполните операцию сложения над двоичными числами:

а) 101010 + 1101

б) 1010 + 1010

в) 10101 + 111

Вычислите выражения:

а) (1111101 2 +AF 16 ):36 8

б) 125 8 + 101 2 ·2A 16 – 141 8

Ответ дайте в десятичной системе счисления.

Заполните таблицу, в каждой строке которой одно и то же число должно быть записано в системах счисления с основаниями 2, 8, 10 и 16.

Верны ли следующие равенства?

а) 33 4 =21 7

б) 33 8 =21 4

Основание 2

Основание 8

101010

Основание 10

Основание 16

127

321

2А

Задачник «Системы счисления»

Опорный конспект

Система счисления — это знаковая система, в которой приняты определённые правила записи чисел.

Цифры - знаки, при помощи которых записываются числа.

Алфавит - совокупность цифр системы счисления.

Система счисления

Непозиционная

Позиционная

Римская

Десятичная

Двоичная

Шестнадцатеричная

Восьмеричная

В позиционной системе счисления с основанием q любое число может быть представлено в виде:

A q =±(a n–1  q n–1 + a n–2  q n–2 +…+ a 0  q 0 + a –1  q –1 +…+ a –m  q –m ).

Электронные образовательные ресурсы

• http://school-collection.edu.ru/catalog/res/caeea6cc-bd1d-4f47-9046-1434ac57e111/?from=a30a9550-6a62-11da-8cd6-0800200c9a66&interface=catalog&class=51&subject=19&rub_guid[]=a30a9550-6a62-11da-8cd6-0800200c9a66 – Умножение и деление двоичных чисел
• http://school-collection.edu.ru/catalog/res/402b749c-240b-4e16-9e4d-bea3fc4fa8fa/?from=a30a9550-6a62-11da-8cd6-0800200c9a66&interface=catalog&class=51&subject=19&rub_guid[]=a30a9550-6a62-11da-8cd6-0800200c9a66 – История развития систем счисления
• http://school-collection.edu.ru/catalog/res/1a264912-eca9-4b45-8d77-c3655b199113/?from=a30a9550-6a62-11da-8cd6-0800200c9a66&interface=catalog&class=51&subject=19&rub_guid[]=a30a9550-6a62-11da-8cd6-0800200c9a66 – Перевод недесятичных чисел в десятичную систему счисления
• http://school-collection.edu.ru/catalog/res/78ba290c-0f7c-4067-aaf4-d72f40f49f3b/?from=a30a9550-6a62-11da-8cd6-0800200c9a66&interface=catalog&class=51&subject=19&rub_guid[]=a30a9550-6a62-11da-8cd6-0800200c9a66 - Перевод десятичных чисел в другие системы счисления
• http://school-collection.edu.ru/catalog/res/67cbf74b-f85a-4e9d-88c5-58f203fb90ce/?from=a30a9550-6a62-11da-8cd6-0800200c9a66&interface=catalog&class=51&subject=19&rub_guid[]=a30a9550-6a62-11da-8cd6-0800200c9a66 - Сложение и вычитание многоразрядных двоичных чисел
• http://school-collection.edu.ru/catalog/res/8bb7eefa-4ed9-43fe-aebe-4d6ac67bc6ec/?from=a30a9550-6a62-11da-8cd6-0800200c9a66&interface=catalog&class=51&subject=19&rub_guid[]=a30a9550-6a62-11da-8cd6-0800200c9a66 - Сложение и вычитание одноразрядных двоичных чисел
• http://school-collection.edu.ru/catalog/res/fc77f535-0c00-4871-b67c-fa2ecf567d46/?from=a30a9550-6a62-11da-8cd6-0800200c9a66&interface=catalog&class=51&subject=19&rub_guid[]=a30a9550-6a62-11da-8cd6-0800200c9a66 – Задачник
• http://school-collection.edu.ru/catalog/res/a96df437-5ae3-4cab-8c5f-8d4cd78c5775/?from=a30a9550-6a62-11da-8cd6-0800200c9a66&interface=catalog&class=51&subject=19&rub_guid[]=a30a9550-6a62-11da-8cd6-0800200c9a66 - Развернутая форма записи числа
• http://school-collection.edu.ru/catalog/res/19d0fb95-871d-4063-961d-e7dc5725e555/?from=a30a9550-6a62-11da-8cd6-0800200c9a66&interface=catalog&class=51&subject=19&rub_guid[]=a30a9550-6a62-11da-8cd6-0800200c9a66 – Тренировочный тест

ПРЕДСТАВЛЕНИЕ ЧИСЕЛ В КОМПЬЮТЕРЕ

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

Ключевые слова

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

Ячейки памяти

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

Каждый такой элемент служит для хранения одного из битов - разрядов двоичного числа. Именно поэтому каждый элемент ячейки называют битом или разрядом .

( n -1)-й разряд

0 –й разряд

ячейка из n разрядов

Представление целых чисел

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

Под целые отводится 8 разрядов:

0

0

1

1

0

1

0

1

Под целые числа отводится 16 разрядов:

Знак

Число

0

0

0

0

0

0

0

0

0

0

1

1

0

1

0

1

Под целые числа отводится 32 разряда:

0

1

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Знак

Число

Беззнаковое представление

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

Минимальное значение: во всех разрядах ячейки хранятся нули.

Максимальное значение: во всех разрядах ячейки хранятся единицы (2 n –1).

Количество битов

8

Минимальное значение

Максимальное значение

0

16

255 (2 8 – 1)

32

0

64

0

65 535 (2 16 – 1)

4 294 967 295 (2 32 – 1)

0

18 446 744 073 709 551 615 (2 64 – 1)

Пример 1 . Число 53 10 = 110101 2 в восьмиразрядном представлении имеет вид:

0

0

1

1

0

1

0

1

Число 53 в шестнадцатиразрядном представлении имеет вид:

0

0

0

0

0

0

0

0

0

0

1

1

0

1

0

1

Представление чисел в памяти компьютера

Представление со знаком

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

Если число положительное, то в знаковый разряд помещается 0 , если число отрицательное, то 1 .

Диапазон представления чисел - 2 n-1 ≤ x ≤ 2 n-1 -1, где n - разрядность ячейки.

Минимальное значение: -2 n-1 .

Максимальное значение: 2 n-1 –1.

Количество битов

8

Диапазон чисел

16

от - 2 7 до 2 7 – 1 (от -128 до 127)

от - 2 15 до 2 15 – 1 (от -32768 до 32767)

32

64

от - 2 31 до 2 31 – 1 (от -2147483648 до 2147483647)

от - 2 63 до 2 63 – 1 (от - 9223372036854775808 )

Прямой код

Пример 2 . Число 73 10 = 1001001 2 .

Прямой код числа 73 10 в восьмиразрядном представлении имеет вид:

0

1

0

0

1

0

0

1

Прямой код числа -73 10 в восьмиразрядном представлении имеет вид:

1

1

0

0

1

0

0

1

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

Представление вещественных чисел

Любое вещественное число А может быть записано в нормальной (научной, экспоненциальной) форме:

А =± m  q p , где:

m - м антисса числа;

q - основание системы счисления;

p - порядок числа.

Пример. 472 000 000 может быть представлено так:

4,72  10 8

47,2  10 7

472  10 6

4720  10 5

Запятая «плавает» по мантиссе.

Такое представление числа называется представлением в формате с плавающей запятой.

Бывают записи вида: 4.72Е+8.

Формат с плавающей запятой

Число в формате с плавающей запятой может занимать в памяти компьютера 32 или 64 разряда.

При этом выделяются разряды для хранения

знака порядка,

порядка,

знака мантиссы

и мантиссы.

0

Знак и порядок

1

1

1

1

1

1

1

0

Знак и мантисса

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Диапазон представления вещественных чисел определяется количеством разрядов, отведённых для хранения порядка числа, а точность - количеством разрядов, отведённых для хранения мантиссы.

Числа в памяти компьютера

Самое главное

Для компьютерного представления целых чисел используются несколько различных способов, отличающихся друг от друга количеством разрядов (8, 16, 32 или 64) и наличием или отсутствием знакового разряда.

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

При представлении со знаком самый старший разряд отводится под знак числа, остальные разряды - под само число. Если число положительное, то в знаковый разряд помещается 0, если число отрицательное, то 1.

Вещественные числа в компьютере хранятся в формате с плавающей запятой:

А = ±m  q p , где:

m - мантисса числа;

q - основание системы счисления;

p - порядок числа .

Вопросы и задания

Как в памяти компьютера представляются целые положительные и отрицательные числа?

Любое целое число можно рассматривать как вещественное, но с нулевой дробной частью.

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

Представьте число 63 10 в беззнаковом 8-разрядном формате.

Найдите десятичные эквиваленты чисел по их прямым кодам, записанным в 8-разрядном формате со знаком:

а) 01001100;

б) 00010101.

Какие из чисел 443 8 , 101010 2 , 256 10 можно сохранить в 8-разрядном формате?

Запишите следующие числа в естественной форме:

а) 0,3800456 · 10 2 ;

б) 0,245 · 10 –3 ;

в) 1,256900Е+5;

г) 9,569120Е–3.

Запишите число 2010,0102 10 пятью различными способами в нормальной форме.

Запишите следующие числа в нормальной форме с нормализованной мантиссой - правильной дробью, имеющей после запятой цифру, отличную от нуля:

а) 217,93410;

б) 7532110;

в) 0,0010110.

Опорный конспект

Числа в компьютере

Целое число

Вещественное число

Положительное

А = ±m  q p , где:

m - мантисса числа;

q - основание системы

счисления;

p - порядок числа.

Отрицательное

Электронные образовательные ресурсы

http://files.school-collection.edu.ru/dlrstore/d26ca47b-943d-4dec-a853-a32844cdc101/9_117.swf - Числа в памяти компьютера

http://files.school-collection.edu.ru/dlrstore/ecf4ab69-d8ac-40a8-b26a-2780aa70b33d/9_118.swf - Представление чисел в памяти компьютера

http://files.school-collection.edu.ru/dlrstore/19d0fb95-871d-4063-961d-e7dc5725e555/9_121.swf - Тест двоичная система счисления и представление чисел в памяти компьютера

ЭЛЕМЕНТЫ АЛГЕБРЫ ЛОГИКИ

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

Ключевые слова

• алгебра логики
• высказывание
• логическая операция
• конъюнкция
• дизъюнкция
• отрицание
• логическое выражение
• таблица истинности
• законы логики

Л огик а

Аристотель (384-322 до н.э.). Основоположник формальной логики (понятие, суждение, умозаключение).

Джордж Буль (1815-1864). Создал новую область науки - Математическую логику (Булеву алгебру или Алгебру высказываний).

Клод Шеннон (1916-2001). Его исследования позволили применить алгебру логики в вычислительной технике

Алгебра

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

Высказывание

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

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

Земля вращается вокруг Солнца .

Москва - столица.

Но не всякое повествовательное предложение является высказыванием:

Это высказывание ложное.

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

Без стука не входить!

Откройте учебники.

Ты выучил стихотворение?

Высказывание или нет?

Зимой идет дождь.

Снегири живут в Крыму.

Кто к нам пришел?

У треугольника 5 сторон.

Как пройти в библиотеку?

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

Запишите домашнее задание

• Зимой идет дождь. Снегири живут в Крыму. Кто к нам пришел? У треугольника 5 сторон. Как пройти в библиотеку? Переведите число в десятичную систему. Запишите домашнее задание

Алгебра логики

Алгебра логики определяет правила записи, вычисления значений, упрощения и преобразования высказываний.

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

Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей ( А = 1 ), а если ложно - нулём ( В = 0 ).

0 и 1 называются логическими значениями .

Простые и сложные высказывания

Высказывания бывают простые и сложные.

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

Сложные (составные) высказывания строятся из простых с помощью логических операций .

Название логической операции

Конъюнкция

Логическая связка

Дизъюнкция

«и»; «а»; «но»; «хотя»

«или»

Инверсия

«не»; «неверно, что»

Логические операции

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

Другое название: логическое умножение.

Обозначения:  ,  , & , И.

Таблица истинности:

Графическое представление

А

0

В

А & В

0

0

0

1

1

1

0

0

1

0

1

A

B

А&В

Логические операции

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

Другое название: логическое сложение .

Обозначения: V, |, ИЛИ, +.

Графическое представление

Таблица истинности:

А

0

В

0

0

А V В

0

1

1

1

0

1

1

1

1

A

B

АVВ

Логические операции

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

Другое название: логическое отрицание.

Обозначения: НЕ, ¬ , ¯ .

Графическое представление

Таблица истинности:

А

0

Ā

1

1

0

A

Ā

Логические операции имеют следующий приоритет:

инверсия, конъюнкция, дизъюнкция .

Решаем задачу

Пусть А = «На Web-странице встречается слово "крейсер"», В = «На Web-странице встречается слово "линкор"».

В некотором сегменте сети Интернет 5000000 Web-страниц. В нём высказывание А истинно для 4800 страниц, высказывание В - для 4500 страниц, а высказывание А V В - для 7000 страниц.

Для какого количества Web-страниц в этом случае будут истинны следующие выражения и высказывание?

а) НЕ ( А ИЛИ В );

б) А & B ;

в) На Web-странице встречается слово "крейсер" И НЕ встречается слово "линкор".

Представим условие задачи графически:

5 000 000

B

И

A

A

B

A&B

7 000

НЕ ( А ИЛИ В )

А ИЛИ В

4800 – 2300 = 2500 Web-страниц

A = 4800, B = 4500.

4800 + 4500 = 9300

Сегмент Web-страниц

На 2500 Web-страницах встречается слово "крейсер" И НЕ встречается слово "линкор".

5000000 – 7000 = 4 993 000 Web-страниц НЕ ( А ИЛИ В )

9300 – 7000 = 2300 Web-страниц A&B

Построение таблиц истинности для логических выражений

подсчитать n - число переменных в выражении

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

установить последовательность выполнения логических операций

определить число столбцов в таблице

заполнить шапку таблицы, включив в неё переменные и операции

определить число строк в таблице без шапки: m =2 n

выписать наборы входных переменных

провести заполнение таблицы по столбцам, выполняя логические

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

Пример построения таблицы истинности

А V A & B

n = 2, m = 2 2 = 4 .

Приоритет операций: &, V

A

B

A&B

A V A&B

0

0

0

1

0

1

0

1

0

0

0

1

0

1

1

1

Свойства логических операций

Законы алгебры-логики

A & Ā = 0

A & B = B & A

Закон исключения

третьего

Переместительный

A V Ā = 1

A V B = B V A

A & A = A

(A & B) & C = A & ( B & C)

Закон повторения

Сочетательный

(A V B) V C =A V ( B V C)

A V A = A

A&(B V C)= (A&B) V (A&C)

A & 0=0; A &1 = A

Распределительный

Законы операций

с 0 и 1

A V 0 = A; A V 1 = 1

A V (B&C) = (A V B)&(A V C)

Закон двойного

отрицания

Законы общей

инверсии

A & B = Ā V B

Ā = A

A V B = Ā & B

Доказательство закона

Распределительный закон для логического сложения: A v (B & C) = (A v B) & (A v C).

A

B

0

C

0

0

B&C

0

0

0

A v (B & C)

0

1

1

A v B

0

1

1

A v C

1

0

1

(A v B) & (A v C)

0

0

1

1

1

1

0

1

1

0

0

0

0

0

0

0

0

1

0

1

0

0

0

0

1

1

1

1

1

1

1

1

0

1

1

1

1

0

1

0

1

1

1

1

1

1

1

1

1

Равенство выделенных столбцов доказывает распределительный закон.

Умножаем В на С и выводим результат.

Складываем А и ( В & С ) и выводим результат.

Умножаем ( А v B ) на ( A v C )и выводим результат.

Складываем А и C и выводим результат.

Складываем А и В и выводим результат.

Решение логических задач

Задача. Коля, Вася и Серёжа гостили летом у бабушки. Однажды один из мальчиков нечаянно разбил любимую бабушкину вазу.

На вопрос, кто разбил вазу, они дали такие ответы:

Серёжа : 1) Я не разбивал. 2) Вася не разбивал.

Вася : 3) Серёжа не разбивал. 4) Вазу разбил Коля.

Коля: 5) Я не разбивал. 6) Вазу разбил Серёжа.

Бабушка знала, что один из её внуков (правдивый), оба раза сказал правду; второй (шутник) оба раза сказал неправду; третий (хитрец) один раз сказал правду, а другой раз - неправду. Назовите имена правдивого, шутника и хитреца.

Кто из внуков разбил вазу?

Решение. Пусть К =«Коля разбил вазу»,

В =«Вася разбил вазу»,

С =«Серёжа разбил вазу».

Представим в таблице истинности высказывания каждого мальчика. Так как ваза разбита одним внуком, составим не всю таблицу, а только её фрагмент, содержащий наборы входных переменных: 001, 010, 100.

K

B

0

C

0

Утверждение Серёжи

0

1

1

1

0

0

Утверждение Васи

0

0

1

1

Утверждение Коли

0

1

0

K

1

0

1

1

1

0

C

1

1

1

0

0

0

С

В

К

С

Исходя из того, что знает о внуках бабушка, следует искать в таблице строки, содержащие в каком-либо порядке три комбинации значений: 00, 11, 01 (или 10). Это первая строка.

Вазу разбил Серёжа, он - хитрец. Шутником оказался Вася. Имя правдивого внука - Коля.

Логические элементы

Логический элемент – устройство, которое после обработки двоичных сигналов выдаёт значение одной из логических операций.

А

А

&

1

А

В

В

НЕ (инвертор)

И (конъюнктор)

ИЛИ (дизъюнктор)

Анализ электронной схемы

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

Какой сигнал должен быть на выходе при каждом возможном наборе сигналов на входах?

A

0

B

F

0

0

1

0

1

1

0

0

1

1

0

А

&

F

В

В инвертор поступает сигнал от входа В .

В конъюнктор поступают сигналы от входа А и от инвертора. Таким образом, F = A & B .

Самое главное

Высказывание — это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.

Основные логические операции , определённые над высказываниями: инверсия, конъюнкция, дизъюнкция .

Таблицы истинности для основных логических операций:

А

0

Ā

1

A

1

B

0

0

0

0

A & B

A V B

0

1

1

0

0

1

0

1

1

0

1

1

1

Название логической операции

Инверсия

Логическая связка

«не, «неверно, что»

Обозначение

Конъюнкция

¬ , ─

Дизъюнкция

«и», «а», «но», «хотя»

«или»

&

V

При вычислении логических выражений сначала выполняются действия в скобках. Приоритет выполнения логических операций: ¬, &, V .

Вопросы и задания

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

1) Число 376 чётное и трёхзначное.

2) Зимой дети катаются на коньках или на лыжах.

3) Новый год мы встретим на даче или на Красной площади.

4) Неверно, что Солнце движется вокруг Земли.

5) Земля имеет форму шара, который из космоса кажется голубым.

6) На уроке математики старшеклассники отвечали на вопросы учителя, а также писали самостоятельную работу.

Объясните, почему следующие предложения не являются высказываниями.

1) Какого цвета этот дом?

2) Число Х не превосходит единицы.

3) 4 Х +3.

4) Посмотрите в окно.

5) Пейте томатный сок!

6) Эта тема скучна.

7) Рикки Мартин - самый популярный певец.

8) Вы были в театре?

Постройте отрицания следующих высказываний.

1) Сегодня в театре идёт опера «Евгений Онегин».

2) Каждый охотник желает знать, где сидит фазан.

3) Число 1 есть простое число.

4) Натуральные числа, оканчивающиеся цифрой 0, не являются простыми числами.

5) Неверно, что число 3 не является делителем числа 198.

6) Коля решил все задания контрольной работы.

7) Во всякой школе некоторые ученики интересуются спортом.

8) Некоторые млекопитающие не живут на суше.

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

Пусть А = «Ане нравятся уроки математики», а В = «Ане нравятся уроки химии». Выразите следующие формулы на обычном языке:

Приведите по одному примеру истинных и ложных высказываний из биологии, географии, информатики, истории, математики, литературы.

А

1

F

В

Вопросы и задания

Алёша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:

1) Алеша : « Это сосуд греческий и изготовлен в V веке ».

2) Боря : « Это сосуд финикийский и изготовлен в III веке ».

3) Гриша : « Это сосуд не греческий и изготовлен в IV веке ».

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

Разбирается дело Джона, Брауна и Смита. Известно, что один из них нашёл и утаил клад. На следствии каждый из подозреваемых сделал два заявления:

Смит : «Я не делал этого. Браун сделал это».

Джон : «Браун не виновен. Смит сделал это».

Браун : «Я не делал этого. Джон не делал этого».

Суд установил, что один из них дважды солгал, другой дважды сказал правду, третий один раз солгал, один раз сказал правду.

Кто из подозреваемых должен быть оправдан?

Опорный конспект

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

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

Основные логические

операции

Дизъюнкция

Конъюнкция

Инверсия

А

A

0

A

Ā

0

0

1

B

1

B

A & B

0

0

0

0

0

A V B

1

0

1

0

1

1

1

1

0

0

1

0

1

0

1

1

1

1

Приоритет выполнения логических операций: ¬, &, V .

Электронные образовательные ресурсы

• http://school-collection.edu.ru/catalog/res/9e997f40-f285-4369-aa7d-88b892beca45/?interface=catalog&class=51&subject=19 – Элементарные логические операции

АЛГОРИТМЫ И ИСПОЛНИТЕЛИ

ОСНОВЫ АЛГОРИТМИЗАЦИИ

Ключевые слова

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

• дискретность понятность определённость результативность массовость
• дискретность
• понятность
• определённость
• результативность
• массовость

• исполнитель
• характеристики исполнителя

• круг решаемых задач среда режим работы система команд
• круг решаемых задач
• среда
• режим работы
• система команд

• формальное исполнение алгоритма

Примеры алгоритмов

Пополнение счёта телефона через терминал

• Подойти к терминалу по оплате платежей
• Выбрать оператора связи
• Ввести номер телефона
• Проверить правильность введённого номера
• Вставить денежную купюру в купюроприёмник
• Дождаться сообщения о зачислении денег на счёт
• Получить чек

Примеры алгоритмов

Рисование лошади

Примеры алгоритмов

Вычислительный алгоритм

Среднее арифметическое двух чисел

• Задать два числа
• Сложить заданные числа
• Разделить сумму на 2

Общая схема работы алгоритма

Исходные данные

Алгоритм

Результат

Исполнитель алгоритма

Исполнитель - это некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд.

Исполнитель

Неформальный

Формальный

Круг решаемых задач

Область, обстановка, условия

Среда исполнителя

Непосредственное управление

СКИ

Программное управление

Режимы работы

Исполнители алгоритмов

Исполнитель Робот

Исполнитель Кузнечик

Разработка алгоритма

Разработка алгоритма

Определение объектов,

указанных в задаче

Определение

последовательности

действий

Установление свойств

объектов, отношений

и действий с объектами

Запись

последовательности

действий с помощью

команд СКИ

Определение исходных

данных и результата

Алгоритм – модель деятельности исполнителя алгоритмов

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

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

Путь решения задачи

разделён на отдельные шаги

Дискретность

Алгоритм состоит из

команд, входящих в СКИ

Понятность

Команды понимаются

однозначно

Определённость

Обеспечивается получение

ожидаемого результата

Результативность

Обеспечивается решение

задач с различными исходными

данными

Массовость

y a = x a = y a Конец" width="640"

Дискретность (от лат. discretus – разделенный, прерывистый) означает, что путь решения задачи разделён на отдельные шаги (действия). Каждому действию соответствует предписание (команда). Только выполнив одну команду, исполнитель сможет приступить к выполнению следующей.

Начало

x, y

нет

да

x y

a = x

a = y

a

Конец

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

Окрошка «Мясная»

1-1.5 л кваса

500 г картофеля

300 г колбасы

3 яйца

200 г редиса

300 г огурцов

зелень по вкусу

сметана

соль

перец

Рецепт приготовления

Картофель отварить до готовности.

Остудить, почистить. Нарезать кубиками.

Колбасу нарезать кубиками.

Яйца нарезать кубиками.

Редис тонко нарезать.

Огурцы нарезать кубиками.

Смешать картофель, колбасу, яйца, редис, огурцы. Посолить, поперчить.

Выложить в тарелки.

Залить квасом, посыпать зеленью. Подавать со сметаной.

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

Доехать до стадиона

• Идти прямо

• Повернуть

• Идти прямо

• Сесть в автобус

• Доехать до остановки «Стадион»

Данная последовательность действий не обладает свойством определённости!

Какое расстояние нужно пройти прямо?

В какую сторону повернуть?

В какой автобус сесть?

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

Чтение книги

• Взять книгу
• Открыть первую страницу
• Пока не конец книги выполнять следующие действия:

3.1 Прочитать текст

3.2 Перелистнуть страницу

• 3.1 Прочитать текст 3.2 Перелистнуть страницу

3.3 Прочитать текст

3.4 Открыть первую страницу

• 3.3 Прочитать текст 3.4 Открыть первую страницу

Данная последовательность команд не обладает свойством результативности. Что нужно изменить?

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

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

Начало

Ввод

коэффициентов

Вычисление

дискриминанта

Дискриминант

меньше 0?

да

нет

Вычисление

значений корней

Вывод корней

«Корней нет»

Конец

Решето Эратосфена

Решето Эратосфена

Рассмотренная последовательность действий является алгоритмом, так как она удовлетворяет свойствам:

• дискретности - процесс нахождения простых чисел разбит на шаги;
• понятности - каждая команда понятна ученику 8 класса, выполняющему этот алгоритм;
• определённости - каждая команда трактуется и выполняется исполнителем однозначно; имеются указания об очерёдности выполнения команд;
• результативности - через некоторое число шагов достигается результат;
• массовости - последовательность действий применима для любого натурального n .

Алгоритм - это предназначенное для конкретного исполнителя описание последовательности действий, приводящих от исходных данных к требуемому результату, которое обладает свойствами :

• дискретности
• понятности
• определённости
• результативности
• массовости

Возможность автоматизации деятельности человека

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

Формальное исполнение алгоритма обеспечивает возможность автоматизации деятельности человека

Процесс решения задачи представляется

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

Создается машина, способная выполнять

эти операции в указанной последовательности

Человек освобождается от рутинной работы,

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

Автоматизация деятельности человека

Автоматизация гостиниц.

Профессиональная система «UCS-Shelter». Автоматизированы такие процессы как бронирование, поселение, выселение, работа со счетами гостей.

Автоматизация торговли.

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

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

Автоматизация производства

Самое главное

Исполнитель - некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд.

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

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

Способность исполнителя действовать формально обеспечивает возможность автоматизации деятельности человека.

Вопросы и задания

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

Сначала записывается исходная цепочка символов, после нее записывается исходная цепочка символов в обратном порядке, затем записывается буква, следующая в русском алфавите за той буквой, которая в исходной цепочке стояла на последнем месте. Если в исходной цепочке на последнем месте стоит буква Я, то в качестве следующей буквы записывается буква А.

Получившаяся цепочка является результатом работы алгоритма. Например, если исходная цепочка символов была ДОМ, то результатом работы алгоритма будет цепочка ДОММОДН.

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

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

1 - приписать 2

2 - разделить на 2

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

по второй число делится на 2.

Как будет преобразовано число 8, если исполнитель выполнит алгоритм 22212?

Составьте алгоритм в системе команд этого исполнителя, по которому число 1 будет преобразовано в число 16 (в алгоритме должно быть не более 5 команд).

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

1 - вычти 1

2 - умножь на 3

Первая из них уменьшает число на 1, вторая увеличивает число в 3 раза.

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

Запишите алгоритм для исполнителя Вычислитель, содержащий не более 5 команд:

а) получения из числа 3 числа 16

б) получения из числа 1 числа 25

Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии.

Система команд Черепашки состоит из двух команд:

Вперёд n (где n - целое число) – вызывает передвижение Черепашки на n шагов в направлении движения - в том направлении, куда развёрнуты её голова и корпус;

Направо m (где m - целое число) - вызывает изменение направления движения Черепашки на m градусов по часовой стрелке.

Что будет результатом исполнения Черепашкой алгоритма:

Повтори 8 [ Направо 45 Вперёд 45 ]?

Исполнитель Робот действует на клетчатом поле, между соседними клетками которого могут стоять стены. Робот передвигается по клеткам поля и может выполнять следующие команды, которым присвоены номера:

1 - Вверх

2 - Вниз

3 - Вправо

4 - Влево

При выполнении каждой такой команды Робот перемещается в соседнюю клетку в указанном направлении. Если же в этом направлении между клетками стоит стена, то Робот разрушается.

В какой клетке должен находиться исполнитель Робот, чтобы после выполнения алгоритма 3241 в неё же и вернуться?

Кто может быть исполнителем алгоритма?

К чему может привести отсутствие какого-либо свойства у алгоритма?

Приведите примеры.

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

В чём важность возможности формального исполнения

алгоритма?

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

Что называют алгоритмом?

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

«компьютер»?

Какие команды должны быть у робота, выполняющего функции:

а) кассира в магазине?

б) дворника?

в) охранника?

Приведите пример формального исполнителя.

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

Приведите примеры алгоритмов, изучаемых вами в

школе.

Подберите синонимы к слову «предписание».

Что такое команда, система команд исполнителя?

Последовательность чисел строится по следующему алгоритму:

первые два числа последовательности принимаются равными 1;

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

Запишите 10 первых членов этой последовательности.

А

В

Опорный конспект

Алгоритм - это предназначенное для конкретного исполнителя описание последовательности действий, приводящих от исходных данных к требуемому результату, которое обладает свойствами дискретности, понятности, определённости, результативности и массовости .

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

Дискретность

Понятность

Определённость

Результативность

Массовость

Электронные образовательные ресурсы

• http://school-collection.edu.ru/catalog/res/07e215ef-cd48-450d-8cf4-f5777cd832b2/?interface=catalog – решето Эратосфена
• http://files.school-collection.edu.ru/dlrstore/58e9a0c3-11df-4c94-a5eb-b0a7b359ea35/9_32.swf - исполнители алгоритмов

СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ

ОСНОВЫ АЛГОРИТМИЗАЦИИ

Ключевые слова

• словесное описание
• построчная запись
• блок-схема
• школьный алгоритмический язык

Марков А.А. (1903—1979) установил, что алгоритмы должны содержать предписания двух видов:

1) функциональные операторы - предписания, направленные на непосредственное преобразование информации;

2) логические операторы - предписания, определяющие дальнейшее направление действий.

Именно эти операторы положены в основу большинства способов записи алгоритмов.

Основные способы записи алгоритма

Графические

Словесные

На алгоритмических языках

Последователь-ность рисунков

Школьный алгоритмический

язык

Словесное описание

Язык программирова-ния

Построчная запись

Структурограмма

Блок-схема

Словесное описание

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

Пример . Словесное описание алгоритма нахождения наибольшего общего делителя (НОД) пары целых чисел (алгоритм Евклида).

Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы X и Y . Запишите первое из заданных чисел в столбец Х , а второе - в столбец Y . Если данные числа не равны, замените большее из них на результат вычитания из большего числа меньшего.

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

Построчная запись

Правила построчной записи алгоритма

Каждое предписание записывается с новой строки

Предписание (шаги) алгоритма нумеруются

Исполнение алгоритма происходит в порядке

возрастания номеров шагов, начиная с первого,

если нет особых указаний

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

Y , то перейти к п. 5, иначе перейти к п. 7. 5. Заменить X на X-Y . 6. Перейти к п. 3. 7. Заменить Y на Y-X 8. Перейти к п. 3. 9. Считать Х искомым результатом. 10. Конец." width="640"

Построчная запись алгоритма Евклида

Построчная запись алгоритма Евклида

1. Начало.

2. Обозначить первое из заданных чисел Х, второе - Y .

3. Если Х = Y то перейти к п. 9.

4. Если X Y , то перейти к п. 5, иначе перейти к п. 7.

5. Заменить X на X-Y .

6. Перейти к п. 3.

7. Заменить Y на Y-X

8. Перейти к п. 3.

9. Считать Х искомым результатом.

10. Конец.

Графические способы

Структурограмма

Последовательные картинки

Блок-схемы

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

Блок начала или конца алгоритма

Блок ввода или вывода данных

Блок обработки данных

Блок проверки условия

Блок пояснительных записей

Y Нет Да Определение большего из X и Y Y:=Y-X X:=X-Y Уменьшение большего числа на величину меньшего НОД:=Х Определение НОД НОД Вывод НОД Конец" width="640"

Запись алгоритма Евклида с помощью блок-схемы

Начало

Ввод значений X и Y

X,Y

Да

X=Y

Нет

Проверка равенства X и Y

XY

Нет

Да

Определение большего

из X и Y

Y:=Y-X

X:=X-Y

Уменьшение большего числа на величину меньшего

НОД:=Х

Определение НОД

НОД

Вывод НОД

Конец

Алгоритмические языки

Алгоритмические языки - формальные языки, предназначенные для записи алгоритмов.

Характеристики алгоритмического языка

Набор используемых символов

Алфавит

Система правил образования

конструкций языка

Синтаксис

Семантика

Система правил, определяющих

смысл и способ употребления

конструкций языка

Общий вид программы на школьном алгоритмическом языке:

алг

нач

кон

Алгоритм для исполнителя Водолей

алг переливания

нач

наполнить сосуд ёмкостью 8 л из сосуда ёмкостью 12 л

наполнить сосуд ёмкостью 5 л из сосуда ёмкостью 8 л

вылить всё из сосуда ёмкостью 5 л в сосуд ёмкостью 12 л

вылить всё из сосуда ёмкостью 8 л в сосуд ёмкостью 5 л

наполнить сосуд ёмкостью 8 л из сосуда ёмкостью 12 л

долить из сосуда ёмкостью 8 л сосуд ёмкостью 5 л

вылить всё из сосуда ёмкостью 5 л в сосуд ёмкостью 12 л

кон

Самое главное

Существуют различные способы записи алгоритмов:

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

Каждый из этих способов обладает своими достоинствами и недостатками.

Вопросы и задания

Представьте в виде построчной записи алгоритм решения следующей задачи:

«Имеются четыре арбуза различной массы. Как, пользуясь чашечными весами без гирь, путём не более пяти взвешиваний расположить их по возрастанию веса?».

Запишите на алгоритмическом языке алгоритм построения окружности заданного радиуса r , проходящей через заданные точки А и В .

Каковы основные способы записи алгоритмов?

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

«Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?».

Чем вызвано существование многих способов записи

алгоритмов?

Дайте словесное описание алгоритма сложения двух

обыкновенных дробей a/b и c/d .

Опорный конспект

Способы записи алгоритмов

Алгоритмический

язык

Словесный

Блок-схема

Обычный

разговорный

язык

Геометрические

фигуры

Слова имеют

заданный смысл и

способ записи

ОБЪЕКТЫ АЛГОРИТМОВ

ОСНОВЫ АЛГОРИТМИЗАЦИИ

Ключевые слова

• величина
• константа
• переменная
• тип
• имя
• присваивание
• выражение
• таблица

Величины

Алгоритмы описывают последовательность действий над некоторыми информационными объектами .

Величина в информатике – это отдельный информационный объект.

Информационный объект

Число

Символ

Строка

Таблица

Величина

Переменная

Постоянная

(больше) = (не меньше) = (равно) И (конъюнкция) ИЛИ (дизъюнкция) НЕ (инверсия) + (сложение) (вычитание) * (умножение) / (деление) Операнды - объекты, над которыми выполняют операции." width="640"

Операции над величинами

Операции над величинами

Логические

Арифметические

Отношения

(больше)

= (не меньше)

= (равно)

И (конъюнкция)

ИЛИ (дизъюнкция)

НЕ (инверсия)

+ (сложение)

• (вычитание)

* (умножение)

/ (деление)

Операнды - объекты, над которыми выполняют операции.

Типы величин

Тип величины в алгоритме

Целая

Числовой

Вещественная

Один

символ

Символьная

Текстовый

Литерная

Строка

символов

ДА (ИСТИНА, TRUE, 1)

Логический

НЕТ (ЛОЖЬ, FALSE, 0)

Имя величины

Имя величины в алгоритме

Латинская

буква

A, B, M, AP

Латинская

буква и цифра

A1, B4, M2

Мнемоническое

имя

SUMMA, PLAN

5) и (X

Выражения

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

Выражения

Логические

Арифметические

Строковые

Операция

сцепления (+).

А=`том`

`a`+А= `атом`

(X5) и (X

Команда присваивания

:=

Свойства присваивания

Пока переменной не присвоено значение, она

остаётся неопределённой

Значение, присвоенное переменной, сохраняется

до следующего присваивания

Если переменной присваивается новое значение,

то предыдущее её значение теряется

Алгоритм обмена значений переменных

Алгоритм, в результате которого переменные А и В литерного типа обменяются своими значениями.

Решение

!

Верно

Неверно



А:=В

В:=А

алг обмен значениями ( лит А, В)

арг А, В

рез А, В

нач лит М

М:=А

А:=В

В:=М

кон

Аналогия с перемещением

Алгоритм перемещения зайца из клетки 1 в клетку 2, а волка - из клетки 2 - в клетку 1.

Нужна клетка 3.

3

2

1

Табличные величины

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

Таблица

Прямоугольная

Линейная

Одномерный

массив

Двумерный

массив

Дни недели

Табель

успеваемости

Примеры линейных таблиц

1

Васечкин

6

2

3

6

1

4

5

0

0

1

Понедельник

2

Вторник

3

Среда

4

Четверг

5

6

Пятница

Суббота

7

Воскресенье

Количество пропущенных учеником уроков

Дни недели

Пример прямоугольной таблицы

1

2

Васечкин

1

2

Ионов

6

3

.

6

3

0

Радугина

4

0

1

.

0

5

.

.

0

0

0

.

0

1

19

.

0

6

.

0

.

Чабанюк

.

.

.

.

0

0

0

.

.

.

.

.

0

0

.

0

Количество уроков, пропущенных учениками класса

Самое главное

Величина в информатике – это отдельный информационный объект (число, символ, строка, таблица и др.).

Величины делятся на:

постоянные - значения указываются в тексте алгоритма и не меняются в процессе его исполнения

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

Тип величины: целый, вещественный, логический, символьный и литерный.

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

Таблица (массив) - набор некоторого числа однотипных элементов, которым присвоено одно имя. Положение элемента в таблице однозначно определяется его индексами.

Вопросы и задания

Запишите логическое выражение, истинное при выполнении указанного условия и ложное в противном случае:

а) x принадлежит отрезку [0; 1]

б) x лежит вне отрезка [0; 1]

в) каждое из чисел x, y положительно

г) хотя бы одно из чисел x, y положительно

д) ни одно из чисел x, y не является положительным

е) только одно из чисел x, y положительно

ж) точка с координатами ( x, y ) лежит в круге радиуса r с центром в начале координат.

Определите типы следующих величин:

а) вес человека;

б) марка автомобиля;

в) год вашего рождения;

г) площадь фигуры;

д) название месяца года;

е) количество мест в самолёте.

Сколько промежуточных переменных потребуется для того, чтобы переменной А было присвоено значение переменной В, переменной В - значение переменной С, а переменной С - значение переменной А?

Запишите соответствующий алгоритм на

алгоритмическом языке.

Запишите команду присваивания, в результате выполнения которой логическая переменная t получает значение TRUE, если выполняется указанное условие, и значение FALSE в противном случае:

а) x - положительное число

б) хотя бы одно из чисел x, y, z равно нулю

в) числа x, y, z равны между собой

г) уравнение ax 2 + bx + c = 0 имеет ровно один корень.

Какие команды присваивания составлены правильно?

а) A:=B

б) A=B

в) A=B+1

г) A+1:=А

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

а) ax 2 + bx + c

б)

в)

г)

д)

После выполнения команды присваивания x:=x+y значение переменной x равно 3, а значение переменной y равно 5.

Чему были равны значения переменных x и y до выполнения указанной команды присваивания?

Переведите из линейной записи в общепринятую:

а) a * b / c

б) a / b * c

в) a + b / c

г) (a + b)/ c

д) a + b / c + d

е) (a + b)/(c + d).

Приведите по одному примеру допустимых и

недопустимых значений для каждой из величин:

а) температура человека;

б) скорость автомашины;

в) площадь государства;

г) название дня недели.

Что называют выражением?

Каковы основные правила записи выражений?

Величины каких типов используются при записи

алгоритмов?

Что такое величина?

Чем отличаются постоянные и переменные величины?

Укажите тип величины, если её значение равно:

2010

14.48

'ДА'

FALSE,

– 125

'142'

1,4 · 10 5

.123Е–2

'пять'

Придумайте свой алгоритм обмена значениями

числовых переменных А и В.

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

а) (х=–1) и (x=–1) и (y

б) (y=x) и (y=–x) и (y

Запишите логическое выражение, принимающее значение TRUE, когда точка с координатами ( x, y ) принадлежит закрашенной области.

Для чего предназначена команда присваивания?

Каковы её основные свойства?

a

y

1

x

2

Вопросы и задания

Какие из приведённых ниже величин целесообразно

представлять с помощью таблиц?

Величина:

рост учеников класса

имена девочек

самая дождливая декада июня

самые жаркие дни лета

количество девочек в классе

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

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

площадь фигуры

имя человека

средний рост учеников класса

список учеников класса

названия дней недели

длины сторон нескольких треугольников

длины сторон треугольника

оценки учеников за контрольную работу

по информатике

средний балл ученика по физике

оценка ученика по физике

названия дней месяца

Опорный конспект

Величина в информатике – это отдельный информационный объект (число, символ, строка, таблица и др.).

Величина

Постоянная

Переменная

Тип величины

Текстовый

Числовой

Логический

Литерный

Символьный

Вещественный

Целый

Опорный конспект

Выражения

Логические

Арифметические

Строковые

Команда присваивания

:=

Опорный конспект

Таблица

Прямоугольная

Линейная

Одномерный

массив

Двумерный

массив

АЛГОРИТМИЧЕСКАЯ КОНСТРУКЦИЯ СЛЕДОВАНИЕ

ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ

Ключевые слова

• следование
• линейные алгоритмы

Основные алгоритмические конструкции

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

• следования,
• ветвления,
• повторения.

( Э. Дейкстра )

Эдсгер Вибе Дейкстра (1930–2002). Выдающийся нидерландский учёный, идеи которого оказали огромное влияние на развитие компьютерной индустрии.

Следование

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

Алгоритмы, в которых используется только структура «следование», называются линейными алгоритмами .

Действие 1

Действие 2

Алгоритмическая структура «следование»

Линейный алгоритм приготовления отвара шиповника

Начало

Столовую ложку сушёных плодов

шиповника измельчить в ступке

Залить стаканом кипячёной воды

Кипятить 10 минут на слабом огне

Охладить

Процедить

Конец

Линейный алгоритм для исполнителя Робот

СКИ исполнителя Робот: вверх , вниз , влево , вправо и закрасить .

алг узор

нач

закрасить

вправо

вправо

закрасить

вниз

влево

закрасить

вверх

влево

кон

Вычисления по алгоритму

Алгоритм

Шаг алгоритма

Переменные

x

1

y

2

s

3

4

5

х:= 2

у:=х*х

у:=у*у

х:=у*х

s:=x+y

2

-

-

4

2

-

-

2

16

16

-

32

48

16

32

Ответ : s = 48

Целочисленная арифметика

С помощью операции div вычисляется целое частное, с помощью операции mod - остаток.

7 mod 3 = 1

7 div 3 = 2

7 : 3 = 2 (ост.1)

8 : 3 = 2 (ост.2)

10 : 3 = 3 (ост.1)

13 : 4 = 3 (ост.1)

11 : 4 = 2 (ост.3)

8 : 5 = 1 (ост.3)

Алгоритм работы кассира

Алгоритм работы кассира, выдающего покупателю сдачу ( s ) наименьшим количеством банкнот по 500 ( k 500), 100 ( k 100), 50 ( k 50) и 10 ( k 10) рублей.

k500:=s div 500

s:=s mod 500

k100:=s div 100

s:=s mod 100

k50:=s div 50

s:=s mod 50

k10:=s div 10

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

Самое главное

Для записи любого алгоритма достаточно трёх основных алгоритмических конструкций (структур): следования, ветвления, повторения.

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

Алгоритмы, в которых используется только структура «следование», называются линейными .

Вопросы и задания

Какие алгоритмы называются линейными?

Приведите пример линейного алгоритма из

повседневной жизни.

Запишите линейный алгоритм, исполняя который Робот

нарисует на клетчатом поле следующий узор и

вернётся в исходное положение:

По алгоритму восстановите формулу.

a1:=1/x

a2:=a1/x

a3:=a2/x

a4:=a3/x

y:=a1+a2

y:=y+a3

y:=y+a4

Для заданного количества суток ( tfh ) требуется

определить количество часов ( h ), минут ( m ) и секунд ( c ).

Известно, что 1 миля = 7 вёрст, 1 верста = 500 саженей,

1 сажень = 3 аршина, 1 аршин = 28 дюймов,

1 дюйм = 25,4 мм.

Пользуясь этой информацией, составьте линейный

алгоритм перевода расстояния Х миль в километры.

Исходное данное - целое трёхзначное число x .

Выполните для x = 125 следующий алгоритм.

a:=x div 100

b:=x mod 100 div 10

c:=x mod 10

s:=a+b+с.

Чем является результат s этого алгоритма?

Определите значение целочисленных переменных x и

y после выполнения фрагмента алгоритма.

x:=336

y:=8

x:=x div y

y:=х mod у

Какое значение получит переменная у после

выполнения фрагмента алгоритма?

х:=1

у:=2*x

у:=у+3

у:=у*х

y:=у+4

y:=y*х

y:=y+5

Восстановите формулу вычисления у для произвольного значения х .

*

Опорный конспект

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

Алгоритмы, в которых используется только структура «следование», называются линейными .

Действие 1

Действие 2

АЛГОРИТМИЧЕСКАЯ КОНСТРУКЦИЯ ВЕТВЛЕНИЕ

ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ

Ключевые слова

• ветвление
• полная форма ветвления
• неполная форма ветвления
• разветвляющийся алгоритм
• простое условие
• составное условие

Ветвление

Ветвление - алгоритмическая конструкция, в которой в зависимости от результата проверки условия («да» или «нет») предусмотрен выбор одной из двух последовательностей действий (ветвей).

Алгоритмы, в основе которых лежит структура «ветвление», называют разветвляющимися.

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

если

то

иначе

все

Да

Условие

Нет

Действие 1

Действие 2

Пример

алг правописание частиц НЕ, НИ

нач

если частица под ударением

то писать НЕ

иначе писать НИ

все

кон

Неполная форма ветвления

если

то

все

Условие

Да

Нет

Действие 1

Пример:

алг сборы на прогулку

нач

если на улице дождь

то взять зонтик

все

кон

B А больше В A = B А больше или равно В A B А не равно В" width="640"

Операции сравнения

A B

А меньше В

A B

А меньше или равно В

A = B

А равно В

A B

А больше В

A = B

А больше или равно В

A B

А не равно В

0 Y:=-X Y:=X Y Конец" width="640"

Вычисление функции f( x ) =| x |

Начало

Список данных

X, Y -вещ

Х

да

нет

Х 0

Y:=-X

Y:=X

Y

Конец

=A) and (Xнет да НЕТ ДА Ответ : Не принадлежит Ответ : Принадлежит A=2 X=4 B=6 B=4 X=6" width="640"

Простые и составные условия

Простые условия состоят из одной операции сравнения. Составные условия получаются из простых с помощью логических связок and ( и ), or ( или ), not ( не ).

Пример. Алгоритм определения принадлежности точки Х отрезку [ A; B ].

A, B, X

(X=A) and (X

нет

да

НЕТ

ДА

Ответ : Не принадлежит

Ответ : Принадлежит

A=2

X=4

B=6

B=4

X=6

Y B Y Y = B Y = A Y:=A Шаг Константы А В 10 1 С 2 Переменная 30 Условие Y 20 3 4 нет да BY Y:=B 10 30 10 (Да) да нет CY 30 20 30 (Нет) Y:=C Ответ : Y = 30" width="640"

Наибольшая из 3-х величин

Переменной Y присваивается значение большей из трёх величин A , B и C .

C Y

B Y

Y = B

Y = A

Y:=A

Шаг

Константы

А

В

10

1

С

2

Переменная

30

Условие

Y

20

3

4

нет

да

BY

Y:=B

10

30 10 (Да)

да

нет

CY

30

20 30 (Нет)

Y:=C

Ответ : Y = 30

Решение линейного уравнения ax + b = 0

Список данных

a, b, x - вещ

a, b

да

нет

a0

да

нет

b0

x:=-b/a

Корней нет

Любое число

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

В какую клетку переместится Робот после выполнения следующего фрагмента алгоритма.

если справа свободно или снизу свободно

то закрасить

все

если справа стена

то влево

все

если слева стена

то вправо

все

б

а

Самое главное

Для записи любого алгоритма достаточно трёх основных алгоритмических конструкций (структур): следования, ветвления, повторения.

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

Алгоритмы , в основе которых лежит структура «ветвление», называют разветвляющимися .

Y Нет А =0 K:=K+1 Y:=B B =0 Нет Да K:=K+1 да нет CY K Y:=C" width="640"

Вопросы и задания

Известно, что 31 января 2011 года приходится на

понедельник. Какие значения должны быть присвоены

литерной переменной y в алгоритме, определяющем

день недели для любого числа (chislo) января 2011

года?

chislo:= chislo mod 7

если chislo=3 то у:='…‘

если chislo=4 то у:='…‘

если chislo=5 то у:='…‘

если chislo=6 то у:='…‘

если chislo=0 то у:='…‘

если chislo=1 то у:='…‘

если chislo=2 то у:='…'

Дополните алгоритм из примера 9 так, чтобы с его

помощью можно было найти наибольшую из четырёх

величин A, B, C и D .

Приведите пример разветвляющегося алгоритма из

повседневной жизни.

Какие алгоритмы называют разветвляющимися?

Запишите алгоритм определения принадлежности

точки Х отрезку [ А; В ] с использованием комбинации из

двух ветвлений.

Определите, есть ли среди цифр заданного целого

трёхзначного числа одинаковые

Запишите алгоритм правописания приставок,

начинающихся с буквы «з» («с»).

Составьте алгоритм, с помощью которого можно

определить, существует ли треугольник с длинами

сторон a, b, с .

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

чисел среди заданных целых чисел А, В и С .

Составьте алгоритм, с помощью которого можно

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

длинами сторон a, b, с равносторонним.

Даны две точки на плоскости.

Определите, какая из них находится ближе к началу

координат.

Составьте алгоритм возведения чётного числа в

квадрат, а нечётного - в куб.

Какая задача решается с помощью следующего

алгоритма?

Y:=A

К :=0

да

нет

Да

BY

Нет

А =0

K:=K+1

Y:=B

B =0

Нет

Да

K:=K+1

да

нет

CY

K

Y:=C

Опорный конспект

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

Алгоритмы , в основе которых лежит структура «ветвление», называют разветвляющимися .

Условие

Условие

Да

Да

Нет

Нет

Действие 1

Действие 2

Действие 1

Неполная форма ветвления

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