to post messages and comments.

← All posts tagged CS

О, годнота в cs-клубе:

1. Семинар по параметризованным алгоритмам.
2. Вычислительная геометрия.
3. Параллельное программирование.
4. Суффиксные деревья: новые идеи и открытые проблемы.
5. Визуализация графов.

compsciclub.ru

Сам хочу сходить посмотреть на вычислительную геометрию и если хватит времени на параллельное программирование.
any1?

Значит как оно в приложении к CS? Берется уже существующий язык, ну который дан, который успешен, который популярен. Ну, не знаю, пусть будет джава как конкретный пример. Мы вполне можем писать на джаве и иметь профит — но вот нам мало, по-этому мы берем какой-то формализм и описываем на нем джаву, весь ее стандарт, со всеми гофовскими паттернами и прочей хренью (но такого формализма нет, беда), причем полностью описываем, безо всяких там «подмножеств», понятное дело. Потом смотрим, и внезапно оказывается, что язык удовлетворяет какому-то свойству Х, которого мы не ожидали! И, оказывается, на нем можно делать какое-то Y, которое мы, читая стандарт языка, и не думали, что можно! Вот это и называется практическим результатом.

Если же берется какой-то готовый язык типа агды там, петуха или идриса, который изначально заточен под определенную формализацию — то тут никакого профита не будет, понятное дело, все, где написано про зависимые типы и всякие агды — это не наука, это бестолковая херня. Ну просто господа, которые занимаются CS, не могут осилить настоящие задачи, а потому переливают из пустое в порожнее — я их в этом понимаю, конечно. Статьи, диссеры, гранты — все это нахаляву, безо всякого труда, сложность работ на уровне средней школы. Кто не соблазнится? Но вот тех людей, которые это читают, нахваливают и просят еще — я понять не могу.

linux.org.ru

Годно:
Сопрамат, тащем-то бесмысленная хуйня для программиста, если он не пишет CAD-ов, как и навык аналитического взятия интегралов. Просто программа образования не менялась с революции и то, что сейчас выходит из вузов — не программисты, а полное говно. Одно повсеместное использование Джавы и С++ и незнание теории категорий, теории типов, конструктивной математики, комбинаторного и лямбда-исчисления (включая типизированные варианты до исчисления конструкций) большинством программистов говорит о том, что CS в рашке нет. Берите интегралы дальше, ага, вы ведь инженеры, инженеры обязаны брать интегралы, интегралы сами не возьмутся.

Лучшие препринты статей по алгоритмам за 2011 год:

* Решение проблем связности, параметризованных шириной дерева за single EXP time. arxiv.org

* Уникальные оценки выполнимости (SAT) для алгоритма PPSZ действительны в общем случае. arxiv.org

* Константа Гротендика строго меньше оценки Кирвина. arxiv.org

* Субэкспоненциальный параметризированный алгоритм для минимального заполнения. arxiv.org

* Циклы и треугольники с минимальным весом: эквивалентности и алгоритмы. arxiv.org

* О сливающейся персисентость для структур данных. arxiv.org

* Распознавание круговых графов за O(m+n) α(n + m). arxiv.org

* Максимальный поток со множеством стоков и истоков в планарных оргафах за почти-линейное время. arxiv.org

* Вычисление совершенных паросочетаний со скоростью алгоритма Райзера. arxiv.org

* 13/9 аппроксимация для геометрической задачи коммивояжера. arxiv.org

Перевел как сумел, оригинал там -> 11011110.livejournal.com

Раз уж такое дело, то какие прочитанные и осиленные вами книги по вычислимости (computability) насоветуете?
Нагуглил:
* Rogers — Theory of recursive functions and effective computability
* Nigel Cutland — An Introduction To Recursive Function Theory

Еще у меня где-то была книжка Манина "Вычислимое и невычислимое".

Книга Роджерса кажется обстоятельной и большой, так что вероятность того, что я ее прочитаю до конца — меньше.

?

Нарыл тут на сайте лекториума интересные (мне) курсы видео-лекций.

* Линейное программирование
lektorium.tv

* Рассказы о теории чисел, алгебраической геометрии и гомотопической топологии
lektorium.tv

* Десятая проблема Гильберта. Решение и применения в информатике
lektorium.tv

* Алгоритмы для NP-трудных задач
lektorium.tv

* Эффективные алгоритмы
lektorium.tv

* Graph Algorithms
lektorium.tv

* Структурная теория сложности
lektorium.tv

* Параметризованные алгоритмы
lektorium.tv

* Проблема изоморфизма графов
lektorium.tv

Где-то на просторах интернета слышал, что нет ничего хуже, чем смотреть видео-лекции для изучения математики. Как у тебя, жуйк? Что приносит больше пользы? Чтение книг, решение задач?