Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Реферат актуальність теми

Скачати 75.28 Kb.

Реферат актуальність теми




Скачати 75.28 Kb.
Дата конвертації16.04.2017
Розмір75.28 Kb.
ТипРеферат

РЕФЕРАТ

Актуальність теми. Зі зростанням застосування цифрових телекомунікаційних технологій все більш актуальними стають дослідження методів підвищення ефективності та надійності передачі цифрових даних.
Підвищення (елевація) - кутова висота об'єкта спостереження (земного предмета, літального апарату, небесного світила тощо) над істинним горизонтом. Підвищення спільно з азимутом служить для визначення напрямку на об'єкт.
Актуа́льність (від лат. actualis - справжній, теперішній, сучасний, важливий у даний момент, злободенний, назрілий) - абстрактний іменник до прикметника «актуальний». Актуальність - важливість, значимість чого-небудь на сьогодні, сучасність, злободенність.
Застосунок Застосунок, застосовна програма, прикладна програма (англ. application, application software; пол. aplikacja; рос. приложение, прикладная программа) - користувацька комп'ютерна програма, що дає змогу вирішувати конкретні прикладні задачі користувача.
Телекомунікації Телекомуніка́ції, також електрозв'язок (англ. Telecommunications) - передавання, випромінювання та/або приймання знаків, сигналів, письмового тексту, зображень та звуків або повідомлень будь-якого роду дротовими, радіо, оптичними або іншими електромагнітними системами.
До них належать методи завадостійкого кодування, засновані на штучному введенні надлишковості.
Код (франц. code, від лат. codex) (англ. code, нім. Schlüssel m, Kennzahl f, Kode m) - зведення законів, система умовних знаків (символів, позначень) для передачі, обробки та зберігання (запам'ятовування) різноманітної інформації.
До найбільш поширених видів коригувальних кодів належать розподільні завадостійкі коди, які мають обмеження на кількість кодових слів у дозволеному коді із заданою розрядністю. Можливим вирішенням проблеми є застосування нерозподільних блочних коригуючих кодів. Їх застосування актуальне для великого спектру сімейств датчиків з апаратурою кодування та декодування значень, що отримуються з цих датчиків. Проте для кодування у нерозподільних кодах необхідно згенерувати максимальний код, що потребує значних обчислювальних ресурсів.
Розрядність числа в математиці - кількість числових розрядів, необхідних для запису цього числа в тій чи іншій системі числення. Розрядність числа іноді також називається його довжиною.
Апаратура (рос. аппаратура, англ. apparatus, нім. Apparatur) - сукупність функціонально різноманітних вимірювальних приладів і допоміжних пристроїв та пристосувань, спеціально підібраних для виконання певної технічної задачі.
Кількість - в Арістотелівській логіці друга з 10 категорій (класів, розрядів, які спрощують процес розумового визначення будь-якої речі), побічна обставина матеріальних речей , за допомогою якої вони поширюються в просторі, вимірюються якоюсь математичною нормою і здатні бути поділеними на окремі частини.
Обчи́слювальні ресу́рси - можливості, забезпечувані компонентами обчислювальної системи, що витрачаються (зайняті) в процесі її роботи.
Ця проблема зводиться до пошуку максимальної кліки графа Хеммінга, що є сама є актуальною проблемою в області дискретної оптимізації вирішення NP-повних задач.
Проблема - складне теоретичне або практичне питання, що потребує розв'язання, вивчення, дослідження. Проблема - об'єкт (питання, недолік чи потреба чогось,завада від надлишку чи наявності чогось, процес) явище збуджуючого характеру як стимул діяльності спонукаючого характеру - незадоволений попит чи нереалізовані потреби (нестача або відсутність, надлишок або наявність чого-небудь), дефект, вада, чи загроза що змушує цілеспрямовано ліквідувати проблему шляхом уникнення взаємодії чи зміни стану об'єкту, себе чи свого ставлення до подій.


Об’єктом дослідження є нерозподільні коригуючі блочні коди.

Предметом дослідження є жадібний алгоритм пошуку кліки графа Хеммінга.

Мета роботи: дослідити предметну область та створити модифікацію жадібного алгоритму пошуку максимальної кліки графа Хеммінга, оцінка швидкодії якого є достатньою для виконання ефективного пошуку максимального нерозподільного коригуючого коду.
Швидкодія (рос. быстродействие, англ. speed of response, нім. Schnelligkeit f, Reaktionsfähigkeit f, Ansprechgeschwindigkeit f) - швидкість реакції системи на зовнішні дії або кількість операцій, які здійснює система за одиницю часу.
Комбінаторна оптимізація (англ. Combinatorial optimization) - розділ теорії оптимізації. Розглядає задачі оптимізації множина розв'язків яких дискретна або може бути зведена до дискретної.
Жа́дібний алгори́тм - простий і прямолінійний евристичний алгоритм, який приймає найкраще рішення, виходячи з наявних на поточному етапі даних, не турбуючись про можливі наслідки, сподіваючись врешті-решт отримати оптимальне рішення.
NP-повна задача (англ. NP-complete) - в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час. Зміст 1 Формальне визначення 1.
Предме́тна о́бласть (ПрО) - множина всіх предметів, властивості яких і відношення між якими розглядаються в науковій теорії. В логіці - гадана область можливих значень предметних змінних логічної мови.


Наукова новизна полягає в наступному:

1. Подальший розвиток методів пошуку максимальних нерозподільних блочних кодів.

2.  Подальший розвиток методів пошуку максимальної кліки графа Хеммінга на базі жадібного алгоритму.

Практична цінність отриманих в роботі результатів полягає в тому, що отримана, як результат виконання імплементації модифікованого алгоритму кліка, інтерпретується, як код завадостійкого кодування, який можливо застосувати для кодування та декодування отриманих даних з різного роду датчиків.

Апробація роботи. Основні положення і результати роботи представлені та обговорені на:

V науковій конференції магістрантів та аспірантів «Прикладна математика та комп’ютинг – ПМК’2013» (Київ, 10 – 12 квітня 2013 року).

Результат, пі́дсумок, (заст. ску́ток, вислід) - кінцевий наслідок послідовності дій. Можливі результати містять перевагу, незручність, вигоду, збитки, цінність і перемогу. Результат є етапом діяльності, коли визначено наявність переходу якості в кількість і кількості в якість.
Mathematica - система комп'ютерної алгебри компанії Wolfram Research. Містить багато функцій як для аналітичних перетворень, так і для чисельних розрахунків. Крім того, програма підтримує роботу з графікою і звуком, включаючи побудову дво- і тривимірних графіків функцій, малювання довільних геометричних фігур, імпорт та експорт зображень і звуку.
Інтерпретатор мови програмування (interpreter) - програма чи технічні засоби, необхідні для виконання інших програм, вид транслятора, який здійснює пооператорну (покомандну, построкову) обробку, перетворення у машинні коди та виконання програми або запиту (на відміну від компілятора, який транслює у машинні коди всю програму без її виконання).
Імплемента́ція (лат. impleo - «наповнюю», «виконую») - здійснення, виконання державою міжнародних правових норм. Кожна держава сама визначає методи і засоби імплементації. У міжнародному договорі також може бути передбачена необхідність видання закону чи іншого акта для його здійснення.
Аспірáнт - основна форма підготовки наукових кадрів при вищих навчальних закладах і науково-дослідницьких установ. Час навчання в стаціонарній аспірантурі входить до наукового стажу і зараховується при призначенні пенсії за Законом України «Про наукову та науково-технічну діяльність».
Поло́ження - нормативно-правовий або локально-правовий акт, що визначає основні правила організації та діяльності державних органів, структурних підрозділів органу, а також установ, організацій і підприємств (філій), що їм підпорядковуються, тимчасово створюваних комісій, груп, бюро і т. ін.
Магі́стр - освітній ступінь, що здобувається на другому рівні вищої освіти та присуджується вищим навчальним закладом у результаті успішного виконання здобувачем вищої освіти відповідної освітньої програми.

VІI науковій конференції магістрантів та аспірантів «Прикладна математика та комп’ютинг – ПМК’2015» (Київ, 15 – 17 квітня 2015 року).

Восьмій міжнародній науково-практичній конференції «ІНТЕГРОВАНІ ІНТЕЛЕКТУАЛЬНІ РОБОТОТЕХНІЧНІ КОМПЛЕКСИ» (ІІРТК-2015) 18-19 травня 2015 року.



Публікації. Основні результати магістерської роботи опубліковані в 3-х наукових роботах.

Структура та обсяг роботи. Магістерська дисертація складається з вступу, чотирьох розділів та висновків.
Інтелектуал - людина розумової праці[Джерело?]. «Інтелектуалом» також називають[Хто?] освічену, начитану людину з високо розвиненим інтелектом[Джерело?].
Дисерта́ція (лат. dissertatio - твір, обговорення, розсуд, доповідь) - спеціально підготовлена наукова праця на правах рукопису, яку виконують для прилюдного захисту на здобуття наукового ступеня. В Україні розрізняють дисертацію для здобуття наукового ступеня кандидата наук (кандидатська дисертація) та доктора наук (докторська дисертація).


У вступі подано загальну характеристику роботи, зроблено оцінку сучасного стану проблеми, обґрунтовано актуальність напрямку досліджень, сформульовано мету і задачі досліджень, показано наукову новизну отриманих результатів і практичну цінність роботи.

У першому розділі введено принципи завадостійкого кодування, наведено класифікацію коригуючих кодів та введено модель представлення множини коригуючих кодів на графі Хеммінга

У другому розділі наведено формулювання та теоретичні засади завдання пошуку кліки графа, розглянуто аналітичні оцінки обчислювальну складність вирішення завдання.
Аналітика (від грец. άναλυτικά ) - основа інтелектуальної, логіко-мисленевої діяльності, спрямованої на рішення практичних завдань. У її основі лежить не стільки принцип констатації фактів, скільки принцип «випередження подій», що дозволяє організації або індивідові прогнозувати майбутній стан об'єкту аналізу.
Тео́рія (від грец. θεωρία - розгляд, дослідження) - сукупність висновків, що відображає відносини і зв'язки між явищами реальності у вигляді інформаційноі моделі. Теорією стає гіпотеза, що має відтворюване підтвердження явищ та механізмів і дозволяє спостерігачу прогнозувати наслідки дій чи зміни стану об'єкта спостережень.
Дослідження Дослі́дження, до́сліди - (широко розуміючи) пошук нових знань або систематичне розслідування з метою встановлення фактів; (вузько розуміючи) науковий метод (процес) вивчення чого-небудь.
Складність обчислювальних процесів - це поняття теорії складності обчислень, оцінка ресурсів (зазвичай часу) необхідних для виконання алгоритму.


У третьому розділі розглянуто алгоритм Брона-Кербоша для універсального випадку пошуку кліки графа, сформульовано теоретичні засади жадібних евристик та наведено модифікацію жадібного алгоритму пошуку кліки графа Хеммінга.
Алгоритм Брона - Кербоша - метод гілок і меж для пошуку всіх клік (а також максимальних за включенням незалежних множин вершин) неорієнтованого графа. Розробили 1973 року голландські математики Бронній і Кербош.


У четвертому розділі розглянуто оцінку обчислювальної складності алгоритмів пошуку кліки графа, виконано порівняння експериментальних результатів роботи імплементацій алгоритмів Брона-Кербоша та модифікованого жадібного алгоритму пошуку кліки графа Хеммінга, показано можливості прикладного застосування отриманих результатів.
Алгори́тм (латинізов. Algorithmi за араб. ім'ям узб. математика аль-Хорезмі) - набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій; система правил виконання дискретного процесу, яка досягає поставленої мети за скінченний час.
Порівняння (лат. comparatio) - це троп, у якому один предмет, подія зіставляються з іншими, у яких ці особливості виявлені різко, яскраво. Порівняння виконують зображальну і емоційно-оціночну роль.
Експериме́нт (англ. experiment) - сукупність дослідів, об’єднаних однією системою їх постановки, взаємозв’язком результатів і способом їх обробки. В результаті експерименту отримують сукупність результатів, які допускають їхню сумісну обробку і зіставлення.


У висновках підбитий підсумок по результатам проведеної роботи.

Робота представлена на 86 аркушах, містить 12 рисунків, 3 таблиці, та список використаних літературних джерел з 25 найменувань.



Ключові слова: максимальна кліка графа, граф Хеммінга, нерозподільний коригуючий код.

ABSTRACT

Relevance of the topic. With the increasing use of digital telecommunication technologies the research of the methods of increasing the efficiency and reliability of the transmission of digital data becomes increasingly important.
Transmission - вільний BitTorrent-клієнт з простим, інтуїтивно зрозумілим інтерфейсом для UNIX-подібних операційних систем. Має менший функціонал, ніж більшість інших клієнтів, проте забезпечує основні можливості роботи з BitTorrent-мережами при малій витраті системних ресурсів.
These include methods of error-correcting coding based on the artificial introduction of redundancy. The most common type of error-correcting codes is declared as separable correcting codes that have a limit on the number of code words in the permitted code with a given digit capacity. A possible solution is the usage of inseparable block correcting codes. Their usage is important for a wide range of sensors families with encoding and decoding apparatus of values ​​obtained from these sensors. However, to be able to encode in terms of inseparable codes it’s needed to generate the maximum code, which requires significant computing resources. The problem boils down to the problem of finding a maximum clique of Hamming graph, which itself is an urgent problem in the area of ​​discrete optimization of NP-complete problems.

Object of research are inseparable block correcting codes.

The subject of the study is the greedy algorithm to find the maximal clique of Hamming graph.

Purpose of the work: explore the subject area and create a modification of the greedy algorithm for finding maximal cliques of the Hamming graph with the computational complexity that is sufficient to carry out an effective search of maximum undivided correcting code for given digital capacity.

Scientific novelty of the results consists in the following:

1. Further development of methods to find the maximum inseparable block codes.

2.  Further development of methods to find the maximum clique of Hamming graph based on the greedy algorithm.

The practical value of obtained results is that the clique obtained as the result of the implementation of the modified algorithm is interpreted as the inseparable correcting code that can be used to encode and decode the data obtained from various kinds of sensors ..

Work approbation. Fundamentals and results are presented and discussed at:

V scientific conference of graduate and post-graduate students ‘Applied Mathematics and Computing – AMC’2013’ (Kyiv, 10 - 12 April 2013).

VІI scientific conference of graduate and post-graduate students ‘Applied Mathematics and Computing – AMC’2015’ (Kyiv, 15 - 17 April 2015).

Eights international scientific-practical conference ‘integrated intelligent robotic systems’ (IIRTS-2015) on 18-19 May 2015.



Publications. The main results of the master's work published in 3 scientific works.

The structure and volume of work. Master's thesis consists of an introduction, four chapters and conclusions.

The introduction presents the general characteristics of the work. Evaluated the current state of the problem, the actuality of research areas, formulated the goals and objectives of the research, showed the scientific novelty of the results and practical value of the work.

The first section covers principles of error-correcting coding, the classification of error-correcting codes and the graph model to represent the set of correcting codes are presented.

The second section provides the theoretical formulations and foundations of the maximal clique find problem, the computational complexity estimation of the maximal clique find problem is reviewed.

In the third section the Bron-Kerbosch algorithm for universal case solution is reviewed, theoretical foundations of the greedy euristics are formulated, experimental results are compared and possible ways of applied usage of the results are shown.

In the fourth section the computational complexity estimates of Bron-Kerbosch and modified greedy algorithms for maximal clique of Hamming graph search are provided.

The conclusions contains the results of the carried out work .

Work is presented at 86 sheets containing 12 drawings, 3 tables and list of used literature sources contained 25 items.



Keywords: maximal clique of the graph, Hamming graph, inseparable correcting code.

РЕФЕРАТ

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

Объектом исследования являются нераздельные корректирующие блочные коды.

Предметом исследования является жадный алгоритм поиска клики графа Хэмминга.

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

Научная новизна заключается в следующем:

1. Дальнейшее развитие методов поиска максимальных нераздельных блочных кодов.

2. Дальнейшее развитие методов поиска максимальной клики графа Хемминга на базе жадного алгоритма.

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

Апробация работы. Основные положения и результаты работы представлены и обсуждены на:

V научной конференции магистрантов и аспирантов «Прикладная математика и компьютинг – ПМК’2013» (Киев, 10 – 12 апреля 2013 года).

VІI научной конференции магистрантов и аспирантов «Прикладная математика и компьютинг – ПМК’2015» (Киев, 15 – 17 апреля 2015 года).

Восьмой международной научно-практической конференции «ИНТЕГРИРОВАННЫЕ ИНТЕЛЛЕКТУАЛЬНЫЕ РОБОТОТЕХНИЧЕСКИЕ КОМПЛЕКСЫ» (ИИРТК-2015) 18-19 мая 2015 года.



Публикации. Основные результаты магистерской работы опубликованы в 3-х научных работах.

Структура и объем работы. Магистерская диссертация состоит из введения, четырех глав и выводов.

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

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

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

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

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

В выводах подведен итог по результатам проведенной работы.

Работа представлена на 86 листах, содержит 12 рисунков, 3 таблицы и список использованных литературных источников из 25 наименований.



Ключевые слова: максимальная клика графа, граф Хемминга, нераздельный корректирующий код.


Скачати 75.28 Kb.

  • Об’єктом дослідження
  • Практична цінність
  • Апробація роботи.
  • ІНТЕЛЕКТУАЛЬНІ
  • Структура та обсяг роботи.
  • Ключові слова
  • Object of research
  • Publications.
  • Keywords
  • Объектом исследования
  • Публикации.