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

Вопрос №1

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

2. Сообщения, осведомляющие о положении дел, о состоянии чего-нибудь. (Научно-техническая и газетная информации, средства массовой информации — печать, радио, телевидение, кино).

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

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

1. Объективность информации. Объективный – существующий вне и независимо от человеческого сознания. Информация – это отражение внешнего объективного мира. Информация объективна, если она не зависит от методов ее фиксации, чьего-либо мнения, суждения.

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

1. Достоверность информации. Информация достоверна, если она отражает истинное положение дел. Объективная информация всегда достоверна, но достоверная информация может быть как объективной, так и субъективной. Достоверная информация помогает принять нам правильное решение. Недостоверной информация может быть по следующим причинам:
• преднамеренное искажение (дезинформация) или непреднамеренное искажение субъективного свойства;
• искажение в результате воздействия помех («испорченный телефон») и недостаточно точных средств ее фиксации.
2. Доступность информации: Мера возможности получить ту или иную информацию. На степень доступности информации влияют одновременно как доступность данных, так и доступность адекватных методов
3. Полнота информации. Информацию можно назвать полной, если ее достаточно для понимания и принятия решений. Неполная информация может привести к ошибочному выводу или решению.
4. Точность (адекватность) информации определяется степенью ее близости к реальному состоянию объекта, процесса, явления и т. п. Характеризует степень соответствия реальному объективному состоянию. Неадекватная информация может образоваться при создании новой информации на основе неполных или недостоверных данных.
   
   

Достоверные данные + неадекватные методы = неадекватная информация

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

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

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

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

Старение информации заключается в уменьшении ее ценности с течением времени. Старит информацию не само время, а появление новой информации, которая уточняет, дополняет или отвергает полностью или частично более раннюю. Научно-техническая информация стареет быстрее, эстетическая (произведения искусства) – медленнее.

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

Измерение информации

В информатике используются различные подходы к измерению информации: Содержательный подход к измерению информации.Сообщение – информативный поток, который в процессе передачи информации поступает к приемнику. Сообщение несет информацию для человека, если содержащиеся в нем сведения являются для него новыми и понятными Информация - знания человека ? сообщение должно быть информативно. Если сообщение не информативно, то количество информации с точки зрения человека = 0. (Пример: вузовский учебник по высшей математике содержит знания, но они не доступны 1-класснику). Алфавитный подход к измерению информациине связывает кол-во информации с содержанием сообщения. Алфавитный подход - объективный подход к измерению информации. Он удобен при использовании технических средств работы с информацией, т.к. не зависит от содержания сообщения. Кол-во информации зависит от объема текста и мощности алфавита. Ограничений на max мощность алфавита нет, но есть достаточный алфавит мощностью 256 символов. Этот алфавит используется для представления текстов в компьютере. Поскольку 256=2⁸, то 1символ несет в тексте 8 бит информации. Вероятностный подход к измерения информации.Все события происходят с различной вероятностью, но зависимость между вероятностью событий и количеством информации, полученной при совершении того или иного события можно выразить формулой которую в 1948 году предложил Шеннон.Количество информации - это мера уменьшения неопределенности.1 БИТ – такое кол-во информации, которое содержит сообщение, уменьшающее неопределенность знаний в два раза. БИТ- это аименьшая единица измерения информацииЕдиницы измерения информации:

1байт = 8 бит

1Кб (килобайт) = 2¹⁰ байт = 1024 байт

1Мб (мегабайт) = 2¹⁰ Кб = 1024 Кб

1Гб (гигабайт) = 2¹⁰ Мб = 1024 Мб

Формула Шеннона

I - количество информации N – количество возможных событий p_i – вероятности отдельных событий

Вопрос №2

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

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

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

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

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

Информатизация общества — организованный социально - экономический и научно-технический процесс создания оптимальных условий для удовлетворения информационных потребностей и реализации прав граждан, органов государственной власти, органов местного самоуправления, организаций, общественных объединений на основе формирования и использования информационных ресурсов

Вопрос №3

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

I	V	X	L	C	D	M

В числе цифры записываются слева направо в порядке убывания. Величина числа определяется как сумма или разность цифр в числе. Если меньшая цифра стоит слева от большей цифры, то она вычитается, если справа - прибавляется. Например, VI = 5 + 1 = 6, а IX = 10 - 1 = 9, СССXXVII=100+100+100+10+10+5+1+1=327.
В позиционных системах счисления величина, обозначаемая цифрой в записи числа, зависит от ее позиции. Количество используемых цифр называется основанием системы счисления. Место каждой цифры в числе называется позицией.

Система счисления	Основание	Алфавит
Десятичная
Двоичная
Троичная
Восьмеричная
Шестнадцатеричная		0123456789ABCDEF

Первая известная нам система, основанная на позиционном принципе - шестидесятеричная вавилонская. Цифры в ней были двух видов, одним из которых обозначались единицы, другим - десятки. Следы вавилонской системы сохранились до наших дней в способах измерения и записи величин углов и промежутков времени.
Однако наибольшую ценность для нас имеет индо-арабская десятичная система. Индийцы первыми использовали ноль для указания позиционной значимости величины в строке цифр. Эта система получила название десятичной системы счисления, так как в ней десять цифр.
Для того чтобы лучше понять различие позиционной и непозиционной систем счисления, рассмотрим пример сравнения двух чисел. В позиционной системе счисления сравнение двух чисел происходит следующим образом: в рассматриваемых числах слева направо сравниваются цифры, стоящие в одинаковых позициях. Большая цифра соответствует большему значению числа. Например, для чисел 123 и 234, 1 меньше 2, поэтому число 234 больше, чем число 123. В непозиционной системе счисления это правило не действует. Примером этого может служить сравнение двух чисел IX и VI. Несмотря на то, что I меньше, чем V, число IX больше, чем число VI.

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

Вопрос №4

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

Вид информации	Двоичный код
Числовая
Текстовая
Графическая
Звуковая
Видео

Каждая цифра машинного двоичного кода несет количество информации равное одному биту. Данный вывод можно сделать, рассматривая цифры машинного алфавита, как равновероятные события. При записи двоичной цифры можно реализовать выбор только одного из двух возможных состояний, а, значит, она несет количество информации равное 1 бит. Следовательно, две цифры несут информацию 2 бита, четыре разряда --4 бита и т. д. Чтобы определить количество информации в битах, достаточно определить количество цифр в двоичном машинном коде.

Кодирование текстовой информации В настоящее время большая часть пользователей при помощи компьютера обрабатывает текстовую информацию, которая состоит из символов: букв, цифр, знаков препинания и др. Традиционно для того чтобы закодировать один символ используют количество информации равное 1 байту, т. е. I = 1 байт = 8 бит. При помощи формулы, которая связывает между собой количество возможных событий К и количество информации I, можно вычислить сколько различных символов можно закодировать (считая, что символы - это возможные события): К = 2I = 28 = 256, т. е. для представления текстовой информации можно использовать алфавит мощностью 256 символов. Суть кодирования заключается в том, что каждому символу ставят в соответствие двоичный код от 00000000 до 11111111 или соответствующий ему десятичный код от 0 до 255. Необходимо помнить, что в настоящее время для кодировки русских букв используют пять различных кодовых таблиц (КОИ - 8, СР1251, СР866, Мас, ISO), причем тексты, закодированные при помощи одной таблицы не будут правильно отображаться в другой кодировке. Наглядно это можно представить в виде фрагмента объединенной таблицы кодировки символов. Одному и тому же двоичному коду ставится в соответствие различные символы.

Двоичный код	Десятичный код	КОИ8	СР1251	СР866	Мас	ISO
		б	В	-	-	Т

Впрочем, в большинстве случаев о перекодировке текстовых документов заботится на пользователь, а специальные программы - конверторы, которые встроены в приложения. Начиная с 1997 г. последние версии Microsoft Windows&Office поддерживают новую кодировку Unicode, которая на каждый символ отводит по 2 байта, а, поэтому, можно закодировать не 256 символов, а 65536 различных символов. Чтобы определить числовой код символа можно или воспользоваться кодовой таблицей, или, работая в текстовом редакторе Word 6.0 / 95. Для этого в меню нужно выбрать пункт "Вставка" - "Символ", после чего на экране появляется диалоговая панель Символ. В диалоговом окне появляется таблица символов для выбранного шрифта. Символы в этой таблице располагаются построчно, последовательно слева направо, начиная с символа Пробел (левый верхний угол) и, кончая, буквой "я" (правый нижний угол). Для определения числового кода символа в кодировке Windows (СР1251) нужно при помощи мыши или клавиш управления курсором выбрать нужный символ, затем щелкнуть по кнопке Клавиша. После этого на экране появляется диалоговая панель Настройка, в которой в нижнем левом углу содержится десятичный числовой код выбранного символа.

Вопрос №5

Основные понятия, элементы и формы Булевой алгебры

Логическая переменная – это переменная, которая может принимать одно из двух значений ноль и единица (истина или ложь).

Логическая константа – это константа (постоянная величина) которая может принимать значение ноль или единица (истина или ложь).

Логическая функция – это функция, которая может принимать два значения ноль и единица (истина или ложь).

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

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

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

Операция импликации

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

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

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

Операция эквивалентности

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

Выражение, образованное эквивалентностью, истинно, если истинность обоих операндов совпадает.

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

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

Вопрос №6

Алгоритм построения таблиц истинности для сложных выражений:

1. Определить количество строк:

количество строк = 2ⁿ + строка для заголовка,

n - количество простых высказываний.

1. Определить количество столбцов:

количество столбцов = количество переменных + количество логических операций;

определить количество переменных (простых выражений);

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

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

Пример: Составить таблицу истинности логического выражения:

D = А & (B Ú C).

Решение: Ù

1. Определить количество строк:

на входе три простых высказывания: А, В, С поэтому n=3 и количество строк = 2³ +1 = 9.

