Шмуэль Галь
Шмуэль Галь (англ. Shmuel Gal, ивр. שמואל גל) — израильский математик, профессор статистики Хайфского университета[1]
Биография[править]
Родился в 1940 году.
В 1962 году Галь с отличием окончил степень магистра математики в Еврейском университете в Иерусалиме, работая над стохастическим приближением под руководством Х. Кастан.
В 1972 году защитил там докторскую диссертацию на тему «Минимаксное решение некоторых поисковых задач» под руководством Арье Дворецкого.
В 1965-1973 годах работал старшим математиком в IAI.
В 1970–1973 годах преподавал в качестве преподавателя на кафедре статистики Тель-Авивского университета, а в 1973–1975 годах был старшим преподавателем в этой области в Хайфском университете.
В 1977–1978 годах работал в качестве приглашенного исследователя в IBM в Исследовательском центре Уотсона в Йорктаун-Хайтс.
В 1981–1990 годах работал преподавателем в Технионе.
В 1973–1997 годах работал в IBM Israel.
В 1994 году был назначен профессором статистики Хайфского университета. В 1995-1998 годах занимал должность начальника управления статистики.
Вклад в науку[править]
Разработал метод точных таблиц Гала для компьютерной оценки элементарных функций.
Совместно с Цви Йехудаем разработал в 1993 году новый алгоритм сортировки, который используется IBM.
Работал над проблемами рандеву со своими коллегами Стивом Альперном , Виком Бастоном и Джоном Ховардом.
Решение игры Принцесса и Чудовище[править]
В теории игр Принцесса и Чудовище — это игра преследования, в которой два игрока играют в некоторой области. Разработана Руфусом Айзексом и опубликована в его книге Дифференциальные игры (1965) в следующем виде: «Монстр ищет принцессу, потраченное на поиск время является ценой игры. Оба находятся в совершенно тёмном помещении (любой формы), но оба знают его границы. Найти принцессу означает, что расстояние между принцессой и монстром оказывается в пределах радиуса захвата, который должен быть относительно мал по отношению к размерам помещения. Монстр достаточно разумен и движется с известной скоростью. Принцессе разрешается полная свобода движения».
Эта игра оставалась не решённой, пока не была решена Галом в конце 1970-х годов. Его оптимальная стратегия для принцессы следующая: принцесса переходит в случайную точку помещения и ждёт в этой точке некоторый интервал времени, не слишком короткий и не слишком длинный. Затем принцесса переходит в другую (независимую) случайную точку и так далее. Для монстра предлагается оптимальная стратегия поиска, в которой всё пространство помещения делится на много мелких прямоугольников. Монстр выбирает прямоугольник случайно и ищет некоторым образом вокруг, затем выбирает случайно и независимо другой прямоугольник, и так далее.