Дерек Корнейл - Derek Corneil

Дерек Г. Корнейл
Родившийся (1942-12-27) 27 декабря 1942 г. (возраст 77)
Квебек
Основные интересы
Теория графов
Информатика

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

Жизнь

Когда он заканчивал школу, его учитель английского сказал Корнейлу, что получение степени по математике и физике - плохая идея и что лучшее, на что он может надеяться, - это поступить в технический колледж. Его интерес к информатике начался, когда, будучи студентом Куинс-колледжа, он услышал, что компьютер был куплен компанией по страхованию жизни 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 статей самостоятельно или с соавторами. Эти документы включают:

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

Как профессор заслуженный, Корнейл по-прежнему занимается исследованиями, а также является редактором нескольких публикаций, таких как Ars Combinatoria и Монографии SIAM по дискретной математике и приложениям.

Награды

Он был введен в должность Сотрудник Института Филдса в 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. ^ Арнборг, Стефан; Корнейл, Дерек Дж .; Проскуровский, Анджей (1987), "Сложность нахождения вложений в $ k $ -дерево", Журнал SIAM по алгебраическим и дискретным методам, 8 (2): 277–284, Дои:10.1137/0608024, МИСТЕР  0881187.
  6. ^ Corneil, D.G .; Lerchs, H .; Берлингем, Л. Стюарт (1981), "Приводимые с дополнением графы", Дискретная прикладная математика, 3 (3): 163–174, Дои:10.1016 / 0166-218X (81) 90013-5, МИСТЕР  0619603.
    - Corneil, D.G .; Perl, Y .; Стюарт, Л. К. (1985), "Алгоритм линейного распознавания для кографов", SIAM Журнал по вычислениям, 14 (4): 926–934, Дои:10.1137/0214065, МИСТЕР  0807891.
  7. ^ Corneil, D.G .; Готлиб, К. С. (1970), "Эффективный алгоритм для изоморфизма графов", Журнал ACM, 17: 51–64, CiteSeerX  10.1.1.453.3730, Дои:10.1145/321556.321562, МИСТЕР  0278977, S2CID  207720001.
    - Прочтите, Рональд С.; Корнейл, Дерек Г. (1977), "Болезнь изоморфизма графов", Журнал теории графов, 1 (4): 339–363, Дои:10.1002 / jgt.3190010410, МИСТЕР  0485586.
  8. ^ Corneil, D.G .; Lerchs, H .; Берлингем, Л. Стюарт (1981). «Дополняем приводимые графы». Дискретная прикладная математика. 3 (3): 163–174. Дои:10.1016 / 0166-218X (81) 90013-5.
  9. ^ Корнейл, Дерек Дж .; Олариу, Стефан; Стюарт, Лорна (1997). «Астероидные тройные свободные графики». Журнал SIAM по дискретной математике. 10 (3): 399–430. Дои:10.1137 / S0895480193250125.
  10. ^ Арнборг, Стефан; Корнейл, Дерек Дж .; Проскуровский, Анджей (1987). «Сложность поиска вложений в k-дереве». Журнал SIAM по алгебраическим и дискретным методам. 8 (2): 277–284. Дои:10.1137/0608024.
  11. ^ Цай, Лейчжэнь; Корнейл, Дерек Г. (1995). «Ключи для деревьев». Журнал SIAM по дискретной математике. 8 (3): 359–387. Дои:10.1137 / S0895480192237403.
  12. ^ Корнейл, Дерек Дж .; Ротикс, Уди (2005). «О соотношении ширины клики и ширины дерева». SIAM Журнал по вычислениям. 34 (4): 825–847. Дои:10.1137 / S0097539701385351.
  13. ^ Корнейл, Дерек Дж .; Драган, Федор Ф .; Хабиб, Мишель; Пол, Кристоф (2001). «Определение диаметра на ограниченных семействах графов» (PDF). Дискретная прикладная математика. 113 (2–3): 143–166. Дои:10.1016 / S0166-218X (00) 00281-X.
  14. ^ Мерциос, Джордж Б .; Корнейл, Дерек Г. (2011). «Расщепление вершин и распознавание графов трапеций» (PDF). Дискретная прикладная математика. 159 (11): 1131–1147. Дои:10.1016 / j.dam.2011.03.023.
  15. ^ Стипендиаты Института Филдса. Проверено 18 февраля 2012 года.

внешняя ссылка