Лекции.Орг
 

Категории:


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


Электрогитара Fender: Эти статьи описывают создание цельнокорпусной, частично-полой и полой электрогитар...


Расположение электрооборудования электропоезда ЭД4М

В15. Скриптовые языки программирования (Java, Perl, HTML, XML). Инструментальные средства создания web-серверов и web-сайтов (PHP, ASP NET, Delphi). Основы web-дизайна.



Сцена́рный язы́к или скри́птовый язы́к (англ. scripting language, в русской литературе принято название язык сценариев) — высокоуровневый язык программирования для написания сценариев — кратких описаний выполняемых системой действий. Разница между программами и сценариями довольно размыта. Сценарий — это программа, имеющая дело с готовыми программными компонентами.

Согласно Джону Устерхауту, автору языка Tcl, высокоуровневые языки можно разделить на языки системного программирования (англ. system programming languages) и сценарные языки(англ. scripting languages). Последние он также назвал склеивающими языками(англ. glue languages) или языками системной интеграции(англ. system integration languages). Сценарии обычно интерпретируются, а не компилируются, хотя сценарные языки программирования один за другим обзаводятся JIT-компиляторами.

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

JavaScript

JavaScript - это язык программирования от компании Netscape, который является реализацией стандарта ECMAScript.

В большинстве случаев при упоминании JavaScript подразумевается так называемый клиентский JavaScript, интерпретатор которого встроен в Web-браузеры. Однако JavaScript изначально был разработан как универсальный язык программирования для встраивания в любое приложение и обеспечения возможности написания в нем сценариев. Например, ActionScript, язык сценариев, доступный в Macromedia Flash 5 и MX, также смоделирован в соответствии со стандартом ECMAScript.

