Информационные процессы и системы

Понятия информации

Информация (от лат. informatio, разъяснение, изложение, осведомленность) — сведения о чем-либо независимо от формы их представления.

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

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

В теории управления

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

В информатике

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

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

В информатике

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

Формы отражения Информации:

· Сознание

· Психика

· Раздражимость

· Запечатление взаимодействия

Основные функции в обществе:

· Познавательная

· Коммуникативная

· Управленческая

Компоненты информации

 

Сигнал (от лат. Signum - знак) — физический процесс(явление), несущий сообщение (информацию) о событии.

Информационные процессы и системы

Информационный процесс- последовательность действий, выполняемых информацией. Системы, реализующие информационные процессы, называют информационными системами.

Основные этапы обращения информации в системах:

· Сбор информации;

· Подготовка (преобразование);

· Передача;

· Обработка;

· Хранение;

· Отображение (воспроизведение, интерпретация).

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

Информационные ресурсы и технологии

Информационные ресурсы- отдельные документы и отдельные массивы документов в информационных системах.

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

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

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

Информация и кибернетика

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

Управление и информация – основные понятия кибернетики. Понятие введено Анри Ампером в19в, как искусство управления людьми и обществом.

Н. Винер «Кибернетика или управление и связь в животном и машине» 1948 г.

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

Основные законы управления:

· Всякое управление есть целенаправленный процесс;

· Всякое управление есть информационный процесс;

· Всякое управление осуществляется в замкнутом контуре.

Определение мехатроника

Современный термин " Мехатроника" (" Mechatronics" ), согласно японским источникам [5], был введен фирмой Yaskawa Electric в 1969 году и зарегистрирован как торговая марка в 1972 году. Это название получено комбинацией слов " МЕХАника" и " ЭлекТРОНИКА". Объединение этих понятий в едином словосочетании означает интеграцию знаний всоответствующих областях науки и техники, которая позволила совершить качественный скачок в создании техники новых поколений и производстве новейших видов систем и оборудования. Аналогичным образом шло развитие электромеханики как науки, использующей достижения электротехники и механики при создании приводных исполнительных систем широкого назначения. Интеграция электромеханики и микроэлектроники привела к появлению комплектных интегрированных мехатронных модулей движения рабочих органов и узлов машин а также создаваемого на их основе оборудования. Именно в этом направлении наиболее активно развивалась мехатроника в нашей стране.

По определению ГОС:

" Мехатpоника - это новая область науки и техники, посвященная созданию и эксплуатации машин и систем с компьютеpным упpавлением движением, котоpая базиpуется на знаниях в области механики, электpоники и микpопpоцессоpной техники, инфоpматики и компьютеpного упpавления движением машин и агpегатов".

 

Уровни изучения сообщений

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

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

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

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

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

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

Меры информации

1. Меры информации синтаксического уровня

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

В двоичной системе счисления один разряд имеет вес, равный 2, и соответственно единицей измерения информации будет бит (bit - binary digit - двоичный разряд). В этом случае сообщение в виде n-разрядного числа имеет объем данных V_a = nбит. Например, восьмиразрядный двоичный код 11001011 имеет объем данных V_a = 8 бит.

1 кбайт = 1024 байт = 2¹⁰ байт;

1 Мбайт = 1024 кбайт =2²⁰ байт = 1 048 576 байт;

1 Гбайт =1024 Мбайт = 2³⁰ байт = 1 073 741 824 байт;

1 Тбайт = 1024 Гбайт =2⁴⁰ байт = 1 099 511 627 776 байт.

Количество информации I (энтропийный подход). В теории информации и кодирования принят энтропийный подход к измерению информации.

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

I = Hapr – Haps, где

Hapr- априорная энтропия о состоянии исследуемой системы или про­цесса;

Haps- апостериорная энтропия.

Апостериори (от лат. a posteriori — из последующего) — проис­ходящее из опыта (испытания, измерения).

Априори (от лат. a priori — из предшествующего) — понятие, ха­рактеризующее знание, предшествующее опыту (испытанию), и независимое от него.

Мера энтропии - H(A) = log N, где N- число возможных состояний источника.

Мера была предложена американским ученым Р. Хартли в 1928 г. Основание логарифма в формуле не имеет принципиального значения и определяет только масштаб или единицу измерения. В зависимости от основания логарифма применяют следующие единицы измерения:

1. Биты — при этом основание логарифма равно 2: Н(А) = log2 N .
2. Наты — при этом основание логарифма равно e: Н(А) = ln N .
3. Диты — при этом основание логарифма равно 10: Н(А) = lg N .

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

Избыточность алфавита сообщений

D= [Hmax (A)– H(A) ]/[Hmax (A)]

Качество информации

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

 

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

Значимость информации – свойство информации сохранять ценность для потребителя с течением времени.

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

