Рубрика «теоретическая информатика»

Есть проблемы гораздо сложнее, чем NP-Complete - 1

Люди часто сравнивают P и NP в таком духе, что проблемы P простые, а NP — сложные. Но это чрезмерное упрощение. На самом деле проблемы могут быть намного, намного сложнее, чем NP.

В этом смысле можно вспомнить интеллектуально-фантастический триллер Travelling Salesman (Коммивояжёр, 2012) о четырёх математиках, нанятых правительством США для решения самой сложной проблемы в истории информатики — равенства классов сложности P и NP (P versus NP problem). И им это удалось. Чиновник министерства обороны США предлагает за их алгоритм вознаграждение $10 млн. Но сами математики слишком хорошо понимают, какие разрушительные последствия принесёт в мир их открытие. Один из лучших фильмов про математику в истории кинематографа…
Читать полностью »

Мы рады сообщить, что при лаборатории им. Чебышева СПбГУ открывается магистратура по теоретической информатике, которая реализуется при тесном сотрудничестве с Computer Science клубом и при поддержке компаний JetBrains и Яндекс.

Магистратура по теоретической информатике в СПбГУ - 1

Программа обучения включает базовые и углублённые курсы по алгоритмам, сложности вычислений, криптографии, дискретной математике, математической логике, машинному обучению, формальным языкам и автоматам, вычислительной геометрии и многочисленным более специализированным предметам, отражающим современные направления в информатике. Под руководством специалистов по теоретической информатике студенты проводят научные исследования.
Читать полностью »

Конкурс студенческих работ по теоретической информатике и дискретной математике им. Алана Тьюринга - 1
Решили финансово поддержать студентов, которые занимаются теоретическими исследованиями, и организовали конкурс студенческих работ.

Цель конкурса: поощрение авторов лучших студенческих научных работ по теоретической информатике и дискретной математике, стимулирование студентов к научной деятельности.

Организаторы конкурса: Санкт-Петербургский Академический университет, ПОМИ РАН, Computer Science Club.

Участниками конкурса могут стать студенты очной формы обучения (специалисты, бакалавры и магистры) любых российских и зарубежных вузов, имеющие этот статус на 1 апреля года проведения конкурса, свободно владеющие русским языком.

На конкурс принимаются научные работы по теоретической информатике и дискретной математике, написанные на математическом уровне строгости на русском или английском языке. Не требуется, чтобы поданная на конкурс работа была опубликована.Читать полностью »

Опубликован быстрый алгоритм для задачи изоморфизма графов - 1
Эти два графа являются изоморфными

Математик Ласло Бабай (László Babai) с факультета компьютерных наук и математики Чикагского университета представил быстрый новый алгоритм для решения задачи изоморфизма графов — одной из фундаментальных проблем теории сложности вычислений. Алгоритм приводит проблему очень близко к классу P. По мнению некоторых специалистов, это один из самых значительных результатов в теоретической информатике за десятилетие, если не за несколько десятилетий.
Читать полностью »

IT + образование. Еще раз о бакалавриате
Когда я оканчивал школу, мой учитель информатики на последнем уроке говорил следующие слова: «Чем дольше вы будете учиться и чем позже начнете работать, тем на большую зарплату вы сможете рассчитывать». С тех пор много воды утекло, и я успел несколько раз изменить собственное мнение по этому поводу, но в свете последних постов о проблемах образования в IT хотелось бы еще раз обсудить эту тему.

Компаниям, как правило, нужны программисты двух типов. Одни — «рабочие руки», т.е. те, кто умеет хорошо выполнять порученное им задание, и вторые — «рабочие мозги», т.е. те, кто может генерировать новые идеи, предлагать новые подходы, разрабатывать новые направления.
Что касается первой категории, то для того, чтобы в ней работать действительно может хватить пары курсов института и книжек перед сном. Со второй категорией все сложнее… Дело в том, что специалисты этого уровня должны иметь знания шире, чем это требуется для их непосредственной работы.
Вот о том, как готовить специалистов второй категории и хочется поговорить сегодня. И начать с азов — с бакалавриата.
Читать полностью »

Продолжаем рассказывать о нашем опыте построения «самой лучшей магистратуры по Computer Science» =) и интересоваться мнением IT-сообщества. Напомню, что нашей целью было создать магистратуру с сильной программой, в которой не было бы «лишних» курсов. И благодаря сотрудничеству с Академией Современного Программирования и лабораторией математической логики Санкт-Петербургского отделения математического института им. В.А. Стеклова РАН у нас это успешно получилось сделать.

В прошлый раз мы написали о том, как создавалась кафедра и о том, чего нам удалось добиться за 5 лет.

В этом посте мы обсудим, чему нужно учить в магистратуре по Computer Science.
Чему нужно учить в магистратуре по Computer Science?

Читать полностью »

Продолжаем рассказывать о нашем опыте построения «самой лучшей магистратуры по Computer Science» =) и интересоваться мнением IT сообщества. Напомню, что нашей целью было создать магистратуру с сильной программой, в которой не было бы «лишних» курсов.. И благодаря сотрудничеству с Академией Современного Программирования и лабораторией математической логики Санкт-Петербургского отделения математического института им. В.А. Стеклова РАН у нас это успешно получилось сделать.

В прошлый раз мы написали о том, как создавалась кафедра и о том, чего нам удалось добиться за 5 лет.

В этом посте мы обсудим, чему нужно учить в магистратуре по Computer Science.
СПбАУ РАН: чему должны учить в магистратуре по Computer Science?

Читать полностью »

Магистратура Академического университета РАН: делимся опытомКафедра математических и информационных технологий Санкт-Петербургского Академического университета РАН создана в 2008 году. В этом году ей исполняется 5 лет. Настало время подвести промежуточные итоги и поделиться опытом с сообществом.

Мы уже несколько раз писали об этом на хабре. Правда раньше мы ограничивались сухими объявлениями.

Зачем мы решили открыть кафедру?

Читать полностью »

image

В Санкт-Петербурге есть замечательное место, где из программистов делают ученых — теоретиков Computer Science. Это Академический Университет Российской Академии Наук (АУ РАН).

На тот момент, когда я поступила на Теоретическое Отделение кафедры Математических и Информационных Технологий АУ, отделение имело только один выпуск, состоящий из двух человек. Сейчас Академический Университет уже заработал себя прекрасное имя. Его выпускники работают в ведущих компаниях города, он принимает студентов из других городов, обеспечивая их жильем, а платное отделение стоит всего-навсего 10 тыс. рублей в семестр.

Но я хочу рассказать, на своем примере, какие интересные и глубокие проблемы можно исследовать и сколько интересного узнать, если вы станете студентом теоретического отделения.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js