Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Дерек Г. Корнейл
Родившийся( 1942-12-27 )27 декабря 1942 г. (78 лет)
Квебек
Основные интересыТеория графов
Информатика

Дерек Гордон Corneil канадский математик и ученый , профессор , заслуженный информатики в Университете Торонто , а также экспертом в области графовых алгоритмов и теории графов .

Жизнь [ править ]

Когда он заканчивал школу, его учитель английского сказал Корнейлу, что получение степени по математике и физике - плохая идея и что лучшее, на что он может надеяться, - это поступить в технический колледж. Его интерес к информатике начался, когда, будучи студентом Куинс-колледжа, он услышал, что компьютер был куплен компанией по страхованию жизни London Life в Лондоне, Онтарио, где работал его отец. На первом курсе он устроился на летнюю работу в UNIVAC.Mark II в компании. Одной из его основных обязанностей было управление принтером. Вскоре после этого появилась возможность работать программистом в компании, спонсирующей его стипендию в колледже. Это был шанс, которым Корнейл ухватился за то, что ему отказали в аналогичной должности в London Life. Первоначально на его работе произошла путаница, так как его надзиратель подумал, что он знает, как программировать UNIVAC Mark II, и поэтому он легко перейдет к тому же самому с недавно приобретенной компанией IBM машиной. Однако у Корнейла не было предполагаемого опыта программирования. Таким образом, в двухнедельное окно, которое Корнейл получил, чтобы научиться программировать на IBM 1401, он научился писать код с нуля, в значительной степени полагаясь на руководство по эксплуатации. Этот опыт продвинул его дальше, как и ряд проектов, над которыми он работал позже на этой должности. [1]

В 1964 году Корнейл получил степень бакалавра математики и физики в Королевском университете . Изначально он планировал поступить в аспирантуру, прежде чем стать учителем средней школы, но его приняли в новую аспирантуру по информатике в Университете Торонто изменил это. В Университете Торонто Корнейл получил степень магистра, а затем в 1968 году докторскую степень в области компьютерных наук под руководством Кэлвина Готлиба . [2] [3] (Его научным руководителем после получения докторской степени был Яап Зайдель.) Именно в это время Корнейл заинтересовался теорией графов. Со временем он и Готлиб стали хорошими друзьями. После докторантуры в Технологическом университете ЭйндховенаКорнейл вернулся в Торонто в качестве преподавателя в 1970 году. [2] До своего выхода на пенсию в 2010 году [4] Корнейл занимал многие должности в Университете Торонто, в том числе заведующий кафедрой компьютерных наук (с июля 1985 года по июнь 1990 года), Директор исследовательских инициатив факультета искусств и наук (с июля 1991 г. по март 1998 г.) и исполняющий обязанности вице-президента по исследованиям и международным отношениям (с сентября по декабрь 1993 г.). Во время работы в качестве профессора он также был приглашенным профессором в таких университетах, как Университет Британской Колумбии, Университет Саймона Фрейзера, Университет Гренобля и Университет Монпелье.

Работа [ править ]

Корнейл провел свои исследования в области алгоритмической теории графов и теории графов в целом. Автор 49 диссертаций и опубликовал более 100 статей самостоятельно или с соавторами. Эти документы включают:

Доказательство того, что распознавание графов малой древовидной ширины является NP-полным , [5]
Открытие представления cotree для кографов и алгоритмов быстрого распознавания для кографов, [6]
Генерация алгоритмов изоморфизма графов . [7]
Алгоритмические и структурные свойства дополняемых приводимых графов. [8]
Свойства астероидных графов, свободных от троек. [9]
Алгоритм для решения проблемы определения того, является ли граф частичным графом k-дерева. [10]
Результаты, касающиеся теоретических и алгоритмических проблем графов, а также проблем сложности в отношении связующих деревьев . [11]
Объяснение взаимосвязи между шириной дерева и шириной клики. [12]
Определение диаметра ограниченных семейств графов. [13]
Описание структуры трапециевидных графов. [14]

Как почетный профессор Корнейл по-прежнему занимается исследованиями, а также является редактором нескольких публикаций, таких как Ars Combinatoria и SIAM Monographs on Discrete Mathematics and Applications .

Награды [ править ]

Он был введен в должность научного сотрудника Института Филдса в 2004 году [15].

