Блог FX’а

Что-то к пятому курсу меня все-таки потянуло на изучение алгоритмов… Нет, я не стал читать книги по алгоритмам, пока не стал. Но всякие статьи по алгоритмам и структурам данных стали мне интересны - если я увижу где-то подобную статью, то я скорее всего её прочту, хотя раньше все было наоборот - увидев заголовок типа “Нахождение минимального остовного дерева в графе” я бы 100% прошел мимо.

Так вот, к чему я это - после первой недели учебы я однозначно могу сказать, что идти в магистратуру к нам на специальность стоит, по крайней мере из-за одного предмета -  “Эвристические алгоритмы комбинаторной оптимизации”. Судя по первой лекции - здесь нам будут рассказывать очень интересные и универсальные алгоритмы нахождения приближенного к оптимальному решения всяческих задач. В частности, NP-трудных и NP-полных задач - например, “задача коммивояжёра“, “Bin Packing” или “задача о рюкзаке“. Не знаю, как вас, а меня, например, уже давно интересовала задача оптимальной “упаковки” многоугольников в прямоугольную фигуру. И она решается! Причем добиться достаточно оптимального решения можно гораздо быстрее чем за экспоненциальное время! Правда мы будем рассматривать очень упрощенный вариант, но сам алгоритм решения остается тот же. В общем, магистратурой нашей специальности я очень даже  доволен. :)

И напоследок - учитесь, знания вам ой как пригодятся в будущем.

written by FX Poster \\ tags: algorithms

Да, кстати, всех студентов и школьников поздравляю с началом нового учебного года (поздновато, но такой уж я забывчивый). Не знаю, как вы, а я как-то даже ждал возможности вернуться в родные стены университета для того, чтобы провести здесь еще один год, на этот раз последний, теперь уже для того, чтобы получить диплом магистра по специальности “Программное обеспечение автоматизированных систем” (свой диплом бакалавра я уже “получил” - нам их даже не выдали :( ). Судя по расписанию, семестр обещает быть не очень трудным, но очень интересным. Чего и вам желаю!

written by FX Poster

Через 2 часа 50 минут состоится экзамен, по которому я вполне могу получить двойку… Страшно, блин…

written by FX Poster

Только что 2 часа убил на “простенькую задачку по комбинаторике”, как сказала наша преподаватель по моделированию. Если кто хочет поломать немного мозги, то вот сама задачка (исходного задания у меня нет, так что это моя интерпретация задания):

Бросаем симметричную монетку n раз. Она может упать либо орлом, либо решкой вверх. Найти вероятность выпадения двух решек (ну, или орлов, не суть важно) подряд.

Если перефразировать в более удобный вид, получаем:

Есть массив, состоящий из нулей и единиц, размером в n элементов. Какова вероятность того, что в массиве есть два нуля, стоящие рядом.

Задача просто бешенная, как бы проста она не казалась. У меня ответ получился только через рекурсию, а в конце в нём всплыл еще и дополнительный ряд Фибоначчи:

q(n) = p(n) / (2 ^ n)
p(n)  = 2 * p(n - 1) + f(n - 1)
p(1)  = 0
f(1) = 1, f(2)  = 1, f(3) = 2, ...
f(n) - ряд Фибоначчи
q(n) - конечная вероятность, которую нужно найти

Это просто пипец… Мне вот интересно, что такое “сложненькая” задача, если эта - “простенькая”.

written by FX Poster \\ tags: Комбинаторика, Моделлирование

… можно опять работать в полную силу. :)

Кстати, я, впервые за эти два с половиной года, буду получать повышенную стипендию. :)

written by FX Poster

… сегодня был успешно сдан. Очередная пятерка в зачетке. :)

written by FX Poster

Эх, млин. Список вопросов на выдали, но, судя по тому, что было на консультации (я не был, работал), вопросы будут не эти…  Ладно, посмотрим.

PS. А потом верстать, верстать, верстать, верстать…

PPS. Обьясните мне, бедному и непонимающему студенту, нахрена было делать это! Кто скажет “ну, типа чтобы генерить JS на серверной части” очень советую глянуть в сторону Symfony, а точнее - её JS-helper’ов. Вот в таком есть смысл, а в JQuery-PHP я его не вижу пока что…

written by FX Poster

Достало меня уже всё… Остался последний отчет, который я пишу из последних сил в последний день учебы в этом году…

Вот такое у меня сейчас в отчете родилось:

written by FX Poster

Вот такая у нас учеба:

Кароче слушай, всё заебись как херово знаешь я только что заметил, что сёдня я матерился уже больше чем за последние 3 месяца, а вчера походу почти стока же.
Мне <предмет> завтра здавать на зачёт, а я ещё не садился, плюс сцуко <препод> со своим сцуко дегроидным проектом, плюс я вышу вчера написал и не знаю что она мне там влепит и эт меня напрегает. и <препода> на завтра я никак не успеваю сделать и бля у меня ща взорвётся бошка и плюс:
приехал в 6-6:30
вечера домой и час убил на <друга> - помогал с вышкой
потом поужинал и попытался поспать\нихера не вышло плюс меня вовреммя не подняли
и я не погрелся в ванной, теперь очень злой невыспавшийся и неготовый к зачёту студент пишет тебе сообщение и мысленно посылает этот долбанный универ нах, за то чот в таком состоянии через часов 7 будет сдавать всякую хрень вот

Орфография сохранена. Подчеркнутые слова были мной заменены, на всякий пожарный.

written by FX Poster

Что-то я затянул немного выполнение лабораторных работ некоторых по универу, нужно исправляться. Сегодня решил вернуться ко второй лабе по ООП. Задание таково:

“Разработать объектно-ориентированную библиотеку для работы со структурами данных по одной из нижеперечисленных тем в соответствии с нижеуказанными требованиями. Свойства и методы для классов разработать в соответствии с известными определениями соответствующих структур данных. Составить тесты для проверки работоспособности библиотеки. Составить программу, демонстрирующую возможности разработанной библиотеки.”

Требования - хрен с ними, а вот тема мне попалась интересная: “Сетевые базы данных (ввод/вывод, навигация)”. Когда я это задание читал в первый раз - я впал в ступор. Потом оклемался, но когда видишь такое задание как-то не по себе становится…

Сетевая бд - это бд, в которой для связи записей используются графы (граф, по курсу структур данных, - это сеть). Т.е. здесь, в отличии от иерархических бд, связи получаются “много к многим” (а там - “один ко многим”).

Поговорил немного с преподами о задании, итог получился такой - “нам не нужна универсальная бд, сделай несколько таблиц статических и связывай их”. Говорил действительно немного - минуты полторы, так что кроме фразы выше я ничего особо не услышал. Сегодня решил хоть чего-нибудь напроектировать, чтобы в пятницу показать преподам и убедится, правильно ли я делаю, или нет. Мысля сейчас такая: есть отдельные таблицы (неважно, как представленные) и есть какой-нибудь класс Relation, который их связывает. Собственно, это очень напоминает обычную иерархическую бд (таблица - связующая таблица - таблица), но как это оформлять по другому я пока что не представляю.

Сел за комп, закодил… Получилось такая фигня:

class Masseur : public Record {
public:
    Masseur();
    virtual ~Masseur();
private:
    char* _name;
    char* _surname;
    char* _fathername;
    char* _qualification;
    Date _birthday;
};

class Service : public Record {
public:
    Service();
    virtual ~Service();
private:
    char* _name;
    char* _part;
    int _duration;
    double _price;
};

class MasseurServiceRelation : public Relation {
public:
    MasseurServiceRelation();
    virtual ~MasseurServiceRelation();
private:
    void add(Masseur*, Service*);
    void remove(Masseur*, Service*);
    void remove(Service* service);
    void remove(Masseur* masseur);
};

Сейчас сижу и думаю, правильным ли путем я иду…

PS. А первые две таблицы очень напоминают паттерн ActiveRecord, на правда ли? :)

written by FX Poster \\ tags: C++