Интерпретатор JavaScript от Netscape был выпущен в виде открытого исходного кода и доступен через организацию Mozilla (http://www.mozilla.org/js/). Mozilla предоставляет две различные версии интерпретатора JavaScript - "SpiderMonkey" (написана на С) и "Rhino" (написана на Java).

Perl — интерпретируемый скриптовый язык программирования, один из самых распространённых в области веб-программирования. По одной из версий, Perl — аббревиатура, которая расшифровывается как "Practical Extraction and Report Language" (практический язык извлечений и отчётов).

Основной особенностью языка считаются его богатые возможности для работы с текстом, реализованные при помощи регулярных выражений (regular expressions). Перл также знаменит огромной коллекцией дополнительных модулей CPAN, находящейся по адресу http://www.cpan.org/.

eXtensible Markup Language (XML, расширяемый язык разметки) — метаязык разметки, очень похож на HTML, с возможностью добавлять свои собственные теги, на котором пишутся специализированные языки разметки (XML-приложения), описывающие данные определенной предметной области и структуры.

HTML (Hypertext Markup Language) - язык разметки гипертекста.

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

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

Разметка - вставка в текст дополнительных служебных символов.

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

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

Web-сервер и Web-сайт

Информация, доступная пользователям Internet, располагается на компьютерах (Web-серверах), на которых установлено специальное программное обеспечение. Значительная часть этой информации организованна в виде Web-сайтов. Каждый из них имеет свое имя (адрес) в Internet. Web-сайт - это информация, представленная в определенном виде, которая располагается на Web-сервере и имеет свое имя (адрес). Для просмотра Web-сайтов на компьютере пользователя используются специальные программы, которые называются браузерами. Наиболее распространенными браузерами в настоящее время являются InternetExplorer и NetscapeNavigator. В зависимости от того, какое имя (адрес) сайта мы зададим в строке "Адрес", браузер будет загружать в свое окно соответствующую информацию.

Web-сайт состоит из связанных между собой Web-страниц. Web-страница представляет собой текстовый файл с расширением *.htm, который содержит текстовую информацию и специальные команды - HTML-коды, определяющие в каком виде эта информация будет отображаться в окне браузера. Вся графическая, аудио- и видео информация непосредственно в Web-страницу не входит и представляет собой отдельные файлы с расширениями *.gif, *.jpg (графика), *.mid, *.mp3 (звук), *.avi (видео). В HTML-коде страницы содержатся только указания на такие файлы (рис. 1.1).

Web-страницы можно создавать вручную с помощью языка HTML (HyperText Mark-up Language - язык разметки гипертекста), при этом ввод HTML-кода выполняется в любом текстовом редакторе или с помощью HTML-редакторов.

Наиболее известные редакторы Web-страниц DreameWeaver, NetscapeComposer, HotDog, Word97 и последующие версии, а также MicrosoftFrontPage, который мы и будем изучать.

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

PHP (англ. PHP: Hypertext Preprocessor — «PHP: препроцессор гипертекста»; первоначально Personal Home Page Tools[3] — «Инструменты для создания персональных веб-страниц») — скриптовый язык программирования общего назначения, интенсивно применяемый для разработки веб-приложений. В настоящее время поддерживается подавляющим большинством хостинг-провайдеров и является одним из лидеров среди языков программирования, применяющихся для создания динамических веб-сайтов.

Язык и его интерпретатор разрабатываются группой энтузиастов в рамках проекта с открытым кодом. Проект распространяется под собственной лицензией.

В области программирования для сети Интернет PHP — один из популярных скриптовых языков (наряду с JSP, Perl и языками, используемыми в ASP.NET) благодаря своей простоте, скорости выполнения, богатой функциональности, кроссплатформенности и распространению исходных кодов на основе лицензии PHP.

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

· автоматическое извлечение POST и GET-параметров, а также переменных окружения веб-сервера в предопределённые массивы;

· взаимодействие с большим количеством различных систем управления базами данных (MySQL, MySQLi, SQLite, PostgreSQL, Oracle (OCI8), Oracle, Microsoft SQL Server, Sybase, ODBC, mSQL, IBM DB2, Cloudscape и Apache Derby, Informix, Ovrimos SQL, Lotus Notes, DB++, DBM, dBase, DBX, FrontBase, FilePro, Ingres II, SESAM, Firebird / InterBase, Paradox File Access, MaxDB, Интерфейс PDO);

· автоматизированная отправка HTTP-заголовков;

· работа с HTTP-авторизацией;

· работа с cookies и сессиями;

· работа с локальными и удалёнными файлами, сокетами;

· обработка файлов, загружаемых на сервер;

· работа с XForms.

Delphi (Де́лфи, произносится /ˈdɛlˌfi:/[1]) — императивный, структурированный, объектно-ориентированный язык программирования, диалект Object Pascal[2]. Начиная со среды разработки Delphi 7.0, в официальных документах Borland стала использовать название Delphi для обозначения языка Object Pascal. Начиная с 2007 года уже язык Delphi (производный от Object Pascal) начал жить своей самостоятельной жизнью и претерпевал различные изменения, связанные с современными тенденциями (например, с развитием платформы .NET) развития языков программирования: появились class helpers, перегрузки операторов и другое.

ASP.NET — технология создания веб-приложений и веб-сервисов от компании Майкрософт. Она является составной частью платформы Microsoft .NET и развитием более старой технологии Microsoft ASP. На данный момент последней версией этой технологии является ASP.NET 4.5.

Разработчики могут писать код для ASP.NET, используя практически любые языки программирования, входящие в комплект .NET Framework (C#, Visual Basic.NET и JScript .NET). ASP.NET имеет преимущество в скорости по сравнению со скриптовыми технологиями, так как при первом обращении код компилируется и помещается в специальный кэш, и впоследствии только исполняется, не требуя затрат времени на парсинг, оптимизацию, и т. д.

Определение Web-дизайна

Пять областей охватывают основные аспекты Web-дизайна.

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

Зрительные образы. Это относится к компоновке экранного пространства на сайте. Эта компоновка обычно создается с помощью HTML, CSS или даже Flash и может включать графические элементы, выполняющие функции украшения или навигации. Визуальная сторона сайта — это наиболее очевидный аспект Web-дизайна, но не единственная, и не самая важная, сторона дисциплины.

Технология. Хотя применение разнообразных базовых Web-технологий вроде HTML или CSS попадает в эту категорию, под технологией в этом контексте чаще подразумеваются различные интерактивные элементы сайта, в особенности созданные с использованием программных методов.Это могут быть элементы в диапазоне от языков сценариев, работающих на стороне клиента, наподобие JavaScript, до серверных приложений, таких как Java-сервлеты, PHP-сценарии.

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

Назначение. Причина, по которой сайт существует, часто связанная с экономическими вопросами, вероятно, является наиболее важной частью Web-дизайна. Этот элемент следует учитывать при принятии любых решений, затрагивающих другие области. Конечно, степень, в которой каждая сторона Web-дизайна оказывает воздействие на сайт, может изменяться в зависимости от типа создаваемого сайта. Личная домашняя страничка обычно не связана с экономическими соображениями, характерными для Internet-магазина. Внутренняя сеть производственной компании может не попадать под влияние соображений, связанных с визуальным представлением, важных для общедоступного Web-сайта, рекламирующего остросюжетный фильм.

 

В.16. Системы управления базами данных. Структура данных, модели данных, создание базы данных и таблиц. БазыданныхAccess, Oracle, MySQL, Foxpro, dBase, SQLServerидр. Основы языка SQL и построение SQL-запросов.

Систе́ма управле́ния ба́зами да́нных (СУБД) — совокупность программных и лингвистических средств общего или специального назначения, обеспечивающих управление созданием и использованием баз данных[1].

MicrosoftAccess — реляционная СУБД корпорации Microsoft. Имеет широкий спектр функций, включая связанные запросы, связь с внешними таблицами и базами данных. Благодаря встроенному языку VBA, в самом Access можно писать приложения, работающие с базами данных.

Oracle Database 10g – первая в мире база данных, разработанная специально для работы в сетях распределенных вычислений. Oracle Database 10g предоставляет возможность автоматической настройки и управления, которая делает ее использование простым и экономически выгодным. Ее уникальные возможности осуществлять управление всеми данными предприятия - от обычных операций с бизнес-информацией до динамического многомерного анализа данных (OLAP).

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

Гибкость СУБД MySQL обеспечивается поддержкой большого количества типов таблиц: пользователи могут выбрать как таблицы типа MyISAM, поддерживающие полнотекстовый поиск, так и таблицы InnoDB, поддерживающие транзакции на уровне отдельных записей..

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

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

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

При всех своих изменениях, SQL остаётся единственным механизмом связи между прикладным программным обеспечением и базой данных. В то же время, современные СУБД, а, также, информационные системы, использующие СУБД, предоставляют пользователю развитые средства визуального построения запросов.

Каждое предложение SQL — это либо запрос данных из базы, либо обращение к базе данных, которое приводит к изменению данных в базе. В соответствии с тем, какие изменения происходят в базе данных, различают следующие типы запросов: запросы на создание или изменение в базе данных новых или существующих объектов (при этом в запросе описывается тип и структура создаваемого или изменяемого объекта); запросы на получение данных; запросы на добавление новых данных (записей) запросы на удаление данных; обращения к СУБД.

Основным объектом хранения реляционной базы данных является таблица, поэтому все SQL-запросы — это операции над таблицами. В соответствии с этим, запросы делятся на

запросы, оперирующие самими таблицами (создание и изменение таблиц);

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

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

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

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

 

В17. Методы и средства защиты информации. Кодирование и декодирование информации. Защита от несанкционированного доступа к данным. Классы безопасности компьютерных систем. Электронная подпись. Организационно-правовые аспекты защиты информации и авторское право.

Методы обеспечения безопасности информации в ИС:

· препятствие;

· управление доступом;

· механизмы шифрования;

· противодействие атакам вредоносных программ;

· регламентация;

· принуждение;

· побуждение.

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

Управление доступом – методы защиты информации регулированием использования всех ресурсов ИС и ИТ. Эти методы должны противостоять всем возможным путям несанкционированного доступа к информации.

Управление доступом включает следующие функции зашиты:

· идентификацию пользователей, персонала и ресурсов системы (присвоение каждому объекту персонального идентификатора);

· опознание (установление подлинности) объекта или субъекта по предъявленному им идентификатору;

· проверку полномочий (проверка соответствия дня недели, времени суток, запрашиваемых ресурсов и процедур установленному регламенту);

· разрешение и создание условий работы в пределах установленного регламента;

· регистрацию (протоколирование) обращений к защищаемым ресурсам;

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

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

Противодействие атакам вредоносных программ предполагает комплекс разнообразных мер организационного характера и исполь­зование антивирусных программ. Цели принимаемых мер – это уменьшение вероятности инфицирования АИС, выявление фактов заражения системы; уменьшение последствий информационных инфекций, локализация или уничтожение вирусов; восстановление информации в ИС. Овладение этим комплексом мер и средств требует знакомства со специальной литературой.

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

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

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

Вся совокупность технических средств подразделяется на аппаратные и физические.

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

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

Программные средства – это специальные программы и программные комплексы, предназначенные для защиты информации в ИС. Как отмечалось, многие из них слиты с ПО самой ИС.

Из средств ПО системы защиты выделим еще программные средства, реализующие механизмы шифрования (криптографии). Криптография – это наука об обеспечении секретности и/или аутентичности (подлинности) передаваемых сообщений.

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

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

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

КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ

- процесс представления информации в определенной стандартнойформе и обратный процесс восстановления информации по ее такому представлению. В математич.литературе кодированием наз. отображение произвольного множества Ав множество конечныхпоследовательностей (слов) в нек-ром алфавите В, а декодированием - обратное отображение. Примерамикодирования являются: представление натуральных чисел в r-ичной системе счисления, при к-ром каждомучислу N=i,2, ... ставится в соответствие слово b1b2 ... bl в алфавите В r={0, 1, ..., r-1} такое, что b1 неравно 0 иb1rl-1+...+ bl-1r+bl=N; преобразование текстов на русском языке с помощью телеграфного кода впоследовательности, составленные из посылок тока и пауз различной длительности; отображение,применяемое при написании цифр почтового индекса (см. рис.). В последнем случае каждой десятичнойцифре соответствует слово в алфавите В 2={0, 1} длины 9, в котором символами 1 отмечены номераиспользованных линий (напр., цифре 5 соответствует слово 110010011). Исследование различных свойств К.и д. и построение эффективных в определенном смысле кодирований, обладающих требуемымисвойствами, составляет проблематику теории кодирования. Обычно критерий эффективности кодированиятак или иначе связан с минимизацией длин кодовых слов (образов

элементов множества А), а требуемые свойства кодирования связаны с обеспечением заданного уровняпомехоустойчивости, понимаемой в том или ином смысле. В частности, под помехоустойчивостьюпонимается возможность однозначного декодирования при отсутствии или допустимом уровне искажений вкодовых словах. Помимо помехоустойчивости, к кодированию может предъявляться ряд дополнительныхтребований. Напр., при выборе кодирования для цифр почтового индекса необходимо согласование собычным способом написания цифр. В качестве дополнительных требований часто используютсяограничения, связанные с допустимой сложностью схем, осуществляющих К. и д. Проблематика теориикодирования в основном создавалась под влиянием разработанной К. Шенноном (С. Shannon, [1])теориипередачи информации. Источником новых задач теории кодирования служат создание и совершенствованиеавтоматизированных систем сбора, хранения, передачи и обработки информации. Методы решения задачтеории кодирования главным образом комбинаторные, теоретико-вероятностные и алгебраические.Произвольное кодирование f множества (алфавита) Асловами в алфавите Вможно распространить намножество А* всех слов в А(сообщений) следующим образом:

где i=1, 2, . . ., k. Такое отображение f: наз. побуквенным кодированием сооб. щений.Более общий класс кодирований сообщений образуют автоматные кодирования, реализуемыеинициальными асинхронными автоматами, выдающими в каждый момент времени нек-рое (быть может,пустое) слово в алфавите В. Содержательный смысл этого обобщения заключается в том, что автомат вразных состояниях реализует различные кодирования букв алфавита сообщений. Побуквенное кодирование- это автоматное кодирование, реализуемое автоматом с одним состоянием: Одним из направлений теориикодирования является изучение общих свойств кодирования и построение алгоритмов распознавания этихсвойств (см. Кодирование алфавитное). В частности, для побуквенных и автоматных кодирований найденынеобходимые и достаточные условия для того, чтобы:

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

Большинство задач теории кодирования сводится к изучению конечных или счетных множеств слов валфавите В r. Такие множества наз. кодами. В частности, каждому однозначному кодированию f : (и побуквенному кодированию ) соответствует код Одноиз основных утверждений теории кодирования состоит в том, что условие взаимной однозначностипобуквенного кодирования накладывает следующее ограничение на длины li=l,if )кодовыхслов f(i):

Справедливо и обратное утверждение: если (l0, ..., lm-1)- набор натуральных чисел, удовлетворяющих (1), тосуществует взаимно однозначное побуквенное кодирование такое, что слово f(i)имеет длинуli;. При этом, если числа li упорядочены по возрастанию, то в качестве f(i) можно взять первые после запятойli символов разложения числа в r-ичную дробь (метод Шеннона).

Наиболее законченные результаты в теории кодирования связаны с построением эффективных взаимнооднозначных кодирований. Описанные здесь конструкции используются на практике для сжатия информациии выборки информации из памяти. Понятие эффективности кодирования зависит от выбора критериястоимости. При определении стоимости L(f)взаимно однозначного побуквенного кодирования предполагается, что каждому числу поставлено в соответствие положительноечисло р i и Р=0, ..., Pm-1). Исследованы следующие варианты определения стоимости L(f):