1. Определить количество столбцов:
• простые выражения (переменные): А, В, С;
• промежуточные результаты (логические операции):
  А - инверсия (обозначим через E);
  B Ú C - операция дизъюнкции (обозначим через F);
  а также искомое окончательное значение арифметического выражения:
  D = А & (B Ú C). т.е. D = E & F - это операция конъюнкции.
2. Заполнить столбцы с учетом таблиц истинности логических операций.

A	B	C	E	F	E & F

Построение логической функции по ее таблице истинности:

Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции
Z(X,Y):

X	Y	Z

Составить логическую функцию для заданной таблицы истинности.

Правила построения логической функции по ее таблице истинности:

1. Выделить в таблице истинности те строки, в которых значение функции равно 1.
2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент взять с отрицанием.

Решение.

1. В первой и третьей строках таблицы истинности значение функции равно 1.
2. Так как строки две, получаем дизъюнкцию двух элементов: ( ) V ( ).
3. Каждый логический элемент в этой дизъюнкции запишим в виде конъюнкции аргументов функции X и Y: (X & Y) V (X & Y).
4. Берем аргумент с отрицанием если его значение в соответствующей строке таблицы равно 0 и получаем искомую функцию:
   Z (X, Y) =( X & Y) V (X & Y).

Вопрос №7

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

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

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

Отдельные объекты, из которых состоит множество, называются элементами множества.

Множества принято обозначать большими буквами латинского алфавита, а элементы этих множеств — маленькими буквами латинского алфавита. Множества записываются в фигурных скобках { }.

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

• a ∈ X — «элемент a принадлежит множеству X»;
• a ∉ X — «элемент a не принадлежит множеству X»;
• ∀ — квантор произвольности, общности, обозначающий «любой», «какой бы не был», «для всех»;
• ∃ — квантор существования: ∃y ∈ B — «существует (найдется) элемент y из множества B»;
• ∃! — квантор существования и единственности: ∃!b ∈ C — «существует единственный элемент b из множества C»;
• : — «такой, что; обладающий свойством»;
• → — символ следствия, означает «влечет за собой»;
• ⇔ — квантор эквивалентности, равносильности — «тогда и только тогда».

Множества бывают конечные и бесконечные. Множества называются конечным, если число его элементов конечно, т.е. если существует натуральное число n, являющееся числом элементов множества. А={a₁, a₂,a ₃, ..., a_n}. Множество называется бесконечным, если оно содержит бесконечное число элементов. B={b₁,b₂,b₃, ...}. Например, множество букв русского алфавита — конечное множество. Множество натуральных чисел — бесконечное множество.

Число элементов в конечном множестве M называется мощностью множества M и обозначается |M|. Пустоемножество — множество, не содержащее ни одного элемента — ∅. Два множества называются равными, если они состоят из одних и тех же элементов, т.е. представляют собой одно и тоже множество. Множества не равны X ≠ Y, если в Х есть элементы, не принадлежащие Y, или в Y есть элементы, не принадлежащие Х. Символ равенства множеств обладает свойствами:

• Х=Х; — рефлексивность
• если Х=Y, Y=X — симметричность
• если X=Y,Y=Z, то X=Z — транзитивность.

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

Сравнение множеств

Множество содержится во множестве (множество включает множество ), если каждый элемент есть элемент :

В этом случае называется подмножеством , — надмножеством . Если и , то называется собственным подмножеством . Заметим, что . По определению .

Два множества называются равными, если они являются подмножествами друг друга:

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

Операции над множествами

Бинарные операции

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

• пересечение:

• объединение:

Если множества и не пересекаются,то . Их объединение обозначают также: .

• разность (дополнение):

• симметрическая разность:

• Декартово или прямое произведение:

Унарные операции

• Абсолютное дополнение:

Операция дополнения подразумевает некоторый универсум (универсальное множество , которое содержит ):

Относительным же дополнением называется А\В (см.выше):

• Мощность множества:

Результатом является кардинальное число (для конечных множеств — натуральное).

• Множество всех подмножеств (булеан):

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

Приоритет выполнения операций

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

Вопрос №8

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

Граф

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 2.15).

Рис. 2.15

Петля это дуга, начальная и конечная вершина которой совпадают.

Простой граф граф без кратных ребер и петель.

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

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

Граф отношения делимости

Построим граф, изображающий отношение делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на первое (рис. 2.16).

Рис. 2.16

ПОДГРАФЫ

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

Подграф, порожденный множеством вершин U это подграф, множество вершин которого - U, содержащий те и только те ребра, оба конца которых входят в U.

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Связность графа

Граф называется связным, если любая пара его вершин связана.
Связными компонентами графа называются подграфы данного графа, вершины которых связаны.

Деревья

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

Генеалогическое дерево

На рисунке 2.17 показано библейское генеалогическое дерево.

Рис. 2.17

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

Очевидно, что графический способ представления графов непригоден для ПК. Поэтому существуют другие способы представления графов.

В теории графов применяются

1. Матрица инцинденций. Это матриц