.. _estructures-de-dades:

Estructures de Dades
....................

Centrem l'estudi d'`estructures de dades
<https://ca.wikipedia.org/wiki/Estructura_de_dades>`_ conjunts i grafs.


.. _conjunts:

Conjunts
--------

Conceptes
~~~~~~~~~

- `Conjunt
  <https://ca.wikipedia.org/wiki/Conjunt_(estructura_de_dades)>`__,
  operacions (conjunt buit, afegir, eliminar, pertany, es buit?,
  cardinal, unió, intersecció, diferència, subconjunt).

Referències
~~~~~~~~~~~

- Secció `Sets
  <https://docs.python.org/3/tutorial/datastructures.html#sets>`__ de
  *the Python tutorial*.


Exercicis
~~~~~~~~~

.. toctree::
   :glob:
   :maxdepth: 1
	      
   conjunts/*/index
   iteradors/Daus/index
   grafs/Línies_de_metro/index
   recursivitat/Catifa_de_Sierpinski/index

.. _grafs:

Grafs
-----

Conceptes
~~~~~~~~~

- `Graf «matemàtiques» <https://ca.wikipedia.org/wiki/Graf_%28matem%C3%A0tiques%29>`__,
  vèrtex, aresta, adjacents, tipus de grafs (dirigits i simètrics),
  arcs, successors, predecessors, camí, cicle, grau, component.
- `Graf «estructura de dades»
  <https://en.wikipedia.org/wiki/Graph_%28data_structure%29>`__,
  recorregut d'un graf en profunditat i en amplada, arbres d'expansió,
  cicles, camins mínims, components connexes.

Referències
~~~~~~~~~~~

- Capítol 1 del llibre `Grafs: fonaments i algorismes
  <http://cataleg.upc.edu/record=b1089601>`__.
- Biblioteca :doc:`NetworkX <networkx:index>`.

  - Veieu la :doc:`guia <networkx:tutorial>` introductòria a la
    biblioteca.

  - De NetworkX usarem especialment les classes :ref:`Graph
    <networkx:graph>` i :ref:`DiGraph <networkx:digraph>` i els seus
    mètodes, i funcions sobre :doc:`components
    <networkx:reference/algorithms/component>`, :doc:`camins mínims
    <networkx:reference/algorithms/shortest_paths>` i
    :doc:`recorreguts <networkx:reference/algorithms/traversal>`.


Material
~~~~~~~~

- `Notes de classe. Grafs
  <https://www.cs.upc.edu/~tonis/inf/notes-de-classe/grafs/index.html>`__. Antoni
  Soto i Riera.

- `Guió/resum de classe - Estructures de dades <https://www.cs.upc.edu/~marc/Inf2/estructures_de_dades.html>`_. Marc Vigo Anglada.

- `Transparències d'estructura de dades 
  <https://www.cs.upc.edu/~josep/I/ed.pdf>`__, `Grafs <https://www.cs.upc.edu/~josep/I/grafs.pdf>`__, `networkx <https://www.cs.upc.edu/~josep/I/grafsnetworkx.pdf>`__ Josep Vilaplana Pastó.

- Transparències estructures de dades: `part 1  <https://www.cs.upc.edu/~dani/INFO/transpes/grafs-1.pdf>`__, `part 2 <https://www.cs.upc.edu/~dani/INFO/transpes/grafs-2.pdf>`__ . Dani Tost Pardell.

- :download:`Apunts d'estructures de dades (apunts_estdades_dolors.pdf) <grafs/apunts_estdades_dolors.pdf>`. Dolors Ayala Vallespí.


Exercicis
~~~~~~~~~

.. toctree::
   :glob:
   :maxdepth: 1

   grafs/*/index