причем предполагается, что в первых двух случаях р i- вероятности, с к-рыми некоторый бернуллиевыйисточник порождает соответствующие буквы алфавита В т а в третьем случае р i-заданные длины кодовых слов. При первом определении стоимость равна средней длине кодового слова,при втором определении с ростом параметра tболее длинные кодовые слова оказывают все большеевлияние на стоимость ( при и при ), при. третьемопределении стоимость равна максимальному превышению длины li кодового слова над заданной длиной рi. Задача построения взаимно однозначного побуквенного кодирования f : В* т->В*r, минимизирующегостоимость L(f), равносильна задаче минимизации функции L(f) на наборах (l0, ..., 1 т-1 )из натуральных чисел,удовлетворяющих (1). Решение этой задачи известно при каждом из указанных определений стоимости.Пусть минимум величины L(f)на наборах (l0, . . ., lm-1 )из произвольных (не обязательно натуральных) чиселравен Lr(P)и достигается на наборе (l0 (Р), ...,l т-1 (Р)). Неотрицательная величина I(f) = L(f) - Lr(P)наз.избыточностью, а величина I(f)/L(f)- относительной избыточностью кодирования f. Для избыточности взаимнооднозначного кодирования построенного по методу Шеннона для длин справедливо неравенство I(f)<1. При первом, наиболее употребительном,определении стоимости как среднего числа кодовых символов, приходящихся на одну букву порождаемогоисточником сообщения, величина Lr(P)равна энтропии Шеннона

