WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     | 1 |   ...   | 69 | 70 || 72 | 73 |   ...   | 93 |

«ТРУДЫ XI МЕЖДУНАРОДНЫХ КОЛМОГОРОВСКИХ ЧТЕНИЙ Ярославль 2013 УДК 51; 51:372.8; 51(091) Печатается по решению редакционноББК 22.1 я434 издательского совета ЯГПУ им. К. Д. ...»

-- [ Страница 71 ] --

Хотя в самой работе [3] О. Борувки нет речи о каком-либо графе, тем не менее, в конце работы приведена интерпретация матрицы, удовлетворяющей условиям (1)-(3) как матрицы расстояний Т.е. любые две вершины соединяет не более, чем одно ребро. (Остальные определения данной статьи следуют [1] и [2].) О. Борувка родился в 1899 г. в маленьком городке Ухерске Остров в Моравии в тогдашней АвстроВенгрии. Учился до 1916 г. в гимназии, а затем – в военной школе около Вены. После окончания 1-й Мировой войны вернулся в гимназию и сдал выпускные экзамены. С 1918 по 1922 годы учился в Техническом университете в Брно. Одновременно, (с 1920 года) становится ассистентом в открытом там же в 1920 г. государственном университете им. Т. Масарика. В 1923 г. О. Борувка защищает диссертацию под руководством одного из творцов топологии, на тот момент ещё экстраординарного профессора, Эдуарда Чеха (Eduard Иech: 1893-1960). В 1926 г. О. Борувка публикует две работы [3, 4], решающие некоторую проблему оптимизации. К этой тематике он больше не возвращается. Поездка в 1926-27 годах в Париж, где он сотрудничает с Эли Картаном (Йlie Joseph Cartan: 1869-1951) привела к смещению интересов О. Борувки в сторону дифференциальной геометрии и теории групп. Возвратившись в 1927 г. в Брно он через год защищает вторую диссертацию (хабилитацию), и, получив стипендию фонда Рокфеллера, едет в 1929-31 гг. во Францию и Германию. Итогом изучения теории групп, а особо интенсивно группоидов, была его книжка на чешском языке, первое издание которой вышло только в 1944 году, “Введение в теорию групп”. Это издание имело 80 страниц, а издание 1960 г. уже – 200 страниц. Эта книга была позже переведена на немецкий (1962) и английский (1976) языки. Что касается интереса к дифференциальной геометрии, то О. Борувка уже с 1934 г. стал заниматься дифференциальными преобразованиями 2-го порядка. Английское издание его чешской версии 1953 г. вышло в 1971 г. под названием “Linear dierential transformations of the second order”. В 1953 г. О. Борувка был избран членом-корреспондентом, в 1965 году – действительным членом Чехословацкой Академии Наук [5].

274 Глава 4. История и философия математики и математического образования между некоторыми n пунктами, а решение задачи фактически сводится к нахождению в современных терминах минимального остовного дерева связного графа Бержа без петель с попарно различными весами ребер.

Более того, дается ссылка на работу [4] по решению задачи построения минимальной (по стоимости) электрической сети1, опубликованной в том же 1926 году.

Через 4 года в 1930 году в том же журнале и под тем же названием появилась работа [6] Войтека Ярника2 (Wojtek Jarnik: 1897-1970), в которой давалось иное решение задачи, сформулированной и решенной О. Борувкой.

Итак, какой же алгоритм решения задачи предложил В. Ярник?

Берем произвольную вершину нашего исходного графа. Пусть это будет вершина xi1. Находим вершину, ближайшую к ней, т.е. имеющую ребро с минимальным весом, инцидентную xi1. Пусть это будет xi2. Итак, выделяем ребро [xi1,xi2 ], которое становится начальным “минимальным подграфом”. Далее ищем вершину, ближайшую к ребру [xi1,xi2 ]. Пусть это будет xi3, и эта вершина пусть ближайшая к xi1. Тогда в “минимальный подграф” добавляем ребро [xi3,xi1 ]. И так далее, беря каждый раз новую вершину, ближайшую к уже построенному подграфу. В итоге получим остовное дерево, и можно доказать, что это дерево минимальное среди всех остовных деревьев.

В силу условия (4) результат алгоритма не зависит от выбора начальной вершины. Разница с алгоритмом Прима лишь в том, что в алгоритме Прима мы выбираем вначале минимальное ребро.

Вернемся теперь к алгоритму О. Борувки. Формально алгоритм состоял из 26 шагов. Если следовать буквально, то на первом шаге выбирались “висячие вершины”, т.е. вершины, инцидентные одному ребру и вторые вершины этих ребер. Если таких вершин не было, то выбрав произвольную вершину брали инцидентное ей ребро с минимальным весом. У второй вершины этого ребра также искали инцидентное ей ребро с минимальным весом. Теперь наш подграф имеет три вершины. Вне этого подграфа искали ребро с минимальным весом. Если только одна из вершин этого ребра принадлежала нашему подграфу, то “добавляли” это ребро к нашему подграфу, строя компоненту связности. Если же обе вершины этого ребра принадлежали нашему подграфу, то это ребро отбрасывали. Если обе вершины этого нового ребра были отличны от выбранных нами ранее, то около этого ребра строили новый подграф (=новую компоненту связности). Далее вновь искали ребро с минимальным весом. Если это ребро соединяло разные компоненты связности, то его оставляли. В итоге получали связный подграф с (n-1) ребром (т.е.

остовное дерево) с минимальным весом.

Значительно позже [8] было доказано, что алгоритм Борувки применим не только к графам Бержа(без петель) с попарно разными весами, но и к другим конечным связным неориентированным графам с числом вершин n и числом ребер V. При этом время решения задачи оценивалось как (**) O(nlogV).

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

В. Ярник родился в 1897 году в Праге, учился в Каролинском университете, а по окончании учебы стал работать там же на должности ассистента. В 1923 г. он на один год едет в Гёттинген для совместной работы с Эдмундом Ландау (Edmund Landau: 1877-1938). Возвратившись на свою должность, он в 1927/ учебном году вновь едет в Гёттингенский университет для работы вместе с Э. Ландау. Возвратившись в Прагу, В. Ярник получает должность руководителя кафедры математики Каролинского университета, проработав на этой должности до 1968 года до выхода на пенсию. Две трети из 90 научных работ В. Ярника посвящены теории чисел, главным образом, Гауссовской “проблеме окружности” и диофантовым уравнениям. В 1933-36 годы В. Ярник интенсивно занимался математическим анализом, в основном производной Дини (Ulisse Dini: 1845-1918) и апроксимативной производной непрерывных функций [7].



Наконец, в 1930 г. вышла единственная работа В. Ярника, относящаяся к оптимизационным алгоритмам, в которой фактически построен алгоритм, названный позже (после 1957 г.) алгоритмом Прима.

Одинец В.П. К истории двух знаменитых оптимизационных алгоритмов в теории графов В 1956 г. Джозеф Краскал (Joseph Bernard Kruskal, Jr.: 1928-2010)1 получил решение задачи, поставленной О. Борувкой для случая конечного связного неориентированного графа (без петель) с числом вершин n с помощью следующего алгоритма [9].

1. Выбираем произвольное ребро е1 с минимальным весом.

2. Выбираем последовательно ребра е2,...,еn1 с минимальным весом среди оставшихся, но так, чтобы новое ребро с выбранными ранее не образовывало цикла.

Выбранные ребра и образуют минимальное остовное дерево. Это дерево в общем случае может быть не единственным.

Для практического применения оказался более удобен алгоритм предложенный в 1957 г. [10] Робертом Примом (Robert Cley Prim: 1921)2.

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

Алгоритм Прима был переоткрыт [11] в том же 1957 г. двумя компьютерными специалистами:

Лоберманом и Вейнбергером (H. Loberman & Arnold Weinberger). В 1959 году появилась публикация [12] Эдсгера Дейкстры (Dijkstra Edsger Wybe: 1930-2002), фактически в других терминах повторившего результат Р. Прима. (Заметим, что публикация Р. Прима была тогда малодоступна в Европе.) Заметим, что в промежуток между 1930 годом и 1956 годом, т.е. работами В. Ярника [6] и Д. Краскала [9], появились две работы, в которых ставилась задача внешне похожая на задачу, поставленную О. Борувкой.

Первая работа [13] 1938 г. принадлежит Густаву Шоке (Gustave Choquet: 1915-2006). В этой работе ставилась задача построения фактически минимального остовного дерева с прямолинейными ребрами, вершинами которого были бы заданные населенные пункты на декартовой Д. Краскал родился в 1928 г. в Нью Йорке в семье преуспевающего оптового торговца Джозефа Краскала Старшего. Учился в университетах Чикаго и Принстона. В 1954 г. защитил докторскую диссертацию под руководством Альберта Таккера (Albert William Tucker: 1905-1995) и Роджера Лындона (Roger Conant Lyndon: 1917-1988). Однако, как неоднократно говорил по этому поводу сам Д. Краскал, диссертация не могла бы быть написана, если бы не две его короткие беседы с Полем Эрдёшем (Paul Erdцs: 1913-1996).