Ссылки [ править ]

  1. ^ http://blogs.technet.com/b/cdnitmanagers/archive/2011/06/13/derek-corneil-renowned-and-esteemed-computer-science-professor-emeritus-university-of-toronto.aspx
  2. ^ а б Биография , Университет Торонто. Проверено 8 февраля 2012 года.
  3. ↑ Дерек Гордон Корнейл в проекте « Математическая генеалогия»
  4. ^ "Дерек Корнейл: уход на пенсию после 40 лет работы в DCS" (PDF) , @DCS , Департамент компьютерных наук Университета Торонто, 1 (3): 8, 2010.
  5. ^ Арнборг, Стефан; Корнейл, Дерек Дж .; Proskurowski, Анджей (1987), "Сложность нахождения вложения в $ K $ -tree", SIAM журнал на алгебраических и дискретных методов , 8 (2): 277-284, DOI : 10,1137 / 0608024 , МР 0881187 .
  6. ^ Корнейл, Д.Г.; Lerchs, H .; Burlingham, Л. Стюарт (1981), "комплемент приводимых граф", Дискретная прикладная математика , 3 (3): 163-174, DOI : 10.1016 / 0166-218X (81) 90013-5 , МР 0619603 .
    - Корнейл, Д.Г.; Perl, Y .; Стюарт, Л. К. (1985), "Линейный алгоритм распознавания для cographs", SIAM журнал по вычислениям , 14 (4): 926-934, DOI : 10,1137 / 0214065 , МР 0807891 .
  7. ^ Корнейл, Д.Г.; Готлиб, CC (1970), "Эффективный алгоритм изоморфизма графов", Журнал ACM , 17 : 51-64, CiteSeerX 10.1.1.453.3730 , DOI : 10,1145 / 321556,321562 , МР 0278977 , S2CID 207720001   .
    - Прочтите, Рональд С .; Corneil, Дерек Г. (1977), "Граф болезнь изоморфизмом", Журнал теории графов , 1 (4): 339-363, DOI : 10.1002 / jgt.3190010410 , МР 0485586 .
  8. ^ Корнейл, Д.Г.; Lerchs, H .; Берлингем, Л. Стюарт (1981). «Дополняем приводимые графы». Дискретная прикладная математика . 3 (3): 163–174. DOI : 10.1016 / 0166-218X (81) 90013-5 .
  9. ^ Корнейл, Дерек G .; Олариу, Стефан; Стюарт, Лорна (1997). «Астероидные тройные свободные графики». Журнал СИАМ по дискретной математике . 10 (3): 399–430. DOI : 10,1137 / S0895480193250125 .
  10. ^ Арнборг, Стефан; Корнейл, Дерек Дж .; Проскуровский, Анджей (1987). «Сложность поиска вложений в ак-дереве». Журнал СИАМ по алгебраическим и дискретным методам . 8 (2): 277–284. DOI : 10.1137 / 0608024 .
  11. ^ Cai, Leizhen; Корнейл, Дерек Г. (1995). «Ключи для деревьев». Журнал СИАМ по дискретной математике . 8 (3): 359–387. DOI : 10.1137 / S0895480192237403 .
  12. ^ Корнейл, Дерек G .; Ротикс, Уди (2005). «О связи ширины клики и ширины дерева». SIAM Journal on Computing . 34 (4): 825–847. DOI : 10.1137 / S0097539701385351 .
  13. ^ Корнейл, Дерек G .; Драган, Федор Ф .; Хабиб, Мишель; Пол, Кристоф (2001). «Определение диаметра на ограниченных семействах графов» (PDF) . Дискретная прикладная математика . 113 (2–3): 143–166. DOI : 10.1016 / S0166-218X (00) 00281-X .
  14. ^ Мерциос, Джордж Б .; Корнейл, Дерек Г. (2011). «Расщепление вершин и распознавание трапециевидных графов» (PDF) . Дискретная прикладная математика . 159 (11): 1131–1147. DOI : 10.1016 / j.dam.2011.03.023 .
  15. ^ Товарищи Института Филдса . Проверено 18 февраля 2012 года.

Внешние ссылки [ править ]

  • Интервью с Корнейлом , Стивеном Ибараки, 13 июня 2011 г.
  • Список публикаций на DBLP