источника, вычисленной по основанию r, a li(P)=-logrpi. Граница избыточности I(f) = L ср(f)- Н r(P)<1 можетбыть улучшена с помощью так наз. кодирования блоками длины k, при к-ром сообщения длины k(а неотдельные буквы) кодируются по методу Шеннона. Избыточность такого кодирования не превышает 1/k. Этотже прием используется для эффективного кодирования зависимых источников. В связи с тем, чтоопределение длин li при кодировании по методу Шеннона основано на знании статистики источника, для нек-рых классов источников разработаны методы построения универсального кодирования, гарантирующегоопределенную верхнюю границу избыточности для любого источника из этого класса. В частности, построенокодирование блоками длины к, избыточность к-рого для любого бернуллиевого источника асимптотически непревышает (при фиксированных ), причем эта асимптотическая границане может быть улучшена.

продолжение Кодирование и декодорование...

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

При исследовании задач построения эффективных помехоустойчивых кодирований обычно рассматриваюткодирования к-рым соответствуют коды {f(0), . .., f(m-1)}, принадлежащие множеству слов длины пв алфавите В r, и предполагают, чтo буквы алфавита сообщений В т равновероятны.Эффективность такого кодирования оценивают избыточностью I(f)= п-logrm или скоростью передачи В(f)= При определении помехоустойчивости кодирования формализуется понятие ошибки и вводитсяв рассмотрение нек-рая модель образования ошибок. Ошибкой типа замещения (или просто ошибкой) наз.преобразование слова, состоящее в замещении одного из его символов другим символом алфавита В r.Напр., проведение лишней линии при написании цифры почтового индекса приводит к замещению вкодовом слове символа 0 символом 1, а отсутствие нужной линии - к замещению символа 1 символом 0.Возможность обнаружения и исправления ошибок основана на том, что для кодирования f, обладающегоненулевой избыточностью, декодирование f-1 может быть произвольным образом доопределено на r п -тсловах из не являющихся кодовыми. В частности, если множество разбито на тнепересекающихсяподмножеств D0, . .., Dm-1 таких, что а декодирование f-1 доопределено так, что f-1(Di)=i, то придекодировании будут исправлены все ошибки, преобразующие кодовое слово f(i) в Di, i=0, ..., т-1.Аналогичная возможность имеется и в случае ошибок других типов таких, как стирание символа (замещениесимволом другого алфавита), изменение числового значения кодового слова на b=1, ..., r-1, i=0, 1, ... (арифметическая ошибка), выпадение или вставка символа и т. п.

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

