1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти


Название1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти
страница1/8
Дата публикации05.05.2013
Размер0.98 Mb.
ТипДокументы
userdocs.ru > Информатика > Документы
  1   2   3   4   5   6   7   8
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации.

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

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

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

Структурная схема одноканальной системы передачи инф!



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

Кодирующее устройство – кодер. Т.к алфавит сомволов<алфавита знаков, то каждому знаку соответствует комбинация символов (кодовая комбинация). Кодер преобразует непрерывный поток знаков в удобный поток символов. При этом 1 или несколько параметров выбр. носителя изменяют в соот. с перед. Инфой(модуляция). Модуляция осущ. модулятором.

Сигнал ->символ производится демодулятором.

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

Приемное устройство. Приемник выделяет сигнал из смеси сигнал+помеха. Мера соответствия принятого и посланного называют верностью передачи. Совокупность передающего и приемного устройства, линия связи – канал связи. Ист.сообщений + канал связи + получатель = ОДНОКАНАЛЬНАЯ система передачи информации

Помехи – любые мешающие возмущения, как внешние так и внутренние, вызывающие отклонение принятых от переданных. Эффект возд. Стараются учесть.

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

Сигнал – физический процесс, параметры которого способны отражать сообщения. !!!!!!!!!!!!!!!!!!!! понятие сигнал имеет неоднозначное толкование. В широком смысле слова под сигналом понимают материальный носительi.

физическая модель сигнала. Т – длительность сигнала = время существования сигнала.

ΔFc – ширина спектра сигнала = диапазон частот в которых сосредоточена основная энергия.

D – динамический диапазон = максимальной мгновенной мощности к минимальной, которая определяется мощностью помех: D=10×lg(9/Pn) Pmax, Pmin (Pmin≥Pn)

V – объем сигнала. V=TΔFcD

Важной характеристикой сигнала является база. Δ=TΔFc. Если δ≤1 – каналы называются узкоканальными. При δ > 1 – ширококанальные (сложные). Для моделирования детерминированных сигналов наиболее часто используются методы спектрального анализа, которые используют преобразование Фурье. Для случайных сигналов используются методы информационного и спектрального анализа, основанные на преобразовании Хинхи-Вепере, которые являются результатом распределения метода Фурье на случайные процессы.
^ 3. Понятия: источник сообщений, алфавит и объем источника сообщений, непрерывные и дискретные сообщения, кодирование в широком и узком смысле.

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

Информация поступает в систему в форме сообщений. Под сообщением понимают совокупность знаков или первичных сигналов, содержащих информацию. Источник сообщений в общем случае образует совокупность источника информации ИИ (исследуемого или наблюдаемого объекта) и первичного преобразователя ПП (датчика, человека-оператора и т.п). Различают дискретные и непрерывные сообщения. Дискретные сообщения формируются в результате последовательной выдачи источником отдельных элементов - знаков. Множество различных знаков называют алфавитом источника сообщений, а число знаков - объемом алфавита. В частности, знаками могут быть буквы естественного или искусственного языка, удовлетворяющие определенным правилам взаимосвязи. Распространенной разновидностью дискретных сообщений являются данные. Преобразование сообщения в сигнал, удобный для передачи по данному каналу связи, называют кодированием в широком смысле слова. Операцию восстановления сообщения по принятому сигналу называют декодированием. Для обеспечения простоты и надежности распознавания образцовых сигналов их число целесообразно сократить до минимума. Поэтому, как правило, прибегают к операции представления исходных знаков в другом алфавите с меньшим числом знаков, называемых символами. При обозначении этой операции используется тот же термин "кодирование", рассматриваемый в узком смысле. Устройство, выполняющее такую операцию, называют кодирующим или кодером.
^ 4. Информационные характеристики источников сообщений и каналов связи.

Характеристики источников:

-количество информациии в сообщении.

-избыточность сообщений

-энтропия

-производительность источнка сообщений

Характеристики каналов:

-скорость передачи

-пропускная способность
^ 5. Формула Хартли для количества информации источника дискретных сообщений. Энтропия источника дискретных сообщений (по К. Шениону).

Рассмотрим передачу дискретных сообщений. Имеется источник iс алфавитом А, который характеризуется объемом n (Хартли, 1928г) n–число символов в сообщении.

I=logN, (N=m) =>I=nlogmp=1\m, I=-nlogpIc = - logP -ФормулаХартлидля вероятности встречаемости символа в сообщении. а:ϵА =>вероятность встречаемости p(ai)

Ic = - logP(ai) - Формула Хартлидля конкретного символа (количества i) при разновероятностной встречаемости символов. Применив операцию усреднения по всему объему алфавита, получим среднее кол-во инфы, приходящиеся на один символ сообщения.

формула Шениона для энтропии источника дискретных сообщений. Энтропия рассматривается как мера неопреленностей поведений источника. Она обладает следующими свойствами: - длядискретных сообщений она вещественная величина (Real).

- для остальных сообщений она – вещественная, ограниченная, положительная, если с вероятностью 1(L)((непонятно как написано в конспекте)) всегда выбирается один и тот же символ.

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

Способ измерения кол-ва инфы, предложенный Шенионом является обобщенным способом Хартли, на случай появления неравновероятностных независимых символов.

Из-за корреляционных связей между символами и неравномерного их появления в реальных сообщениях, уменьшается кол-во инфы, которое переносит 1 символ. Количественно эти потери характеризуют коэффициент избыточности r: , где – максимальное значение кол-ва инфы, которое может переносить 1 символ и которое переносит 1 символ в реальных условиях. Для европейских языков избыточность сообщений r≥0.5
^ 6.Основные понятия теории сложности: массовая и индивидуальная задачи, алгоритм, входная длина индивидуальной задачи, временная сложность алгоритма.

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

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

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

Задача Р определяется:

1) общим списком всех параметров;

2) формулировкой свойств, которым должен удовлетворять ответ или решение задачи.

Индивидуальная задача I получается из массовой Р, если всем параметрам Р присвоить конкретное значение.

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

^ Входная длина индивидуальной задачи I из Р определяется как число символов в цепоч-ке, полученной применением к задаче I схемы кодирования для массовой задачи Р:

  1. I+lg n;

  2. k – полином степени k; (k+1)lg n;

  3. Матрица A(r x s), для любых Aij≤n, rs lg n.

В теории сложности есть 2 основных направления – определение сложности алгоритма и сравнение алгоритмов по сложности.

^ Временная сложность алгоритма – это функция, которая входной длине n ставит в соответствие максимальное время, затрачиваемое алгоритмом индивидуальных задач этой длины. Временная сложность отражает требующиеся для его работы затраты времени.
^ 8.Алгоритм деления с остатком.

Множество всех натуральных чисел 1,2,3… будем обозначать N. Множество всех целых чисел 0,±1,±2… - Z. a,b ϵZ и a≠0. Говорят, что а делит b: a/b если существует c=ab. Это отношение рефлексивно, транзитивно, но не симметрично. Есть свойства:

  1. a/b, a/c => a/(b±c);

  2. a/b => a/bc, cϵZ;

  3. a/b, b/a => a=±b.

Теорема: Пусть а – целое число и b – натуральное. Тогда существует такие однозначно определенные q и r ϵZ: 0≤ r≤ b, что a=bq+r. Доказательство:{возьмем наибольшее b/qa => r1+r1, 0≤r11)+r-r1 => (r-r1) кратно b; так как (r-r1)1)=0; т.к. r=r1 => q=q1. Теорема справедлива для любого b≠0 при условии, что r
^ 7.Полиноминальные и экспоненциальные алгоритмы. NP-полные и NP-трудные задачи.

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

^ Полиноминальным алгоритмом (или алгоритмом полиноминальной временной сложности) называется алгоритм, у которого временная сложность определяется на основании полиноминальной функции, где n – входная длина. Остальные алгоритмы экспоненциальные. Различие указанных типов алгоритмов становится особенно заметно при решении задач большого размера.

^ NP-полные и NP-трудные задачи (not proof): Принцип деления алгоритмов на экспоненциальные и полиноминальные является выявлением сложно решаемых задач. Полиноминальные задачи – «хорошие», но некоторые задачи целочисленного прог-ия невозможно решить такими «хорошими» алгоритмами. Экспоненциальные алгоритмы нельзя считать «хорошими». Большинство экспоненциальных алгоритмов – это варианты полного перебора, в то время как полиноминальные алгоритмы обычно сложно построить лишь тогда, когда удается более глубоко проникнуть в сущность задачи. Имеется известное соглашение о том, что задача не считается решенной до тех пор, пока для нее не получен полиноминальный алгоритм. Поэтому задача называется трудно решаемой, если для ее решения нет полиноминального алгоритма. Это одна из трактовок трудно решаемая задача. Различие между алгоритмами может иметь другой характер, когда размеры решаемой задачи невелики, известны экспоненциальные алгоритмы, которые зарекомендовали себя на практике хорошо.
^ 9.Наибольший общий делитель (НОД). Алгоритм Евклида для нахождения НОД.

Всякое целое, делящее 2 числа A и B называется их общим делителем. Наибольший из общих делителей для чисел А и В называется НОД. Ввиду конечного числа делителей данного числа существование и единственность НОД очевидны. Если НОД a и b =1, то a и b взаимнопростые. Найдем НОД для а и b:

Лемма 1: b/a  (a,b)=b {очевидно}.

Лемма 2: a=bq+r  (a,b)=(b,r).

Эти леммы лежат в основе алгоритма Евклида для нахождения НОД. Т.о. НОД – последний отличный от нуля остаток в алгоритме Евклида.

(175, 77)

175=77*2+21, 77=21*3+14, 21=14*1+7, 14=7*2 => r=7.
^ 10.Взаимно-простые числа. Наименьшее общее кратное (НОК).

Теорема (критерий взаимной простоты чисел): Два целых числа будут взаимно-простыми тода и только тогда, когда любой u и v, что au+bv=1. Доказательства: {Док-во вытекает из алг. Евклида. Необходимость:

rn-2=rn-1qn+rn

rn=rn-1qn+rn-2

rn-1=…

В итоге получаем линейное разложение НОД: d=au+bv.

Достаточность вытекает из свойств делимости: (a,b)/a, (a,b)/b  (a,b)/au+bv=1  (a,b)=1. }

Из доказанного критерия взаимной простоты вытекают следующие свойства:

  1. (a/b)=1, (a,c)=1  (a,b,c)=1;

  2. a/bc, (a,b)=1  a/c;

  3. a/c, b/c, (a,b)=1  ab/c.

НОК: Если a/M и b/M, то число MϵN называют общим кратным чисел a и b ϵ Z. НОК чисел a и b обозначается как [a,b]. Теорема 1: Если M – общее кратное чисел a и b, то НОК [a,b]/M. Доказательство: {Разделим с остатком M на [a,b]  M=[a,b]q+r. Ввиду того, что r=M-[a,b]q, имеем a[a,b]a/r, аналогично b/r. Поскольку 0≤r≤[a,b], то это возможно, только если r=0 }

Теорема 2: Справедливо следующее соотношение: [a,b]=ab/(a,b).
^ 12. Класс вычетов по модулю m. Понятие вычета. Привести примеры классов вычетов и вычетов по модулю m.

Если данное число m записано в десятичной системе счисления, то разделить его с остатком на 10 очень легко – остатком будет последняя цифра, а неполным частным – число, получающееся зачеркиванием последней цифры: 123456=10x12345+6

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

Число a называется сравнимым с числом b по модулю m, если разность a – b делится на m. Для сравнений по модулю m употребляется следующая запись: a≡b(mod m).

Можно дать другое определение сравнимости: a≡b(mod m), если a и b имеют одинаковые остатки при делении на m. Вычетом числа a по модулю m называется остаток от деления a на m.

Зафиксируем модуль m > 1. Все числа, сравнимые между собой по модулю m, можно объединить вместе. Такое множество называется классом вычетов по модулю m. Все числа в одном классе вычетов имеют один и тот же остаток при делении на m, а числа в разных классах имеют разные остатки. Выпишем для примера классы вычетов по модулю 5.

0, 5, 10, 15, 20, 25, 30, …

1, 6, 11, 16, 21, 26, 31, …

2, 7, 12, 17, 22, 27, 32, …

3, 8, 13, 18, 23, 28, 33, …

4, 9, 14, 19, 24, 29, 34, …

Классы вычетов по модулю m представляют собой арифметические прогрессии с разностью m. Классы удобно дополнить отрицательными целыми числами. Например, в класс чисел по модулю 5, сравнимых с числом 4, попадут такие числа: …, –11, –6, –1, 4, 9, 14, …
  1   2   3   4   5   6   7   8

Похожие:

1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconИнформация. Понятие информации. Формирование информации (схема)....
В информатике под информацией понимается сообщение, снижающее степень неопределенности знаний о состоянии предметов или явлений и...
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconНачальник кафедры Уиит полковник полиции
Актуальность защиты информации. Понятие информации, информационной сферы, безопасности информации. Автоматизированные системы обработки...
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconМатериал для подготовки
Понятие информации. Виды информации. Роль информации в живой природе и в жизни людей
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconЭкзаменационные вопросы по курсу
Понятие информации. Свойства, виды и формы информации. Единицы измерения информации
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconЛекция 3 Понятие информации, измерение информации
...
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconВопросы к зачёту по дисциплине «Медицинская информатика» для студентов 1 курса
История информатики. Медицинская информатика. Понятие информации. Основные свойства информации. Виды информации. Виды медицинской...
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconДля гос экзамена по курсу «Базы данных» 2011 год
Понятие экономической информации. Требования, предъявляемые к экономической информации. Виды экономической информации
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconТема Понятие информации
Основы защиты информации и сведений, составляющих государственную тайну; методы защиты информации
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти icon!!!Сообщения, данные, сигнал, атрибутивные свойства информации, показатели...
Информацию рассматривают с точки зрения ее практической полезности для получателя
1. Понятие теории информации. Формирование теории информации как науки и ее значение для общественного развития. Понятие информации. Теория информации. Ти iconПонятие «информация», откуда возникает, с чем связано, меры информации?
Эволюция информационных технологий в зависимости от развития процессов хранения, транспортирования и обработки информации
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2015
контакты
userdocs.ru
Главная страница