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

      ЧОУ ВПО Институт экономики, управление и права (г. Казань) 
 
                                             Юридический факультет 
 
 
 
 
                                
 
                                                                                                                 Рамазанов Айрат 
                                                                                                                           Марселевич 
                                                                                           1 курс заочного отделения  
                                                                                            юридического факультета 
                                                                                                                                    гр. 221-з 
 
 
 
 
                                                         Контрольная работа 
                  по дисциплине «Информатика и математика» 
                                      за 1 семестр 2012/2013 уч. года  
 
 
 
 
 
 
 
 
 
 
 
 
 
ул. Пр. Победы, д.124, кв. 3 «а», 
420100, 
+79510616888 
 
 
 
 
 
 
 
 
1. Информатика — молодая научная дисциплина, изучающая вопросы, связанные с поиском, сбором, хранением, преобразованием и использованием информации в самых различных сферах человеческой деятельности. Она включает дисциплины, относящиеся к обработке информации в вычислительных машинах и вычислительных сетях: как абстрактные, вроде анализа алгоритмов, так и довольно конкретные, например, разработка языков программирования.  
        Темами исследований в информатике являются вопросы:  что можно, а что нельзя реализовать в программах и базах данных (теория вычислимости искусственный интеллект), каким образом можно решать специфические вычислительные и информационные задачи с максимальной эффективностью (теория сложности вычислений), в каком виде следует хранить и восстанавливать информацию специфического вида (структуры и базы данных), как программы и люди должны взаимодействовать друг с другом (пользовательский интерфейс и языки программирования и представление знаний), и т. п. 
 
2. Информация — сведения о чем-либо, независимо от формы их представления.  
        Информацию можно разделить на виды по различным критериям: 
       по способу восприятия: 
Визуальная — воспринимаемая органами зрения. 
Аудиальная — воспринимаемая органами слуха. 
Тактильная — воспринимаемая тактильными рецепторами. 
Обонятельная — воспринимаемая обонятельными рецепторами. 
Вкусовая — воспринимаемая вкусовыми рецепторами. 
       по форме представления: 
Текстовая — передаваемая в виде символов, предназначенных обозначать лексемы языка. 
Числовая — в виде цифр и знаков, обозначающих математические действия. 
Графическая — в виде изображений, предметов, графиков. 
Звуковая — устная или в виде записи и передачи лексем языка аудиальным путём. 
      по назначению: 
Массовая — содержит тривиальные сведения и оперирует набором понятий, понятным большей части социума. 
Специальная — содержит специфический набор понятий, при использовании происходит передача сведений, которые могут быть не понятны основной массе социума, но необходимы и понятны в рамках узкой социальной группы, где используется данная информация. 
Секретная — передаваемая узкому кругу лиц и по закрытым (защищённым) каналам. 
Личная (приватная) — набор сведений о какой-либо личности, определяющий социальное положение и типы социальных взаимодействий внутри популяции. 
       по значению: 
Актуальная — информация, ценная в данный момент времени. 
Достоверная — информация, полученная без искажений. 
Понятная — информация, выраженная на языке, понятном тому, кому она предназначена. 
Полная — информация, достаточная для принятия правильного решения или понимания. 
Полезная — полезность информации определяется субъектом, получившим информацию в зависимости от объёма возможностей её использования. 
       по истинности: 
Истинная 
Ложная 
 
3. Хранение информации осуществляется с помощью её переноса на некоторые материальные носители. Семантическая информация, зафиксированная на материальном носителе для хранения, называется документом. 
        Хранить информацию человечество научилось очень давно. В наиболее древних формах хранения информации использовалось расположение предметов — раковин и камней на песке, узелков на верёвке. Существенным развитием этих способов явилась письменность — графическое изображение символов на камне, глине, папирусе, бумаге. Огромное значение в развитии этого направления имело изобретение книгопечатания. За свою историю человечество накопило огромный объём информации в библиотеках, архивах, периодических изданиях и других письменных документах. 
        В настоящее время особое значение получило хранение информации в виде последовательностей двоичных символов. Для реализации этих методов используются разнообразные запоминающие устройства. Они являются центральным звеном систем хранения информации. Кроме них в таких системах используются средства поиска информации (поисковая система), средства получения справок (информационно-справочные системы) и средства отображения информации (устройство вывода). Сформированные по назначению информации такие информационные системы образуют базы данных, банки данных и базы знаний. 
         Передачей семантической информации называется процесс её пространственного переноса от источника к получателю (адресату). Передавать и получать информацию человек научился даже раньше, чем хранить её. Речь является способом передачи, который использовали наши далекие предки в непосредственном контакте (разговоре) — ею мы пользуемся и сейчас. Для передачи информации на большие расстояния необходимо использовать значительно более сложные информационные процессы. 
         Для осуществления такого процесса информация должна быть некоторым образом оформлена (представлена). Для представления информации используются различные знаковые системы — наборы заранее оговоренных смысловых символов: предметов, картинок, написанных или напечатанных слов естественного языка. Представленная с их помощью семантическая информация о каком-либо объекте, явлении или процессе называется сообщением. 
         Очевидно, что для передачи сообщения на расстояние информация должна быть перенесена на какой-либо мобильный носитель. Носители могут перемещаться в пространстве с помощью транспортных средств, как это происходит с письмами, посылаемыми по почте. Такой способ обеспечивает полную достоверность передачи информации, поскольку адресат получает оригинал сообщения, однако требует значительного времени для передачи. С середины девятнадцатого века получили распространение способы передачи информации, использующие естественно распространяющийся носитель информации — электромагнитные колебания (электрические колебания, радиоволны, свет). Реализация этих способов требует: 
        предварительного переноса информации, содержащейся в сообщении, на носитель — кодирования; 
        обеспечения передачи  полученного таким образом  сигнала адресату по специальному каналу связи; 
        обратного преобразования кода сигнала в код сообщения —  декодирования. 
 
        Использование электромагнитных носителей делает доставку сообщения адресату почти мгновенной, однако требует дополнительных мер по обеспечению качества (достоверности и точности) передаваемой информации, поскольку реальные каналы связи подвержены воздействию естественных и искусственных помех. 
         Устройства, реализующие процесс передачи данных, образуют системы связи. В зависимости от способа представления информации системы связи можно подразделять на знаковые (телеграф, телефакс),звуковые (телефон), видео и комбинированные системы (телевидение). Наиболее развитой системой связи в наше время является интернет.  
 
4. Как и всякий объект, информация обладает свойствами. Характерной отличительной особенностью информации от других объектов природы и общества, является дуализм: на свойства информации влияют как свойства исходных данных, составляющих ее содержательную часть, так и свойства методов, фиксирующих эту информацию. 
С точки зрения информатики наиболее важными представляются следующие общие качественные свойства:  
Объективность информации. Объективный – существующий вне и независимо от человеческого сознания. Информация – это отражение внешнего объективного мира. Информация объективна, если она не зависит от методов ее фиксации, чьего-либо мнения, суждения. 
Пример. Сообщение «На улице тепло» несет субъективную информацию, а сообщение «На улице 22°С» – объективную, но с точностью, зависящей от погрешности средства измерения. 
Объективную информацию можно получить с помощью исправных датчиков, измерительных приборов. Отражаясь в сознании человека, информация может искажаться (в большей или меньшей степени) в зависимости от мнения, суждения, опыта, знаний конкретного субъекта, и, таким образом, перестать быть объективной. 
Достоверность информации. Информация достоверна, если она отражает истинное положение дел. Объективная информация всегда достоверна, но достоверная информация может быть как объективной, так и субъективной. Достоверная информация помогает принять нам правильное решение. Недостоверной информация может быть по следующим причинам: преднамеренное искажение (дезинформация) или непреднамеренное искажение субъективного свойства; искажение в результате воздействия помех («испорченный телефон») и недостаточно точных средств ее фиксации. 
Полнота информации. Информацию можно назвать полной, если ее достаточно для понимания и принятия решений. Неполная информация может привести к ошибочному выводу или решению. 
Точность информации определяется степенью ее близости к реальному состоянию объекта, процесса, явления и т. п. 
Актуальность информации – важность для настоящего времени, злободневность, насущность. Только вовремя полученная информация может быть полезна. 
Полезность (ценность) информации. Полезность может быть оценена применительно к нуждам конкретных ее потребителей и оценивается по тем задачам, которые можно решить с ее помощью. 
 
5. Количество информации – в теории информации это количество информации в одном случайном объекте относительно другого. Пусть и – случайные величины, заданные на соответствующих множествах и . Тогда количество информации относительно есть:

,

где

, — энтропия, а

, — условная энтропия, в теории  передачи информации она характеризует  шум в канале. 
 
Свойства количества информации. 
Для количества информации справедливы свойства:

как следствие теоремы Байеса.

если  и – независимые случайные величины.

Последнее свойство показывает, что количество информации совпадает с энтропией, если компонента потери информации (шум) равна нулю. 
 
Формула Хартли определяет количество информации, содержащееся в сообщении длины n. 
 
Имеется алфавит А, из букв которого составляется сообщение:

Количество  возможных вариантов разных сообщений:

где N — возможное количество различных сообщений, шт; m — количество букв в алфавите, шт; n — количество букв в сообщении, шт.

Пример: Алфавит состоит  из двух букв «B» и «X», длина сообщения 3 буквы — таким образом, m=2, n=3. При выбранных нами алфавите и длине сообщения можно составить разных сообщений «BBB», «BBX», «BXB», «BXX», «XBB», «XBX», «XXB», «XXX» — других вариантов нет.

Формула Хартли определяется:

где I — количество информации, бит.

При равновероятности символов формула Хартли переходит в собственную информацию.

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

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

Поэтому функция  энтропии должна удовлетворять условиям:

1. определена и непрерывна для всех , где для всех и . (Нетрудно видеть, что эта функция зависит только от распределения вероятностей, но не от алфавита.)
2. Для целых положительных , должно выполняться следующее неравенство:

3. Для целых положительных  , где , должно выполняться равенство:

Шеннон показал, что единственная функция, удовлетворяющая  этим требованиям, имеет вид:

где  — константа (и в действительности нужна только для выбора единиц измерения).

Шеннон определил, что  измерение энтропии ( ), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т. д.

Определение энтропии Шеннона  связано с понятием термодинамической  энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии. 
 
6. Система счисления —символический метод записи чисел, представление чисел с помощью письменных знаков.

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

Системы счисления подразделяются на позиционные, непозиционные и смешанные. 
 
В позиционных системах счисления один и тот же числовой знак (цифра)в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у мусульман. 
Под позиционной системой счисления обычно понимается -ричная система счисления, которая определяется целым числом , называемым основанием системы счисления. Целое число без знака в -ричной системе счисления представляется в виде конечной линейной комбинации степеней числа :

, где   — это целые числа, называемые цифрами, удовлетворяющие неравенству .

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

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

Наиболее употребляемыми в настоящее время позиционными системами являются: 
1— единичная 
2 — двоичная 
8 — восьмеричная 
10 — десятичная 
12 —двенадцатеричная 
13 —тринадцатеричная 
16 —шестнадцатеричная 
60 — шестидесятеричная

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

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

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

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

Наиболее  известным примером смешанной системы  счисления является представление  времени в виде количества суток, часов, минут и секунд. При этом величина « дней, часов, минут, секунд» соответствует значению секунд.

В непозиционных  системах счисления величина, которую обозначает цифра, не зависит от положения в числе. При этом система может накладывать ограничения на положение цифр, например, чтобы они были расположены в порядке убывания. 
 
Двоичная система счисления — позиционная система счисления с основанием 2 
В этой системе счисления числа записываются с помощью двух символов (0 и 1). 
 
7.  Теория множеств — раздел математики, в котором изучаются общие свойства множеств. Теория множеств лежит в основе большинства математических дисциплин; она оказала глубокое влияние на понимание предмета самой математики.  
В основе теории множеств лежат первичные понятия: множество и отношение быть элементом множества (обозначается как — «x есть элемент множества A», «x принадлежит множеству A»). Среди производных понятий наиболее важны следующие: 
пустое множество , обычно обозначается символом ; 
подмножество и надмножество  
семейство множеств 
пространство(универсум) 
конституента 
 
Диаграмма Венна — схематичное изображение всех возможных пересечений нескольких (часто — трёх) множеств. Если пересечения позволяется указывать не все, получается более общий случай — круги Эйлера. 
Диаграммы Эйлера — Венна (как их ещё называют) изображают все комбинаций свойств, то есть конечную булеву алгебру. При диаграмма Эйлера — Венна обычно изображается в виде трёх кругов с центрами в вершинах равностороннего треугольника и одинаковым радиусом, приблизительно равным длине стороны треугольника. 
Они появились в сочинениях английского логика Джона Венна(1834—1923), подробно изложившего их в книге «Символическая логика», изданной в Лондоне в 1881 году. 
 
8. Комбинаторика (Комбинаторный анализ) — раздел математики , изучающий дискретные объекты, множества и отношения на них. Комбинаторика связана со многими другими областями математики —алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике). 
Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». 
Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов. 
 
Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций. Примеры комбинаторных конфигураций:

Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества. 
Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n. 
Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений. 
Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел. 
Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел. 
 
Разделы комбинаторики:

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

 
9. Алгоритм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система. 
Виды алгоритмов. Особую роль выполняют прикладные алгоритмы, предназначенные для решения определённых прикладных задач. Алгоритм считается правильным, если он отвечает требованиям задачи (например, даёт физически правдоподобный результат). Алгоритм (программа) содержит ошибки, если для некоторых исходных данных он даёт неправильные результаты, сбои, отказы или не даёт никаких результатов вообще. Последний тезис используется  в олимпиадах по алгоритмическому программированию, чтобы оценить составленные участниками программы.