Лекция №1 по математическим основам информатики
план-конспект урока по информатике и икт (9 класс) по теме

Введение.

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

      Что такое информация - это до сих пор дискуссионный вопрос.

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

Современное научное представление об информации очень точно сформулировал, "отец" кибернетики Норберт Винер. А именно:

Информация — это обозначение содержания, полученного из внешнего мира в процессе нашего приспособления к нему и приспособления к нему наших чувств.

Как измерять информацию ?

Американский инженер Р. Хартли в 1928 г. процесс получения информации рассматривал как выбор одного сообщения из конечного наперёд заданного множества из N равновероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определял как двоичный логарифм N.

 I = log2N

Обобщил формулу американский ученый Клод Шеннон. Он ввел понятие информационной энтропии, как меры неопределенности состояния сообщений. Если сообщения не равновероятны, то для измерения этой энтропии или все равно, что количества информации, он предложил в 1948 г. такую формулу:

или     I = - (p1log2p1  + p2log2p2 + ...+ pNlog2pN),
где pi — вероятность того, что именно i-е сообщение выделено в наборе из N сообщений. Из формулы следует, энтропия I (количество информации) максимальна, когда все события равновероятны. P1 = P2 =  ….. = PN

Если основание логарифма равно 2, то единицу измерения называют -  бит. Она главная в цифровой технике. Если равно 10, называется дит(хартли). Если логарифм натуральный, то ед. изм. называется нат.

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

ТЕМА 1. Математические основы компьютерной обработки информации.

1. Двоичная и шестнадцатиричная системы счисления (СС).

Кроме десятичной СС существует бесчисленное множество систем С. СС, в которой для записи числа используется N знаков, называется N-ричной. Например, количество 12 можно представить так.          000000000000 – в одноричной СС,

110 – в 3-ех ричной,   14 – в 8-и ричной,   12 – в 10-ой СС.

В общем случае, чтобы записать число Х в N-ричной СС, необходимо представить Х в следующей форме :

или                 X= ak Nk + ak-1 Nk-1 + ak-2 Nk-2 + …..+a0 N0 ,                                                                                    

где k=[logNX] – целая часть числа  и  все ai < N.

Само же число в N–ричной СС будет - ak ak-1 ak-2 ak-3….a0

Например  102 = 1*32+0*31+1*30 = 1013 

                    102 = 1*23+0*22+1*21+0*20 = 10102

                    102 = 2*41+2*40 = 224

                    102 = 2*51+0*50 = 205

На дом : представить 100 в 2,3,4,5 СС.

В ЭВМ базовая СС – двоичная, т.е. для представления числа используется два знака – 0 и 1. В качестве дополнительной (для удобства записи исп-ся 16-и ричная). По международному соглашению для нее принято употреблять знаки  0 - 9,A,B,C,D,E,F.

Величина способная принимать только два значения 0 или 1 называется бит. 8 бит – 1 байт.

1Кбайт=1024б, 1Мб=1024Кб, 1Гб=1024Мб, 1Тераб=1024Гб, 1Петаб=1Тб.

1457664 ≈ 1,4 Мб. Объем памяти в ЭВМ(количество информации) измеряется в битах, байтах, Кб, Мб, Гб, Тб.

2. Перевод чисел из двоичной СС в 10-ую.

Алгоритм понятен из следующего примера.

7 6 5 4 3 2 1 0

          1 0 1 0 0 1 1 12 = (167)10

1*27+0*26+1*25+0*24+0*23+1*22+1*21+1*20=167

Задание. По коду (ASCII) байтовый код z=01011010. Перевести в дес. СС. (90)

Задание. Перевести число 20113 в десятичную СС.

3. Перевод из 10-ой СС в 2-ую СС.

Алгоритм понятен из следующего примера.

                            35/2

    3510=1000112

Задание. По международному коду ASCII код знака N в 10-ой СС = 72. Определить байт для N ?       (01001110)

Задание. Перевести 3510 в трехричную  (1022)

Задание. В ЭВМ знак на клавиатуре кодируется одним байтом. Сколько max количество знаков можно закодировать.? Какого max числовое значение байта?  

4.  Сложение двоичных чисел

0+0=0   0+1=1   1+0=1    1+1=10        1 0 1 1 0 1 1 0

1 0 0 0 1 1 1

5. Перевод чисел из двоичной в шестнадцатиричную СС.  

Здесь можно использовать следующую таблицу.

Делят последовательность нулей и единиц на тетрады (четверки) начиная с конца.       01001011 = 4B

6. Перевод чисел из 16-ой в 2-ую СС.

