Я хочу описать историю одного заносчивого и самовлюбленного студента Академического Университета, коим я, конечно, не являюсь, но хорошо представляю его мысли и переживания. Будем называть этого студента, например, Шурик. На момент поступления Шурика в Академический Университет (АУ), согласно его программистскому резюме, он уже был экспертом в области алгоритмов. Он мастерски владел алгоритмом поиска в глубину, знал несколько методов сортировки массивов, и имел представление о двоичном поиске. Естественно, курс алгоритмов его не интересовал совершенно, да и вообще, мало чему можно научить программиста с пятилетним опытом. Программа теоретической информатики АУ его заинтересовала тем, что в темах по известным ему предметам было слишком много неизвестных ему слов. Но это же Питер, там они и бордюр то странным словом называют, вероятно, и для поиска в глубину красивых слов понавыдумывали. Он тщательно изучил слайды и видеозаписи курсов. Оказалось, что существует какая-то там информатика, которой Шурик не владеет в совершенстве. Шурик собрал книги, носки и пять лет опыта, и отправился в Питер на собеседование. Там он встретил людей, которые могут научить чему-то даже программиста с таким опытом. Это все рушило Шурикову картину мира, в которой знание информатики измерялось количеством написанных классов на C#.
Во время учëбы в магистратуре Шурик занимался исследованиями в области схемной сложности и области экспоненциальных алгоритмов. Это действительно очень интересно и, что не менее важно, полезно для поступления в аспирантуру.
На данный момент Шурик является счастливым аспирантом New York University, использует слово «поребрик», и с глубокой благодарностью вспоминает Академический Университет. А кафедра математических и информационных технологий АУ и сейчас ведет набор новых магистрантов, в частности, по направлению «теоретическая информатика».
Сейчас я передаю слово Шурику, который и расскажет об одном своëм исследовании.

Введение.

На данный момент не известно полиномиальных по времени алгоритмов точного решения NP-трудных задач. Более того, специалисты по теории сложности склоняются к варианту, что таких алгоритмов не существует. Однако, NP-трудные задачи часто встречаются в жизни. Одним из способов борьбы с NP-трудными задачами на практике является применение приближенных алгоритмов.

Рассмотрим лучший известный приближенный алгоритм решения задачи о вершинном покрытии.