Д. Краскал известен не только своим оптимизационным алгоритмом (1956), но глубокими работами в статистике, компьютерных науках и в психометрии. Его старший брат Уильям Краскал (William Kruskal : 1919-2005) известен своими работами по непараметрическим метода исследования гипотез. Другой старший брат Мартин Краскал (Martin David Kruskal: 1925-2006) прославился изучением “сюрреальных” чисел, нашедших применение в вычислительных алгоритмах.

Роберт Прим родился в маленьком городке Sweetwater штата Техас в 1921 г. В 1941 г. он получил степень бакалавра по электро-инженерии Принстонского университета. В 1941-44 гг. он работает инженером в компании General Electric. В 1944-48 гг. он работает вначале инженером, а позже математиком в Лаборатории Военно-морского флота США. Весь 1949 год он работает исследователем в Принстонском университете, и там же в том же 1949 году защищает докторскую диссертацию под руководством Соломона Лефшеца (Solomon Lefschets: 1884-1972), который до 21 года, жил в Москве, и является одним из создателей алгебраической топологии. Позже Р. Прим переходит в BellLabs компании AT&T. Там он знакомится с Д. Краскалом, который работал над простым алгоритмом решения задачи нахождения минимального остовного дерева, что сулило большой экономический эффект при телефонизации населенных пунктов. Решение, найденное Д. Краскалом, было простым, но не удовлетворило Р. Прима, так как при прокладке телефонных сетей “перескакивать” с места на место, что предполагал в общем случае алгоритм Краскала, было неудобно. В 1957 г. Р. Прим предлагает свой алгоритм [10]. Позже в 1958-61 гг. Р. Прим возглавит исследовательскую работу математиков в BellLabs а затем он станет вице-президентом Национальной Лаборатории Сандия – основного подрядчика по созданию систем безопасности министерства энергетики США.

276 Глава 4. История и философия математики и математического образования плоскости. Во второй работе [14] 1951 года пяти вроцлавских математиков: Казимежа Флорека (Kazimierz Florek), Юзефа Лукашевича (Jzef Jukaszewicz: 1927), Хуго Штейнхауза (Hugo Steinhaus: 1887-1972), Юлиана Перкаля (Julian Perkal: 1913-1965), Стефана Зубжицкого (Stefan Zubrzycki: 1927-1968) ставилась та же задача. При этом речь даже не шла о населенных пунктах, а просто о n точках на декартовой плоскости. Интересно, что формально при этом были сформулированы условия (1) и (2) на расстояния между точками. В обеих работах решения опирались на метрические и топологические свойства искомого дерева.



Pages:     | 1 |   ...   | 69 | 70 || 72 | 73 |   ...   | 93 |
 



Похожие работы:

«Издание 3-е, исправленное и дополненное. Лейся, песня, на просторе. (Из кинофильма Семеро смелых) Стихи А. АПСАЛОНА, музыка В. ПУШКОВА. Лейся, песня, на просторе, Не скучай, не плачь, жена, Штурмовать далеко море Посылает нас страна. Курс на берег невидимый, Бьется сердце корабля. Вспоминаю о любимой У послушного руля. Буря, ветер, ураганыТы не страшен, океан: Молодые капитаны Поведут наш караван. Мы не раз отважно дрались, Принимая вызов твой, И с победой возвращались К нашей гавани, домой....»

«А. А. ФОРМОЗОВ ПАМЯТНИКИ ПЕРВОБЫТНОГО ИСКУССТВА НА ТЕРРИТОРИИ СССР Издание второе, дополненное и переработанное ИЗДАТЕЛЬСТВО НАУКА Москва 1980 Ф о р м о з о в А. А. Памятники первобытного искус­ ства на территории СССР. Изд. 2-е, доп. и пер.— М.: Наука, 1980.— 136 с, ил., 0,5 ид,— (Серия Страницы истории нашей Родины). Немало древнейших произведений искусства, созданных людьми эпохи палеолита, мезолита, неоли­ та и бронзового века, найдено на территории нашей страны советскими археологами. В...»

