Основы информатики (элементы комбинаторики, алгебры логики и системы кодирования информации)

БАШКИРСКАЯ АКАДЕМИЯ

ГОСУДАРСТВЕННОЙ СЛУЖБЫ И УПРАВЛЕНИЯ
ПРИ ПРЕЗИДЕНТЕ РЕСПУБЛИКИ БАШКОРТОСТАН

Кафедра информатики

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

Основы информатики

(элементы комбинаторики, алгебры логики и системы кодирования информации)

Уфа  2011

1. Элементы комбинаторики

1.1.Правило произведения

Если из некоторого множества А элемент а можно выбрать ka способами, а элемент b из множества B kb способами, то совокупность (a,b) можно образовать ka  kb способами.

Пример. На курсе 3 группы. В первой - 25 человек, во второй - 30, в третьей - 20. Сколькими способами из них можно выбрать одного студента?

Решение: из первой группы одного человека можно выбрать 25 способами, из второй - 30, из третьей - 20. Чтобы найти ответ, нужно сложить все эти способы: 25 + 30 + 20 = 75.

Ответ: выбрать одного студента из трех групп можно 75 способами.

 Пример. На курсе есть 3 группы. В первой - 25 человек, во второй - 30, в третьей - 20. Сколькими способами из каждой из них можно выбрать по одному студенту?

Решение: из первой группы одного человека можно выбрать 25 способами, из второй - 30, из третьей - 20. Чтобы найти ответ, нужно перемножить эти числа: 25·30·20 = 15 000.

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

1.2.Перестановки

              Перестановки – это число возможных последовательных расположений n элементов. Pn=n!, где n!=12…n – читается как n факториал.

Пример. Сколькими способами можно расставить в шеренгу студентов группы из 25 человек?

Решение: число способов есть число перестановок из 25 элементов, т. е.:

P25 = 25 · 24 · 23·… · 1 = 25! = 1,55 · 1025.

Ответ: расставить в шеренгу студентов группы из 25 человек можно 1,55·1025 способами.

1.3.Размещения

              Размещениями называется число способов выбора m элементов из n, когда порядок в выборке важен.

.

Пример. Из группы, состоящей из 25 человек, надо выбрать шахматную команду из четырех человек на I, II, III и IV доски. Сколькими способами это можно сделать?

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

Ответ: выбрать из 25 человек шахматную команду из четырех человек на I, II, III и IV доски можно 303 600 способами.

1.4.Сочетания

              Если порядок отбираемых m элементов не важен, то говорят о числе сочетаний из n элементов по m.

.

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

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

Ответ: из группы в 25 человек можно выбрать баскетбольную команду 53130 способами.

2. Системы кодирования информации

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

I     V     X      L     C       D       M

1     5     10    50   100   500    1000

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

VI = 5 + 1 = 6;     IV = 5 - 1 = 4;

MCMXCVII = 1000 + (-100 +1000) + (-10 +100) + 5 + 1 + 1 = 1997.

В позиционных системах счисления одна и та же цифра имеет различное значение в зависимости от того, какое место (позицию) она занимает в последовательности цифр, изображающей число. Например, в последовательности цифр 555,55 одна и та же цифра 5 соответствует количеству сотен, десятков, единиц, десятых долей единицы и сотых долей единицы, а все число может быть представлено в виде:

555,55 = 5102 + 5101 + 5100 + 510-1 + 510-2.

В этих примерах число 10 является основанием системы счисления, определяемым количеством используемых цифровых знаков (0,1,…,9).

Для двоичной системы                         0 и 1.

Для восьмиричной системы                 0, 1, 2, 3, 4, 5, 6, 7.

Для шестнадцатиричной системы       0, 1, …, 9, A(10), B(11), C(12), D(13), E(14), F(15).

Алгоритм перевода целого десятичного числа Nв позиционную систему с основанием p:

1. Разделить нацело число N на p.
     2. Полученный остаток от деления дает цифру, стоящую в нулевом разряде p-ичной записи числа N.
     3. Полученное частное снова разделить нацело на p и снова запомнить полученный остаток - это цифра первого разряда, и т.д.
     4. Такое последовательное деление продолжается до тех пор, пока частное не станет равным 0.

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

     Для оформления записи перевода предлагается один из возможных способов: слева от черты записываются неполные частные от целочисленного деления на основание, а справа - остатки от деления.
     Например, надо перевести десятичное число 26 в двоичную, троичную и шестнадцатеричную системы счисления.

Результат: 2610=110102, 2610=2223, 26=1A16.

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

10   101   111                                        1010       1111

2       5       7                                         10=A      15=F

         2578                                                      AF16

Вся обрабатываемая на ЭВМ информация, как исходные данные, так и программы, преобразуется в двоичную форму (кодируется). Объем памяти, занимаемой одним из символов двоичной системы (т.е. 1 или 0), называется битом. С помощью набора битов можно закодировать любой знак и любое число.

Символьная информация в компьютере кодируется с помощью восьмиразрядных двоичных кодов. Полное число таких комбинаций нулей и единиц равно 28 = 256. Каждому символу ставится в соответствие единственный код. Таким образом, с помощью восьмиразрядного кода можно закодировать строчные и прописные буквы латинского и русского алфавитов, цифры, знаки арифметических операций, специальные символы и др. Объем памяти, занимаемой одним символом, закодированным с помощью восьмиразрядных двоичных кодов, равен 8 битам, или 1 байту.

Если в алфавите используемого языка всего 42 символа, выясним, какого разряда должны быть коды.

Если двухразрядными, то на месте первого разряда может находиться один из двух символов: 0 или 1; на месте второго – также один из двух символов: 0 или 1. По правилу произведения всего таких пар можно составить 2∙2=4. То есть, с помощью двухразрядных кодов можно закодировать 4 символа, а в нашем алфавите их 42.

Если коды будут трехразрядными, то всего символов может быть 2∙2∙2=8, если четырехразрядными, то 2∙2∙2∙2=16, если пятиразрядными, то 2∙2∙2∙2∙2=32, если шестиразрядными, то 2∙2∙2∙2∙2∙2= 64. Этого количества достаточно, чтобы можно было закодировать 42 символа алфавита данного языка.

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

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

В обычной алгебре числа заменяют буквами и когда формулируют какой-либо закон, например a(b+c)=ab+ac, то подразумевают, что он выполняется на некотором множестве числовых значений тех переменных, которые в него входят. В алгебре логики тоже используют буквы не только для обозначения конкретных высказываний, но и для обозначения логических переменных. Только эти переменные могут принимать лишь два значения: И и Л (истина и ложь). Логические выражения, полученные из этих переменных с помощью логических операций, также могут принимать лишь два значения И и Л.

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

а)  пятью пять двадцать пять (истинное высказывание);

б) 2+6>8 (ложное высказывание);

в) сумма чисел 4 и 1 больше числа 8 (ложное высказывание);

г) II + VI > VII (истинное высказывание);

Высказывание, которое можно разложить на части, называется сложным, а неразложимое далее высказывание - простым. Например, "Функция y = aх2 + bх + с непрерывна и дифференцируема при всех значениях х" состоит из двух простых высказываний: "Функция y=ах2+bх+с непрерывна при всех значениях х" и "Функция  y=ах2+bх+с дифференцируема при всех значениях х".

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

3.1.Отрицание

Отрицанием высказывания а называют такое высказывание , что ложно, если а истинно, и истинно, если а ложно. Обозначение читается так: "Не а", или "Неверно, что а". Следующая таблица показывает связь между высказываниями а и:

Буквы "и" и "л" - сокращение слов "истина" и "ложь" соответственно. Эти слова в логике называют значениями истинности. Таблица называется таблицей истинности  а.

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

3.2.Конъюнкция

Конъюнкцией двух высказываний а и b называется такое высказывание ab (читается "а и b"), которое истинно тогда и только тогда, когда истинны оба составляющих его высказывания. Это определение распространяется и на любое конечное число высказываний. Таблица истинности ab выглядит так: