Алан М.Фриз - Alan M. Frieze

Алан М.Фриз (1945 жылы 25 қазанда дүниеге келген Лондон, Англия) - математика ғылымдары кафедрасының профессоры Карнеги Меллон университеті, Питтсбург, АҚШ. Ол бітірді Оксфорд университеті 1966 жылы докторлық диссертациясын докторантурадан қорғады Лондон университеті 1975 жылы. Оның ғылыми қызығушылығы комбинаторика, дискретті оңтайландыру және теориялық информатика. Қазіргі уақытта ол осы бағыттардың ықтимал аспектілеріне назар аударады; атап айтқанда, асимптотикалық қасиеттерін зерттеу кездейсоқ графиктер, алгоритмдердің орташа жағдайлық талдауы және рандомизацияланған алгоритмдер. Оның соңғы жұмысына кірді шамамен санау арқылы көлемді есептеу кездейсоқ серуендер; ішіндегі шеттік жолдарды табу кеңейтетін графиктер, және зерттеу анти-Рэмси теориясы және тұрақтылығы маршруттау алгоритмдері.

Негізгі үлестер

Алан Фриздің қосқан екі маңызды үлесі:

(1) көлемін жуықтауға арналған полиномдық уақыт алгоритмі дөңес денелер

(2) арналған алгоритмдік нұсқа Semerédi тұрақты лемма

Осы екі алгоритм де қысқаша сипатталған болады.

Дөңес денелер көлемін жуықтаудың полиномдық уақыт алгоритмі

Қағаз[1]бірлескен жұмыс болып табылады Мартин Дайер, Алан Фриз және Равиндран Каннан.

Жұмыстың негізгі нәтижесі - ан табу үшін кездейсоқ алгоритм дөңес дененің көлеміне жуықтау жылы - өлшемді эвклид кеңістігі мүшелік ораклдың болуын болжайды. Алгоритм in көпмүшесімен шектелген уақытты алады , өлшемі және .

Алгоритм деп аталатынды күрделі қолдану болып табылады Марков тізбегі Монте-Карло (MCMC) әдісі.Алгоритмнің негізгі схемасы іштен біркелкі іріктеу болып табылады тұратын торды орналастыру арқылы n-өлшемді текшелер және осы текшелер бойынша кездейсоқ серуендеу. Теориясын қолдану арқылыМарков тізбектерін тез араластыру, олар кездейсоқ жаяу жүру үшін біркелкі үлестірім болғанша көпмүшелік уақытты қажет ететіндігін көрсетеді.

Semerédi жүйелілік бөліміне арналған алгоритмдік нұсқа

Бұл қағаз[2]- Алан Фриздің және Равиндран Каннан. Алгоритмдік нұсқасын шығару үшін олар екі лемманы қолданады Semerédi тұрақты лемма табу - тұрақты бөлім.


Лемма 1:
K және түзету және рұқсат етіңіз график болыңыз төбелер. Келіңіздер тең құқылы бөлім сабақтарда . Болжам және . Артық екенін дәлелдеген жұп емес - тұрақты, O (n) уақытында әділетті бөлімді табуға болады (бұл нақтылау болып табылады ) ішіне сыныптар, ең бастысы кардиналдың ерекше класы бар және солай


Лемма 2:
Келіңіздер болуы а матрица , және және позитивті нақты болу.
(а) егер бар болса , осындай , және содан кейін
(b) егер , сонда бар , осындай , және қайда . Сонымен қатар, , көпмүшелік уақытта құруға болады.


Бұл екі лемма теңдеудің келесі алгоритмдік құрылысында біріктірілген Semerédi тұрақты лемма.


[1-қадам] Шыңдарын ерікті түрде бөліңіз әділ бөлімге сабақтармен қайда және демек . белгілеу .
[2-қадам] Әр жұп үшін туралы , есептеу . Егер жұп болса емес тұрақты, содан кейін Lemma 2 арқылы біз олардың жоқтығына дәлел аламыз тұрақты.
[3-қадам] Егер ең көп болса дәлелдемелер шығаратын жұптар тоқтайтын заңдылық. болып табылады тұрақты.
[4-қадам] Lemma 1-ді қайда қолданыңыз , , және алу бірге сыныптар
[5-қадам] Келіңіздер , , және 2-қадамға өтіңіз.

Марапаттар мен марапаттар

Жеке өмір

Фриз үйленген Кэрол Фриз Карнеги Меллон университетінің информатика кафедрасына екі түсіндіру жұмыстарын жүргізеді.[5]

Әдебиеттер тізімі

  1. ^ М.Дайер, А.Фриз және Р.Каннан (1991). «Дөңес денелер көлемін жуықтауға арналған кездейсоқ полиномдық уақыт алгоритмі». ACM журналы. 38 (1). 1-17 бет.
  2. ^ А.Фриз және Р.Каннан (1999). «Семередидің регулярлық бөлімін құрудың қарапайым алгоритмі» (PDF). Электрон. J. тарақ. 6.
  3. ^ Сиам стипендиаттарының 2011 ж
  4. ^ Американдық математикалық қоғам мүшелерінің тізімі, алынған 29 желтоқсан 2012 ж.
  5. ^ Фриз, Кэрол, Жеке, Карнеги Меллон университеті, алынды 20 қаңтар 2019

Сыртқы сілтемелер