MW, praca domowa 2

MW_PD_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Modelowanie wieloagentowe - praca domowa 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Praca składa się z 6 zadań programistycznych, za każde z nich można dostać 2 punkty. W przypadku niektórych z nich możliwe jest uzyskanie większej ilości punktów - jest to oznaczone w poleceniu. Wyjątkiem jest zadanie 6 za które można uzyskać 5 puntów. Rozwiązane zadania należy wysyłać na adres [bpankratz@o2.pl](mailto: bpankratz@o2.pl) w formacie <tt>ipynb</tt> (ten plik uzupełniony o komendy i wyniki wpisane w pozostawione w nim miejsca; obliczenia można wykonać np. na https://juliabox.com) w trakcie trwania semestru (dokładny termin ustalony będzie na ćwiczeniach)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zad 1 (2 p.)\n",
    "\n",
    "Napisz funkcję, która stworzy trójdiagonalną macierz o rozmiarze $n \\times n$ i [postaci](https://en.wikipedia.org/wiki/Toeplitz_matrix):\n",
    "\n",
    "\\begin{bmatrix}\n",
    "4 & -1 & 0 & 0 & \\dots & 0 \\\\\n",
    "-1 &  4 & -1 & 0 & \\dots  & 0 \\\\\n",
    "0 &  -1 & 4  & -1 & \\dots & 0 \\\\\n",
    "\\vdots & \\vdots & \\vdots  & \\vdots & \\ddots & \\vdots \\\\\n",
    "0 & 0 & 0 & 0 & \\dots & 4 \\\\\n",
    "\\end{bmatrix}\n",
    "\n",
    "a następnie dokona dekompozycji [Cholesky'ego](https://en.wikipedia.org/wiki/Cholesky_decomposition) tej macierzy, samodzielnie zaimplementuj algorytm Cholesky'ego.\n",
    "\n",
    "Przetestuj funkcję dla $n = 10$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zad 2 (2 p.)\n",
    "\n",
    "Napisz kod (ponownie bez bibliotek), który rozwiąże równanie postaci $AX=b$, gdzie $b$ jest wektorem jedynek o długości $n$, korzystając przy tym z funkcji z poprzedniego zadania i odpowiedniego [algorytmu](http://mathfaculty.fullerton.edu/mathews/n2003/BackSubstitutionMod.html). Następnie porównaj i pokaż na wykresie czasy wykonania zaproponowanego rozwiązania, rozwiązania opartego na odwracaniu macierzy i wbudowanego w Julię operatora lewego dzielenia macierzy (<tt>A\\b</tt>) dla $n\\in[100,200,…,5000]$.\n",
    "\n",
    "<b>Uwaga:</b> Jeżeli nie udało Ci się rozwiązać zadania 1 stwórz macierz i dokonaj jej dekompozycji za pomocą odpowiednich funkcji z bibliotek dostępnych w Julii. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zad 3 (2 p.)\n",
    "\n",
    "Napisz funkcję, która dla zadanego tekstu (<tt>String</tt>) składającego się z liter alfabetu angielskiego wygeneruje i zwróci w wektorze wszystkie angielskie słowa wykorzystujące znaki z tego ciągu. Przyjmij, że znaki tego ciągu mogą się wielokrotnie powtarzać w jednym słowie. Wykorzystaj do tego słownik dostępny [tutaj](https://github.com/dwyl/english-words). Rozwiązanie powinno ignorować wielkość liter.\n",
    "\n",
    "<b>Dodatkowo:</b> Najszybszy zaproponowany algorytm rozwiązania zadania będzie nagrodzony dodatkowymi dwoma punktami."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zad 4 (2 p.)\n",
    "\n",
    "Zaimplementuj [algortytm Strassena](https://en.wikipedia.org/wiki/Strassen_algorithm) mnożenia dowolnej macierzy kwadratowej rozmiaru $2^n \\times 2^n$. \n",
    "\n",
    "<b>Dodatkowo:</b> Zmodyfikuj kod w taki sposób aby rozwiązywał zadanie dla każdej macierzy postaci $n \\times n$ <b>(2 p)</b>. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zad 5 (2 p.)\n",
    "\n",
    "Napisz funkcję, która dla dowolnego ciągu znaków zwróci jego najdłuższy podciąg będący [palindromem](https://pl.wikipedia.org/wiki/Palindrom). Załóż, że dane wejściowe przyjmują postać wektora znaków, na przykład: <tt>['a','b','c','d']</tt>.\n",
    "\n",
    "<b>Dodatkowo:</b> Zmodyfikuj kod w taki sposób aby dane wejściowe były tekstem, np.: <tt>\"Może jutro ta dama da tortu jeżom\"</tt>, w którym ignorowana jest wielkość liter i spacje (podany tekst jest w całości palindromem) <b>(2 p.)</b>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Zad 6 (5 p.)\n",
    "\n",
    "Inwestor obserwuje cenę pewnego aktywa. Zebrał dane historyczne o tej wycenie w pliku. Interesuje go znalezienie długości najdłuższej sekwencji cen, która jest malejąca. Np dla danych 1, 3, 2, 4, 1 taka długość to 3 (odpowiada sekwencji 3, 2, 1, którą tworzą liczby odpowiednio z pozycji 2, 3 i 5)\n",
    "\n",
    "Długość takiej malejącej sekwencji i czas wykonywania algorytmu dla [tego zbioru](https://drive.google.com/open?id=1niQl1YPtnY02ycm-zSIPou0yiDJ-jNqA).\n",
    "\n",
    "<b>Dodatkowo:</b> Najszybsza implementacja będzie nagrodzona dodatkowymi dwoma punktami "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.6.2",
   "language": "julia",
   "name": "julia-0.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}