где максимум берется по всем наборам (q0, . . ., qm-1 )таким, что и Эффективностькодирования f характеризуется скоростью передачи R(f), а помехоустойчивость - средней вероятностьюошибки декодирования Р(f) (при наилучшем разбиении. В nr на подмножества Di). Основной результат теориипередачи информации (теорема Шеннона) состоит в том, что пропускная способность Сявляется верхнейгранью чисел Rтаких, что для любого е>0 при всех п, начиная с нек-рого, существует кодирование

для к-рого и Р(f)<e.

Другая модель образования ошибок (см. Код с исправлением ошибок, Код с исправлением арифметическихошибок, Код с исправлением выпадений и вставок )характеризуется тем, что в каждом слове длиныппроисходит не более заданного числа tошибок. Пусть Ei(t)- множество слов, получаемых из f(i)в результатеtили менее ошибок. Если для кода

множества Ei(t), i=0, ..., m-1, попарно не пересекаются, то при декодировании таком, что Ei(t)Н Di, будутисправлены все ошибки, допустимые рассматриваемой моделью образования ошибок, и такой код наз.кодом с исправлением tошибок. Для многих типов ошибок (напр., замещений, арифметич. ошибок,выпадений и вставок) функция d( х, у), равная минимальному числу ошибок данного типа, преобразующихслово в слово является метрикой, а множества Ei(t)- метрическими шарами радиуса t.Поэтому задача построения наиболее эффективного (т. е. максимального по числу слов т)кода в В nr сисправлением tошибок равносильна задаче плотнейшей упаковки метрического пространства шарамирадиуса t. Код для цифр почтового индекса не является кодом с исправлением одной ошибки, так как d(f(0),f(8))=1 и d(f(5), f(8)) = 2, хотя все другие расстояния между кодовыми словами не менее 3.

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

