ТДВ контрольная, научный текст, аннотация, реферат, рецензия. контрольная. Вторичные учебнонаучные тексты
 Скачать 15.62 Kb.
|
|
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «УФИМСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЯНОЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» КАФЕДРА РУССКОГО ЯЗЫКА И ЛИТЕРАТУРЫ Контрольная работа по дисциплине «Технологии делового взаимодействия» на тему: «Вторичные учебно-научные тексты» Выполнил: Студент группы БПОи-21-03 Хаертдинов И.И. Проверил: канд.филол.наук, доцент каф. РЯЛ Бикмаева Л.У. Уфа 2022 Основу многих алгоритмов обработки сетевой информации составляют алгоритмы обхода (итерации) графов, в процессе которых производится поиск необходимой информации или определение каких-либо характеристик сети. Теория графов, как самостоятельная математическая дисциплина, сформировалась в тридцатые годы двадцатого века и нашла широкое применение во многих разделах науки и техники. Методы теории графов успешно используются в теории информации, планировании производства, генетике и химии, на транспорте, в маршрутизации данных в интернете и многих других областях науки, техники и общественной жизни. Теория графов является основным инструментом обработки таких интересных объектов, как лабиринты. Исторически сложилось так, что лабиринты вначале имели мистико-аллегорический статус, затем использовались в качестве элементов садово-парковой культуры и практически не рассматривались как интересный математический объект. Все изменилось во второй половине XX века. Развитие робототехники, проблемы, связанные с автоматизацией проектирования электроники, – все это заставило человечество по-новому взглянуть на лабиринты, увидеть их математическую сущность, рассматривать их как математический объект и в полной мере оценить их практическую важность. В дальнейшем используются следующие понятия и определения: Лабиринт – это какая-либо структура, которая располагается в двухмерном или трехмерном пространстве и состоит из запутанных путей к выходу. Данные пути представляют собой некоторую последовательность локаций; Локация – это входящее в состав лабиринта помещение, имеющее не более четырех соседних помещений, в каждое из которых может вести проход, причем только один. В случае отсутствия прохода, локации отделены друг от друга стеной; Решение лабиринта – это поиск маршрута, соединяющего некоторую начальную (стартовую) локацию и отличную от нее конечную (финальную). В отношении лабиринтов можно условно выделить две фундаментальные проблемы, решение которых позволяет применять лабиринты в выше обозначенных прикладных областях: проблема построения лабиринта и проблема поиска пути в лабиринте. Инструментарий для решения данных задач предоставляет такая область математической науки как дискретная математика, имеющая в своем составе теорию графов, на основе положений которой можно формализовать лабиринт с целью его дальнейшей обработки. Лабиринт можно рассматривать как совокупность трех множеств. Первое множество включает в себя множество локаций, которые содержит лабиринт. С точки зрения теории графов, это множество вершин графа. Вторым множеством является некоторое конечное множество ребер – проходов между локациями. Третье множество ставит паре локаций в соответствие некоторый проход, соединяющий данные локации, причем только один. Следовательно, лабиринт можно представить в виде графа. На основе положений теории графов можно провести формализацию лабиринта, которая будет заключаться в определении класса графов, представителем которого является произвольный лабиринт. Прежде всего, необходимо определить, обязан ли лабиринт являться связным графом, т.е. можно ли связать цепочкой ребер любые две вершины данного графа. Предположим, что это утверждение истинно. Следовательно, не могут существовать лабиринты, которые не имеют решения для некоторой пары точек (локаций). С другой стороны, определение лабиринта не исключает возможности того, что для двух произвольных точек может не существовать маршрута, их соединяющего, что, фактически, приводит к противоречию. Отсюда можно сделать вывод: граф, являющийся формализацией произвольного лабиринта, не является связным. Теперь следует проверить, является ли граф орграфом или ориентированным графом, т. е. графом, для которого задано направление всех ребер (дуг). Проход, которому ставится в соответствие ориентированное ребро, может быть пройден только в выбранном направлении. Но определение локации не содержит требования о невозможности прохождения одного и того же ребра в разных направлениях, что порождает очередное противоречие. Значит, граф, описывающий произвольный лабиринт, является неориентированным – все его ребра не имеют направления. Осталось выяснить, может ли граф содержать кратные ребра (различные ребра, соединяющие одинаковые вершины) или петли (ребра, у которых совпадают начало и конец). Произвольная локация лабиринта, соответствующая данному выше определению, не может содержать прохода, ведущего в эту же локацию. Таким образом, граф не может содержать петель. Наличие кратных ребер подразумевает наличие между локациями двух и более проходов, что также противоречит выше приведенному определению локации. Таким образом, можно заключить, что граф произвольного лабиринта является простым, т. е. не содержит петель и кратных ребер, и неориентированным. Проведенная формализация лабиринта ставит ему в соответствие некоторый граф. Кроме того, по имеющемуся графу можно восстановить лабиринт, которому он соответствует. В связи с этим, проблему генерации лабиринта можно свести к проблеме генерации псевдослучайного графа заданного размера и заданных свойств. В свою очередь, проблему генерации псевдослучайного графа можно упростить и свести к проблеме генерации минимального остового дерева. Из этого следует, что допустимо использование алгоритмов Р. Прима (Robert C. Prim) и Д. Краскала (Joseph B. Kruskal) для генерации минимального остового дерева, но с небольшими модификациями, которые связаны с тем, что граф, лежащий в основе лабиринта, не является взвешенным (это следует из того, что в определении локации не указана «стоимость прохода» по тому или иному маршруту), в то время как исходные алгоритмы Прима и Краскала рассчитаны на взвешенные графы. Рассмотрим алгоритм Краскала. В начале работы данного алгоритма имеется множество не связанных между собой точек, каждая из которых является вершиной будущего графа и множество локацией будущего лабиринта. Каждая из вершин будущего графа образует подграф. Таким образом, в самом начале работы алгоритма имеется граф, состоящий из N-подграфов, не связанных между собой. Конечной задачей является построение N–1 ребра таким образом, чтобы в результате получился полностью связный граф, из любой вершины которого существует маршрут в любую другую вершину. Для решения задачи необходимо выяснить, каким именно образом нужно соединять вершины ребрами. В случае тривиального графа, содержащего всего две вершины, их соединение возможно единственным ребром. Данный случай можно рассматривать в качестве базового. Если количество вершин в графе больше чем две, множество вершин необходимо разбить на два подмножества, каждое из которых примерно в два раза меньше исходного. После этого, если в получившихся множествах оказалось более чем по две вершины, следует провести разбиение каждого из имеющихся подмножеств на два еще меньших подмножества. Разбиения проводятся до тех пор, пока не получится некоторое количество подмножеств, содержащих не более чем две вершины будущего графа, для которых выполняются построения базового случая. Далее множества попарно объединяются путем соединения получившихся пар подграфов одним ребром. Пары подграфов соединяю до тех пор, пока в результате не останется один единственный граф, который и будет являться минимальным остовым деревом для заданного множества точек. В случае с лабиринтами будет получен граф, соответствующий некоторому лабиринту, содержащему N локаций. Алгоритм может быть упрощен следующим образом. Изначально по-прежнему имеется N вершин, каждая из которых является графом. Соединяются две произвольные вершины и тем самым количество подграфов уменьшается на единицу. До тех пор, пока не останется ровно один подграф, т. е. пока не будет построен связный граф, содержащий N вершин, выбирается случайная вершина А, которая соединяется с другой произвольной вершиной B. При этом между вершинами А и B не должно существовать пути – в противном случае граф перестанет быть минимальным, т. к. одно из ребер будет потрачено не на добавление новой вершины, а на образование цикла (на соединение двух вершин, уже встроенных в конечный граф). Задача решения лабиринтов может быть решена следующим образом. Решение лабиринта относительно двух его локаций – это маршрут, соединяющий две данные локации. К настоящему времени разработано большое количество различных алгоритмов, предназначенных для решения лабиринтов. Остановимся на одном из них, который был первоначально открыт в 1956 году в рамках задачи о решении лабиринтов Э. Ф. Муром (E. P. Moore), а также независимо открыт Ч. Ли (C. Y. Lee) при формализации алгоритмов трассировки печатных плат (1961 г.). Речь идет об алгоритме волновой трассировки, известном как алгоритм Ли. По отношению к имеющемуся графу, описывающему лабиринт, данный алгоритм может быть представлен следующим образом. Начальная вершина, из которой будет начинаться поиск, помечается некоторым числом a (как правило – нулем), после чего все вершины, имеющие ребра, общие с начальной вершиной, получают метку на единицу большую. На следующем шаге алгоритм последовательно перемещается в каждую из вершин, имеющих метку a+1, и ставит метки всем связанным с данной, но еще не отмеченным вершинам. Процесс продолжается до тех пор, пока не будет отмечена искомая вершина, или пока не будут отмечены все доступные вершины. В случае, если достигнут второй результат, а искомая вершина так и не получила метку, говорят, что нет решения для двух данных точек, т. к. не существует маршрута, который включал бы их обеих. В случае, если искомая вершина получила некоторую метку b, алгоритм прекращает расстановку новых меток и перемещается в искомую вершину. Поскольку все вершины, которые входят в маршрут, соединяющий начальную и конечную вершины, имеют некоторые метки, лежащие в интервале (a, b), можно восстановить маршрут, действуя следующим образом. Запомнить вершину, имеющую метку b, после чего выбрать вершину, имеющую метку b-1, переместиться в нее и запомнить эту вершину. После этого выбрать новую вершину, имеющую метку на единицу меньше, переместиться в нее и также запомнить. Подобные действия совершаются до тех пор, пока не будет достигнута точка, имеющая метку a. В результате вершины, которые были запомнены во время обратного движения, будут составлять искомый маршрут. Проведенная формализация понятия лабиринта, как математического объекта в теории графов и рассмотренный алгоритм позволяют решать многие важные и интересные задачи, связанные с генерацией и решением лабиринтов [1]. Проблемы, связанные с данной тематикой, в том числе генерация и, особенно, решение лабиринта, меняющегося при каждом движении в нем, а также программное прохождение лабиринта в условиях ограниченного обзора, детально рассмотрены не были, что оставляет возможность дальнейших изысканий в этой области. Еще одно направление развития данной темы связано со сравнительным анализом различных алгоритмов генерации и решения лабиринтов. Представленные сведения носят универсальный характер и могут служить дидактическими материалами в ходе организации обучения будущих программистов при рассмотрении вопросов программирования алгоритмов обхода графов. (Современные научные исследования и инновации. 2015. № 12) Аннотация Мартынюк Ю.М., Ванькова В.С., Угаров А.С. Формализация лабиринта в теории графов // Современные научные исследования и инновации. 2015. № 12 В статье представлены основные понятия лабиринтов, как математических объектов теории графов. В статье формализовано понятие лабиринта, рассмотрены основные задачи, решаемые в данной предметной области. Приведены алгоритмы решения задач и фрагменты их программной реализации на языке С++. Данная статья предназначена для студентов и преподавателей технических вузов. И также начинающих и опытных программистов. Реферат Статья под заголовком “Формализация лабиринта в теории графов” написана кандидатом педагогических наук, доцентом кафедры информатики и информационных технологий Тульского государственного педагогического университета им. Л.Н. Толстого Мартынюк Юлией Михайловной. И опубликована в журнале “современные научные исследования и инновации” №12 в 2015 году. Статья представляет собой описание метода представления лабиринта в виде графа. Для дальнейшего его исследования с математической точки зрения и использования в компьютерных программах. В статье рассмотрены варианты задания графов подходящих для решения задач с лабиринтами. В начале отмечается, что исторически лабиринты имели мистико-аллегорический статус. И лишь недавно, с развитием робототехники, математики по новому взглянули на лабиринты. Так же задаются и объясняются необходимые понятия теории графов. В основной части статьи автор подробно описывает алгоритмы задания лабиринтов в виде графов локаций и маршрутов. Для этого используется алгоритм Краскала, создающий граф из множества не соединенных точек и множества локаций будущего лабиринта. А результатом данного алгоритма является множество путей в конечном графе. Далее автор рассматривает алгоритм решения графа, представляющего лабиринт. Для решения этой задачи используется алгоритм волновой трассировки или алгоритм Ли. В данном алгоритме дистанция до i-ой вершины находится прибавлением единицы к длине предшествующей вершины. Благодаря этому можно не только определить имеется ли решение лабиринта, но и найти кратчайший путь от входа до выхода. Автор приходит к выводу, что использование лабиринтов формализованных в теории графов поможет в решении различных задач связанных с робототехникой и электроникой. Таким образом можно прийти к выводу, что решение задач генерации и обхода лабиринтов является важной тенденцией в нынешнем IT-мире. Рецензия В рецензируемой статье идет речь о представлении лабиринтов в теории графов для дальнейшего использования этой модели в программировании и робототехнике. Актуальность статьи не вызывает сомнения, поскольку начиная со второй половины ХХ века, с развитием робототехники появилась потребность решать задачи ориентирования роботов в пространстве, поиска оптимальных путей и обхода графов. В работе описываются методы построения графов на основе алгоритма Краскала и дальнейшее их решение с помощью алгоритма Ли или же обхода в ширину. Таким образом, рассматриваемая статья даёт нам представление о представлении лабиринтов в виде графов и дальнейшей их обработке . В данной работе отсутствуют значительные недостатки. Представляется, что в целом статья имеет важное значение и будет полезной для студентов и преподавателей технических вузов, разработчиков, организаторов бизнес-процессов, будущих работников в IT-сфере. |