stringtranslate.com

Дерек Корнейл

Дерек Гордон Корнейл — канадский математик и специалист по информатике , почетный профессор компьютерных наук в Университете Торонто , эксперт в области графовых алгоритмов и теории графов .

Жизнь

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

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

Работа

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

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

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

Награды

В 2004 году он был назначен научным сотрудником Института Филдса. [17]

Ссылки

  1. ^ "Дерек Корнейл: известный и уважаемый профессор компьютерных наук, почетный профессор Университета Торонто - Блог канадского ИТ-менеджера - Главная страница сайта - Блоги TechNet". Архивировано из оригинала 2011-06-23 . Получено 2012-02-19 .
  2. ^ ab Биография, Университет Торонто. Получено 1/8 февраля 2012.
  3. ^ Дерек Гордон Корнейл в проекте «Генеалогия математики»
  4. ^ "Дерек Корнейл: выход на пенсию после 40 лет работы в DCS" (PDF) , @DCS , 1 (3), Университет Торонто, кафедра компьютерных наук: 8, 2010.
  5. ^ Арнборг, Стефан; Корнейл, Дерек Г.; Проскуровски, Анджей (1987), «Сложность поиска вложений в $k$-дереве», SIAM Journal on Algebraic and Discrete Methods , 8 (2): 277–284, doi :10.1137/0608024, MR  0881187.
  6. ^ Корнейл, Д.Г.; Лерчс, Х.; Берлингем, Л. Стюарт (1981), «Дополнительные сводимые графы», Дискретная прикладная математика , 3 (3): 163–174, doi :10.1016/0166-218X(81)90013-5, MR  0619603
  7. ^ Корнейл, Д.Г.; Перл, И.; Стюарт, Л.К. (1985), «Линейный алгоритм распознавания кографов», SIAM Journal on Computing , 14 (4): 926–934, doi :10.1137/0214065, MR  0807891.
  8. ^ Корнейл, Д.Г.; Готлиб, К.К. (1970), «Эффективный алгоритм для изоморфизма графов», Журнал ACM , 17 : 51–64, CiteSeerX 10.1.1.453.3730 , doi : 10.1145/321556.321562, MR  0278977, S2CID  207720001 
  9. ^ Рид, Рональд К.; Корнейл, Дерек Г. (1977), «Болезнь изоморфизма графов», Журнал теории графов , 1 (4): 339–363, doi :10.1002/jgt.3190010410, MR  0485586.
  10. ^ Корнейл, Д.Г.; Лерчс, Х.; Берлингхэм, Л.Стюарт (1981). «Дополнительные сводимые графы». Дискретная прикладная математика . 3 (3): 163–174. doi :10.1016/0166-218X(81)90013-5.
  11. ^ Корнейл, Дерек Г.; Олариу, Стефан; Стюарт, Лорна (1997). «Астероидные трипл-свободные графы». Журнал SIAM по дискретной математике . 10 (3): 399–430. doi :10.1137/S0895480193250125.
  12. ^ Арнборг, Стефан; Корнейл, Дерек Г.; Проскуровски, Анджей (1987). «Сложность поиска вложений в ak-дереве». Журнал SIAM по алгебраическим и дискретным методам . 8 (2): 277–284. doi :10.1137/0608024.
  13. ^ Cai, Leizhen; Corneil, Derek G. (1995). «Tree Spanners». Журнал SIAM по дискретной математике . 8 (3): 359–387. doi :10.1137/S0895480192237403.
  14. ^ Корнейл, Дерек Г.; Ротикс, Уди (2005). «О связи между шириной клики и шириной дерева». Журнал SIAM по вычислениям . 34 (4): 825–847. doi :10.1137/S0097539701385351.
  15. ^ Корнейл, Дерек Г.; Драган, Федор Ф.; Хабиб, Мишель; Поль, Кристоф (2001). «Определение диаметра в ограниченных семействах графов» (PDF) . Дискретная прикладная математика . 113 (2–3): 143–166. doi :10.1016/S0166-218X(00)00281-X.
  16. ^ Мерциос, Джордж Б.; Корнейл, Дерек Г. (2011). «Разделение вершин и распознавание трапециевидных графов» (PDF) . Дискретная прикладная математика . 159 (11): 1131–1147. doi :10.1016/j.dam.2011.03.023.
  17. ^ Стипендиаты Института Филдса. Получено 18 февраля 2012 г.

Внешние ссылки