причем достигается "мощностная" граница, основанная на подсчете числа слов длины пв шаре радиуса t.Асимптотика величины Ir(n, t )при г>2, а также при r=2 для многих других типов ошибок (напр., арифметич.ошибок, выпадений и вставок) не известна (1978). Во втором случае, когда t=[pn], где р - некотороефиксированное число, 0<р<(r-1)/2r, а "мощностная" граница

где Tr(p)=-p logr(p/(r- 1))-(1-р)logr(l- p), существенно улучшена. Имеется предположение, что верхняя граница

полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir( п,[ рп])~пТ r().Доказательство или опровержение этого предположения - одна из центральных задач теории кодирования.

Большинство конструкций помехоустойчивых кодов являются эффективными, когда длина пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанные со сложностью устройств,осуществляющих кодирование и декодирование (кодера и декодера). Ограничения на допустимый типдекодера или его сложность могут приводить к увеличению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n2, для к-рого существуетдекодер, состоящий из регистра сдвига и одного мажоритарного элемента и исправляющий одну ошибку,имеет порядок (ср. с (2)). В качестве математич. модели кодера и декодера обычно рассматриваютсхемы из функциональных элементов и под сложностью понимают число элементов в схеме. Для известныхклассов кодов с исправлением ошибок проведено исследование возможных алгоритмов К. и д. и полученыверхние границы сложности кодера и декодера. Найдены также нек-рые соотношения между скоростьюпередачи кодирования, помехоустойчивостью кодирования и сложностью декодера (см. [5]).

Еще одно направление исследований в теории кодирования связано с тем, что многие результаты (напр.,теорема Шеннона и граница (3)) не являются "конструктивными", а представляют собой теоремысуществования бесконечных последовательностей п} кодов В связи с этим предпринимаютсяусилия, чтобы доказать эти результаты в классе таких последовательностей п} кодов, для к-рых существуетмашина Тьюринга, распознающая принадлежность произвольного слова длины lмножеству завремя, имеющее медленный порядок роста относительно l(напр., llog l).

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

 


 

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


 





Дата добавления: 2017-02-25; просмотров: 1438 | Нарушение авторских прав


Рекомендуемый контект:


Похожая информация:

Поиск на сайте:


© 2015-2019 lektsii.org - Контакты - Последнее добавление

Ген: 0.018 с.