«Библейская Археология Предисловие Несколько лет тому назад доктор Натаниэль Миклем (Nathaniel Micklem) редактор Duckworth’s Studies in Theology попросил меня подготовить книгу по библейской археологии для издававшейся этим издательством серии. Я занялся пересмотром и переделкой неопубликованного и незавершенного труда, начатого мною перед войной. Прежде чем я успел довести работу до половины, стало ясно, что книга будет иметь куда больший объем, чем этого требовали цели издания. Итогом этих...»

«Учебно методический комплекс по курсу ЭКОНОМИЧЕСКАЯ ИСТОРИЯ Издательство СЗАГС 2004 Рассмотрено и утверждено на заседании кафедры 16 июня 2004 г., протокол № 10 Одобрено на заседании учебно методического совета СЗАГС Рекомендовано к изданию редакционно издательским советом СЗАГС Учебно методический комплекс подготовила ст. преп. Васильева Т. В. © СЗАГС, 2004 Выписка из образовательного стандарта ОПД.Ф.06.10. Экономическая история. Становление цивили зации как воспроизводящего хозяйства;...»

«X V — X V I века стали переломными в российской истории. Это было время великих свершений и чудовищных репрессий, расцвета культуры, подъема экономики и бесконечных кровопролитных войн, экономическо­ го кризиса, неисчислимых народных бедствий и страданий, впечатляющих побед и горьких поражений. В начале X V века Русь еще была разделена на враждующие друг с другом феодальные княжества, зависимые от воли золотоордынских ханов и не всегда способные противостоять иноземным вторжениям. На рубеже X V...»

«Хетты Герни О.Р. Книга известного английского востоковеде О.Р. Герни посвящена важнейшим вопросам хеттологии: этнической, политической и социально-экономической истории хеттов, харктерным особенностям права, религии, литературы и искусства. Снабжена послесловием. Хетты (О.Р.Герни) www.NetBook.perm.ru Предисловие Эта небольшая работа была написана по совету проф М. Э. Л. Мэллоуэна. Она представляет собой попытку дать английскому читателю сжатый очерк хеттской истории и цивилизации в пределах,...»

«ЭВЛИЯ ЧЕЛЕБИ КНИГА ПУТЕШЕСТВИЙ СЕЙАХАТНАМЕ КНИГА ПУТЕШЕСТВИЯ ЭВЛИИ ЧЕЛЕБИ КАК ИСТОЧНИК ПО ИСТОРИИ РОССИИ, УКРАИНЫ И МОЛДАВИИ СЕРЕДИНЫ XVII СТОЛЕТИЯ Среди источников, относящихся к истории СССР, особое место занимают известия иностранцев: путешественников, дипломатов и др., имевших возможность в той или иной мере ознакомиться со страной, населяющими ее народами, занятиями и бытом жителей и т. п. Особенностью свидетельств иностранцев о народах нашей страны, ее полководцах и государственных...»

«ТРОПОЮ ПАЛЛАСА Вячеслав Лоскутников МОУ Средняя общеобразовательная школа №38 с углубленным изучением немецкого языка г. Чита, Россия Забайкалье. Удивительный край, вобравший в себя всё многообразие природных красок планеты. Можно много рассказывать о его достопримечательностях. Я очень люблю свой край. Эту любовь мне привила моя семья. Зная историю своей семьи, мне хочется более основательно изучить историю своего края. Но, так как я учусь в школе с углубленным изучением немецкого языка, то...»

«В небе Кировоградщины (часть вторая) Кировоград 2007 2 629.7(09) Б. Чижов. В небе Кировоградщины. Часть вторая. Кировоград, самиздат, 2007. 366с. Фото Ольги Кушнир Об истории авиации родной Кировоградщины пишет директор музейного комплекса Государственной лётной академии Украины Борис Игнатьевич Чижов. Компьютерная вёрстка, 2007 3 Вступление Первая часть этой книги вызвала большой резонанс в авиационных кругах. О ней положительно отозвались газеты Ведомости плюс в обширном интервью автора с...»

«Эксмо; Москва; 2010 ISBN 978-5-699-37901-9 Аннотация В этой книге собраны почти все инструменты системы KPI, которые могут реально работать в российских компаниях. Огромный опыт в разработке комплексных систем мотивации и управления персоналом, мотивации на базе KPI, внедрении стратегического, целевого, бюджетного, процессного и проектного управления позволил автору обобщить практику проведения проектов в российских и западных компаниях и дать читателям самые необходимые инструменты для работы....»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.