Каждую шестнадцатиричную цифру представляют двоичной тетрадой.

Например   2EA = 0010 1110 1010

Задание . Сложить два числа                  AA+BB=       165

Задание. Сложить в восьмиричной СС    37+48   ?     106

Задание. Сколько бит необходимо, чтобы закодировать 5 букв.

 Задание. Сколько знаков можно закодировать N битами?

Логические выражения и логические операции

Операции выполняются над логическими константами и переменными.

Для обработки логических выражений была создана наука математическая логика - алгебра высказываний, или алгебра логики или булева алгебра (названа в честь французского математика Джорджа Буля). Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем, которые лежат в основе работы любого компьютера. Логические операции - главные, именно через них компьютер выполняет арифметические + - / *.

1. Логическое сложение (дизъюнкция)  «или» , «OR»

Обозначатся  V

Хотя бы одна 1

 результат = 1

2. Логическое умножение (конъюнкция)  «и» , «AND»

Обозначатся  Λ(&)

Хотя бы один 0

 результат = 0

3. Логическое отрицание (инверсия)  «не»  «NOT»

Обозначатся  ¬  (или чертой сверху бита)        ¬1=0   ¬0=1

4. Логическое следование (импликация)  «если … то …»

Обозначатся  =>

Ложно тогда и только тогда,

когда А истинно и В ложно

5. Логическое тождество (эквиваленция)  

Обозначатся  <=>

Истина, когда значения

одинаковы

Импликацию можно выразить     А => В = v В.

Эквиваленцию можно выразить   А  В = (v В) • (v А).

"Быть иль не быть - вот в чем вопрос." (В. Шекспир)     А V ¬ A <=> В
"Если хочешь быть красивым, поступи в гусары." (К. Прутков) А => В

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

Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке:
     1. (отрицание) инверсия;
     2. (умножение) конъюнкция;
     3. (сложение) дизъюнкция;
     4. импликация и эквивалентность.
Законы логики
     1. ¬ ¬a = a;
     2. a Λ b = b Λ a ;
     3. A V b = b V a ;
     4. a Λ (b Λ c) = (a Λ b) Λ c ;
     5. a V (b V c) = (a V b) V c ;
     6. a Λ (b V c) = (a Λ b) V ( a Λ c ) ;
     7. A V (b Λ c) = (a V b) Λ ( a V c) ;
     8. a Λ a = a
     9. a V a = a
     10. A V ¬a = 1 ;
     11. a Λ ¬a = 0 ;
     12. a Λ 1 = a
     13. A V 1 = 1
     14. a Λ 0 = 0
     15. a V 0 = a
     16. ¬ ( a Λ b ) = ¬ a V ¬ b законы де Моргана;
           ¬ ( a V b ) = ¬ a Λ  ¬ b;
     17. a => b  = ¬ a V b .

  Пример. Упростить выражения ¬  (a Λ b) V¬ b; ¬ (a Λ b) V¬ b; так, чтобы в  

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

¬ (a Λ b) V¬ b = ¬a V ¬b V ¬ b = ¬a V ¬b   (16) и (9)

¬ (¬b Λ c V c) = ¬(¬b Λ c) Λ ¬c = (b V ¬c) Λ ¬c = (b Λ ¬c) V (¬c Λ ¬c) =

   (b Λ ¬c) V ¬c = ¬c.     (16)  (16) (6) (8)
На дом : упростить   ¬(¬a Λ c) V b Λ ¬c                         ответ (a V ¬c)

Минимизировать функцию:

F(x, y ,z)=(x V y) Λ z V x Λ y Λ z Λ (¬z V x Λ y) V ¬z Λ x Λ y V ¬x Λ y Λ ¬z

                                                                                       Ответ      x Λ z V y

Электронные логическин схемы

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

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

1.   «или» - дизъюнктор

          2.    «или-не» элемент Пирса

3.    «и» - конъюнктор

4.    «и-не» - элемент Шеффера

5.   «не» - инвертор

Задача. Построить электронный элемент «сумматор» на два входа (бита)

             x+y=z1z0        =>               z1=xΛy       z0=(xΛ¬y)V(¬xΛy)

Оптимизированная схема

Пример решения логических задач.

Пример. Трое болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

Джон   — Шумахер не придет первым,первым будет Хилл.  

Ник     —  победителем будет Шумахер, а  Алези не быть первым.

Питер  — Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

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

Решение. Введем обозначения для логических высказываний:

Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

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

Зафиксируем высказывания каждого из друзей:

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

Высказывание  истинно только при Ш=1, А=0, Х=0. 

Ответ. Победителем этапа гонок стал Шумахер.