Δ t1—продолжительностью времени, в течение которого оцениваемая информация полностью сохраняет свою идентичность; Δ t2— продолжительностью времени, в течение которого идентичность информации падает, но не более чем на одну четверть; Δ t3— продолжительностью времени, в течение которго идентичность информации падает наполовину; Δ t4— продолжительностью времени, в течение которого идентичность информации падает на три четверти.

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

 

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

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

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

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

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

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

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

Основными показателями сохранности являются целостность и готовность информации.

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

Готовность информации характеризуется степенью работоспособности ИМ при выполнении целевых и функциональных задач системы.

Виды и формы информации

 

 

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

· в виде одного сигнала — например, электрического напряжения, которое сравнимо с величиной X (аналогично ей). Например, при X - 2003 единицам на вход вычислительного устройства можно подать напряжение 2, 003 В (масштаб представления 0, 001 В /ед.) или 10, 015 В (масштаб представления 0, 005 В /ед.);

· в виде нескольких сигналов — нескольких импульсов напряжений, которые сравнимы с числом единиц в X, числом де­сятков в X, числом сотен в X и т. д. (например, при X, равном 1995 единицам, на вход вычислительного устройства можно подать четыре импульса напряжением 1 В, 9 В и 5 В).

Первая форма представления информации (с помощью сходной величины — аналога) называется аналоговой, или непрерывной.

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

Лекция 3

Представление информации в цифровых автоматах

Системы счисления

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

Все системы счисления можно разделить на позиционные и непозиционные.

Непозиционная система счисления система, в которой символы, обозначающие то или иное количество, не меняют своего значения в зависимости от местоположения (позиции) в изоб­ражении числа.

 

Запись числа А в непозиционной системе счисления D может быть представлена выражением:

 

Двоично-десятичная система

В двоично-десятичной системе десятичные цифры от 0 до 9 представляют 4-разрядными двоичными комбинациями от 0000 до 1001, т. е. двоичными эквивалентами десяти первых шестнадцатеричных цифр

Две двоично-десятичные цифры составляют 1 байт. Таким образом, с помощью 1 байта можно представлять значения от 0 до 99, а не от 0 до 255, как при использовании 8-разрядного двоичного числа.

(1001 0101 0011 1000)₂ = (38200)₁₀

Лекция

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

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

Своим существованием наука «алгебра логики» обязана английскому математику Джорджу Булю, который исследовал логику высказываний (1854г.). Первый в России курс по алгебре логики был прочитан П. С. Порецким в Казанском государственном университете.

Логическое высказывание — упрощение термина «Суждение» из формальной логики, используется в математической логике. Высказыванием является повествовательное предложение, которое формализует некоторое выражение мысли. Это утверждение, которому всегда можно поставить в соответствие одно из двух логических значений: ложь (0, ложно, false) или истина (1, истинно, true). Логическое высказывание принято обозначать заглавными латинскими буквами.

Высказывательной формой называется логическое высказывание, в котором один из объектов заменён переменной. При подстановке вместо переменной какого-либо значения высказывательная форма превращается в высказывание. Пример: A(x) = «В городе x идет дождь.» A — высказывательная форма, x — объект.

Высказывание обычно имеет только одно логическое значение. Так, например, «Париж — столица Франции» — высказывание, а «На улице идет дождь» — не высказывание. Аналогично, «5> 3» — высказывание, а «2+3» — не высказывание. Как правило, высказывания обозначают маленькими латинскими буквами.

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

, где B — непустое множество, над элементами которого определены три операции:

- отрицание (унарная операция),

- конъюнкция (бинарная),

- дизъюнкция (бинарная),

а также константы — логический ноль 0 и логическая единица 1.

Дизъю́ нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например ). Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например ).

Аксиомы алгебры логики

Аксиомы:

1) Дизъюнкция двух переменных равна 1, если хотябы одна переменная равна 1

0+0=0

0+1=1

1+0=1

1+1=1

2) Конъюнкция двух переменных равна 0, если хотя бы одна переменная равна 0

0 ∙ 0=0

0 ∙ 1=0

1 ∙ 0=0

1 ∙ 1=1

3) Инверсия

Законы алгебры логики

1. Законы однопарных элементов

Универсального множества

· X+1=1

· X ∙ 1=X

нулевого множества

· X+0=X

· X ∙ 0=0

2. Законы отрицания

 

 

Комбинационные законы

 

 

 

Понятие алгоритма

Алгори́ тм, от имени учёного аль-Хорезми (перс. خ و ا ر ز م ی ‎ [al-Khwā razmī ]) — точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Ранее часто писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место (например, Нормальный алгорифм Маркова).

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

Единого «истинного» определения понятия «алгоритм» нет.

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)

«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)

«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)

«Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)

«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)

 

Виды алгоритмов

Прикладные алгоритмы, предназначенные для решения определённых прикладных задач.

int factorial(int n)

{ int result = 1;

for ( int i = 2; i < = n; i++ ) { result *= i; }

return result;

}

Рекурсивные алгоритмы

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

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

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

int factorial(int n) {

if ( n < = 1 ) {

return 1;

}

return n * factorial(n - 1);

}

Формы описания алгоритмов

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

Блок-схемы:

ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.

Для программной документации (устарели, заменяются ГОСТ 19.701-90):

• ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения.

• ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные графические.

Формы описания алгоритмов

Алан Тьюринг высказал предположение (известное как Тезис Чёрча — Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.

В настоящее время теория алгоритмов развивается, главным образом, по трем направлениям.

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

· Теория асимптотического анализа алгоритмов рассматривает методы получения асимптотических оценок ресурсоемкости или времени выполнения алгоритмов, в частности, для рекурсивных алгоритмов. Асимптотический анализ позволяет оценить рост потребности алгоритма в ресурсах (например, времени выполнения) с увеличением объема входных данных.

Теория практического анализа вычислительных алгоритмов решает задачи получения явных функции трудоёмкости, интервального анализа функций, поиска практических критериев качества алгоритмов, разработки методики выбора рациональных алгоритмов

 

 

Блок-схемы

 

Формы описания алгоритмов

Маши́ на Тью́ ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

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

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

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

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Норма́ льный алгори́ тм Ма́ ркова (НАМ) — один из стандартных способов формального определения понятия алгоритма, так же как и машина Тьюринга. Понятие нормального алгоритма введено А.А. Марковым в конце 1940-х годов. Традиционно, когда говорят об алгоритмах Маркова, используют слово " алгорифм".

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

Использование алгоритма Маркова для преобразований над строками:

Правила:

1. «А» → «апельсин»
2. «кг» → «килограмм»
3. «М» → «магазинчике»
4. «Т» → «том»
5. «магазинчике» → • «ларьке» (заключительная формула)
6. «в том ларьке» → «на том рынке»

 

Исходная строка:

«Я купил кг Аов в Т М.»

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

1. «Я купил кг апельсинов в Т М.»
2. «Я купил килограмм апельсинов в Т М.»
3. «Я купил килограмм апельсинов в Т магазинчике.»
4. «Я купил килограмм апельсинов в том магазинчике.»
5. «Я купил килограмм апельсинов в том ларьке.»

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

Лекция

Виды алгоритмов

Комбинаторные алгоритмы

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

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

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

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

Перестановкой из n элементов (например чисел 1, 2, …, n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.

Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

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

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

Алгоритмы на графах

Тео́ рия гра́ фов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V, E), где V есть подмножество любого счётного множества, а E — подмножество V× V.

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

Алгоритмы поиска

Алгоритмы на строках

Алгоритмы сортировки

Например, «Сортировка пузырьком»

Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n-1], A[n]

t: = истина

цикл пока t:

t: = ложь

цикл для j = 1, 2, ..., n − 1:

если A[j] > A[j+1], то:

обменять местами элементы A[j] и A[j+1]

t: = истина

Алгоритмы слияния

Алгоритмы сжатия данных

Алгоритмы сжатия без потерь

Семейство алгоритмов словарного сжатия Лемпеля — Зива

Deflate — это алгоритм сжатия без потерь, который использует комбинацию алгоритма LZ77 и алгоритма Хаффмана. Изначально он был описан Филом Кацом для 2-й версии своей утилиты для создания архивов PKZIP, который впоследствии был определён в RFC 1951 (http: //tools.ietf.org/html/rfc1951).

Алгоритмы сжатия с потерями

Вычислительная геометрия

Триангуляция

Диаграмма Вороного

Локализация точки (англ.)

Пересечения

Компьютерная графика

Компьютерное зрение

Криптографические алгоритмы

Шифрование с симметричным (скрытым) ключом:

· ГОСТ 28147-89

· AES (англ. Advanced Encryption Standard) — победитель соревнования NIST, также известен как Rijndael

· Blowfish

· DES (англ. Data Encryption Standard) — иногда, алгоритм DEA (англ. Data Encryption Algorithm), победитель соревнования NBS, заменён на AES для большинства применений

· RC2

· IDEA (англ. International Data Encryption Algorithm)

· RC4

Асимметричное шифрование (с публичным ключом)

· RSA

Цифровая обработка сигналов

Цифрова́ я обрабо́ тка сигна́ лов (ЦОС, DSP - англ. digital signal processing) — преобразование сигналов, представленных в цифровой форме.

Линейная фильтрация — селекция сигнала в частотной области; синтез фильтров, согласованных с сигналами; частотное разделение каналов; цифровые преобразователи Гильберта и дифференциаторы; корректоры характеристик каналов

Спектральный анализ — обработка речевых, звуковых, сейсмических, гидроакустических сигналов; распознавание образов

12345678910Следующая ⇒

Поделиться: