Державний університет телекомунікацій Кафедра Прикладного програмування ЗАГАЛЬНОУНІВЕРСИТЕТСЬКА СТУДЕНТСЬКА НАУКОВА КОНФЕРЕНЦІЯ ПРОГРАМУВАННЯ В ІТ - PDF

Description
Державний університет телекомунікацій Кафедра Прикладного програмування ЗАГАЛЬНОУНІВЕРСИТЕТСЬКА СТУДЕНТСЬКА НАУКОВА КОНФЕРЕНЦІЯ ПРОГРАМУВАННЯ В ІТ 21 квітня 2016 р. ПРАЦІ КОНФЕРЕНЦІЇ Київ ДУТ 2016 ОРГАНІЗАЦІЙНИЙ

Please download to get full document.

View again

of 30
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Shopping

Publish on:

Views: 20 | Pages: 30

Extension: PDF | Download: 0

Share
Transcript
Державний університет телекомунікацій Кафедра Прикладного програмування ЗАГАЛЬНОУНІВЕРСИТЕТСЬКА СТУДЕНТСЬКА НАУКОВА КОНФЕРЕНЦІЯ ПРОГРАМУВАННЯ В ІТ 21 квітня 2016 р. ПРАЦІ КОНФЕРЕНЦІЇ Київ ДУТ 2016 ОРГАНІЗАЦІЙНИЙ КОМІТЕТ Голова Онищенко В.В. Заступник голови Гладиш О.Б. Члени комітету Гуменюк І.М., Яскевич В.О., Коник Р.С., Тихонов Е.С., Скубак О.М., Дробик О.В., Марченко О.В., Солодкий В.Д Державний університет телекомунікацій Орфографія та пунктуація авторів збережена 2 Використання мурашиного алгоритму для оптимізації запитів до бази даних Коник Р. С., аспірант кафедри ПП Василенко В. В., аспірант кафедри КНІТ Куклов В. С., аспірант кафедри ТС Мурашиний алгоритм (алгоритм оптимізації наслідуванням мурашиній колонії, англ. ant colony optimization, ACO.) - один з ефективних поліноміальних алгоритмів для знаходження наближених рішень задачі комівояжера, а також аналогічних завдань пошуку маршрутів на графах. Суть підходу полягає в аналізі та використанні моделі поведінки мурах, що шукають шляхи від колонії до джерела живлення і являє собою метаевристичну (англ. metaheuristic, meta «за межами» и heuristic «знайти») оптимізацію. Перша версія алгоритму, запропонована доктором наук Марко Дориго в 1992 році, була спрямована на пошук оптимального шляху в графі. В основі алгоритму лежить поведінка мурашиної колонії - маркування більш вдалих шляхів великою кількістю феромона. Робота починається з розміщення мурашок у вершинах графа (містах), потім починається рух мурашок - напрям визначається імовірнісним методом, на підставі формули виду: де: Pi - ймовірність переходу по шляху i, li - величина, зворотна вазі (довжині) i-ого переходу, fi - кількість феромону на i-му переході, q - величина, що визначає «жадібність» алгоритму, p - величина, що визначає «стадність» алгоритму і q + p = 1. Оновлення феромонів відбувається відповідно до формули: i, j = (1 - ) i, j + i, j, де i, j кількість феромону на дузі і, j, швидкість випаровування феромону, i, j кількість відкладеного феромону, зазвичай визначається як де L k вартість k-го шляху мурахи (зазвичай довжина). Рішення не є точним і навіть може бути одним з найгірших, однак, в силу імовірнісного рішення, повторення алгоритму може видавати досить точний результат. У реальному світі мурахи (спочатку) ходять у випадковому порядку і коли знаходять продовольство повертаються в свою колонію, прокладаючи феромонами стежки. Якщо інші мурахи знаходять такі стежки, вони, найімовірніше, підуть за ними. Замість того, щоб відстежувати ланцюжок, вони зміцнюють його при поверненні, якщо 3 в кінцевому підсумку знаходять джерело живлення. Згодом феромонна стежка починає випаровуватися, тим самим зменшуючи свою привабливу силу. Чим більше часу потрібно для проходження шляху до мети і назад, тим сильніше випарується феромонна стежка. На короткому шляху, для порівняння, проходження буде більш швидким і як наслідок, щільність феромонів залишається високою. Випаровування феромонів так само має властивість уникнення, прагнення до локально-оптимального рішення. Якби феромони не випаровувались, то шлях, обраний першим, був би найпривабливішим. У цьому випадку, дослідження просторових рішень були б обмеженими. Таким чином, коли один мураха знаходить (наприклад, короткий) шлях від колонії до джерела їжі, інші мурахи, швидше за все підуть цим шляхом, і позитивні відгуки в кінцевому підсумку приводять всіх мурах до одного, найкоротшого, шляху. Оригінальна ідея виходить від спостереження за мурахами в процесі пошуку найкоротшого шляху від колонії до джерела живлення і проілюстрована на малюнку нижче. 1. Перший мураха знаходить джерело їжі (F) будь-яким способом (а), а потім повертається до гнізда (N), залишивши за собою стежку з феромонів (b). 2. Потім мурахи вибирають один з чотирьох можливих шляхів, потім зміцнюють його і роблять привабливим. 3. Мурахи вибирають найкоротший маршрут, так як у більш довгих феромони сильніше випарувалися. Серед експериментів з вибору між двома шляхами нерівної довжини, що ведуть від колонії до джерела живлення, біологи помітили, що, як 4 правило, мурашки використовують найкоротший маршрут. Модель такої поведінки полягає в наступному: Мурашка (так званий «Бліц») проходить випадковим чином від колонії. Якщо він знаходить джерело їжі, то повертається в гніздо, залишаючи за собою слід з феромона. Ці феромони привертають інших мурах що знаходяться поблизу, які найімовірніше підуть по цьому маршруту. Повернувшись в гніздо, вони зміцнять феромонну стежку. Якщо існує 2 маршрути, то коротшим, за той же час, встигнуть пройти більше мурах, ніж по довгому. Короткий маршрут стане більш привабливим. Довгі шляхи, в кінцевому підсумку, зникнуть через випаровування феромонів. Мурахи використовують навколишнє середовище як засіб спілкування. Вони обмінюються інформацією непрямим шляхом, через феромони, в ході їх «роботи». Обмін інформацією має локальний характер, тільки ті мурахи, які знаходяться в безпосередній близькості, де залишилися феромони - можуть дізнатися про них. Така система називається «Stigmergy» і справедлива для багатьох соціальних тварин (була вивчена в процесі будівництва стовпів в гніздах термітів). Даний механізм вирішення проблеми дуже складний і є хорошим прикладом самоорганізації системи. Така система базується на позитивному (інші мурахи зміцнюють феромонну стежку) і негативному (випаровування феромонної стежки) зворотньому зв'язку. Теоретично, якщо кількість феромонів залишатиметься незмінним, з плином часу, по всіх маршрутах, неможливо буде вибрати шлях. Однак через зворотний зв'язок, невеликі коливання призведуть до посилення одного з маршрутів і система стабілізується до найкоротшого шляху. ЛІТЕРАТУРА 1. Chakravarthy U.S., Fishman D.H., Minker J. Semantic Query Optimization in Expert Systems and Database Systems // Expert Database Syst.: Proc. 1st Int. Workshop, Menlo Park, Calif., Feb New York, Database Modeling and Design: Logical Design / T.Teorey, S. Lightstone, T. Nadeau, H. Jagadish., p. (Elsevier). 5 Алгоритм оптимизации больших данных Тихонов Е. С., аспирант кафедры Прикладного программирования Научный руководитель: Онищенко В. В., к.ф-м.н, доцент Большие данные в какой-то степени являются, абстрактной фразой, которая описывает зависимость между размером данных и скоростью обработки данных в системе. Простое для понимания определение понятия гласит следующее: «данные, размер которых вынуждает нас выходить за пределы проверенных временем методов, широко распространенных в данное время» [1]. Это означает, что сценарий, при котором инновационная оптимизация для обеих: моделей и алгоритмов требуется для обработки больших объемов данных, вполне может быть классифицирована как большая проблема данных. Когда торговые представители и клиенты ведут переговоры, сделка должна быть подтверждена, что окончательные предложения будет оказывать достаточно высокую прибыль для компании, занимающейся продажей. Крупные компании имеют разные способы сделать это, один из которых является запуск моделирования продаж. Такие системы моделирования часто требуются выполнять сложные вычисления над большими объемами данных, которые, в свою очередь, требуют эффективных моделей и алгоритмов. Проект намерен оценить, можно ли оптимизировать и расширить существующую систему продаж под названием РСТ, которая в настоящее время страдает от недопустимо высокого времени работы в процессе моделирования. Это делается на основе анализа текущей реализации, а затем за счет оптимизации своих моделей и разработки эффективных алгоритмов. Производительность этих оптимизированных и расширенных моделей по сравнению с существующей используется для того, чтобы оценить их улучшение. Заключением этого проекта является то, что процесс моделирования в РСТ действительно может быть оптимизирован и расширен. Оптимизированные модели служат доказательством концепции, которая показывает, что результаты, идентичные исходной системы, и могут быть вычислены в пределах 1% от первоначального времени работы для крупнейших клиентов. ЛИТЕРАТУРА 1. Jacobs, The pathologies of big data, Commun. ACM Vol. 52 (8) (2009) pp Емпіричні методи у створенні алгоритмів розпізнавання одновимірних штрих-кодів Мокрінцев О.А. аспірант кафедри Прикладного програмування, Піскунов О.Г. Науковий керівник: к.т.н., доцент Скубак О.М., Одновимірні штрих-коди відіграють важливу роль у сучасному повсякденному житті. З поширенням мобільних камер у смартфонах розпізнавання штрих-кодів у зображеннях стало однією з найактуальніших і поширених задач. У той же час трансляція зовнішньої графічної інформації у цифрову форму стикається з певними труднощами. Нерівномірне освітлення, перекоси зображень, цифровий шум у бюджетних камерах вносять нелінійну складову та ускладнюють процес розпізнавання. Тому, щоб максимально успішно розпізнавати штрих-коди потрібно постійно вдосконалювати набір алгоритмів з області обробки цифрової обробки зображень та методику їх застосування. Отже, дедалі актуальними у такий ситуації стають емпіричні методи досліджень. Емпіричний цикл у його класичному розумінні складається з наступних елементів: Спостереження (Observation): збір та групування емпіричних фактів, формування гіпотези. Індукція (Induction): розробка гіпотез. Дедукція (Deduction): дедукція або виведення послідовності гіпотез, які перевіряються прогнозуванням. Перевірка (Testing): перевірка гіпотези з нового емпіричного матеріалу. Оцінка (Evaluation): оцінка результатів перевірки. У проблемі розпізнавання об єктів у зображеннях взагалі і зокрема штрих-кодів на сьогодні не існує єдиного шляху отримання результату. Кожен випадок ускладнень вимагає використання специфічних інструментів (алгоритмів), кожен у більшості випадків з особливими налаштуваннями. Отже, на макро-рівні ми маємо аналізувати вхідні зображення, ідентифікувати типові проблеми, що виникають на кожній стадії процесу розпізнавання, від введення даних до обробки і верифікації результату. Далі, по винайденим проблемам розробляються нові чи вдосконалюються існуючи методи і алгоритми, які перевіряються шляхом серій експериментів. У той же час емпіричність проблематики розпізнавання штрих-кодів виникає також на мікро-рівнях. Наведемо як приклад метод бінаризації півтонових зображень Ніблека [1] дещо вдосконалений Жангом і Таном [2]. Метод базується на обчисленні локального середнього значення та 7 локального середньоквадратичного відхилення. Порогове значення має вигляд: s( x, y) B( x, y) ( x, y) 1 k 1 R де k та R емпіричні константи. У такому вигляді алгоритм стає менш чутливим до шумових явищ. Наведені константи підбираються у більшості випадків експериментальним шляхом. Література 1. Niblack, An Introduction to Digital Image Processing. Englewood Cliffs, NJ: Prentice-Hall, 1986, pp Z. Zhang and C. L. Tan, Restoration of images scanned from thick bound documents, Proc. Int. conf. Image Processing., vol. 1, 2001, pp Игровые движки. Популярные инструменты разработки игр. Бешта Я.А., ф-т Информационных Технологий, группа ПД-11 Научный руководитель: Скубак А.Н., доцент кафедры прикладного программирования 1. Что такое игровой движок и что он включает? Игровой движок центральный программный компонент компьютерных и видеоигр или других интерактивных приложений с графикой, обрабатываемой в реальном времени. Основную функциональность обычно обеспечивает игровой движок, включа
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks