• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

overblue

Projecto de informatica que envolva matematica

16 mensagens neste tópico

tenho de desenvolver um projecto que envolva a informatica e a matematica...eu pensei em fazer 1 sistema de votação electronico para a escola e a parte da matematica ia ser as estatisticas no fim mas duvido que seja aceite!alguem tem alguma ideia...?

peço dcp se não tiver colocado o topico no tema correcto!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Dava jeito indicar o nível em que estás...

Podes desenvolver um software de cálculo matemático (de preferência com suporte para cálculo simbólico), que disponibilize operações como resolução de sistemas, resolução de equações não lineares, calculo de derivadas, etc.

Dependendo do nível de dificuldade que desejas, podes ir adicionando funcionalidades, e eventualmente permitir computação paralela/distribuída.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

pois isso secalhar é 1 bocado puxado pk eu inda so tenho o 11º ano de matematica... :-[ ms era 1 projecto bastante potente tnks... eu n tenho grands problemas na com a programação mas a matematica é k diminui o nr de cenas k posso fazer pk ainda so estou a começar a matematica de 12º!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Vocês agora dão o algoritmo Simplex em Matemática, certo?

Implementá-lo dá um bocado de trabalho, mas também devia ser um projecto interessante (isto dependendo do tempo que tens disponível).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O algoritmo simplex resume-se à inversão de uma matriz e multiplicação de uma matriz por um vector coluna. Ok... e umas simplificações matriciais semelhantes à eliminação de gauss. O que quero dizer é que qualquer calculadora com capacidade de calculo matricial é tudo o que é necessario para aplicar o simplex de forma mortalmente simples, talvez não seja grande ideia estar a trabalhar num programa de computador para isso.

Mas isto é o meu ponto de vista... se o objectivo é mesmo implementar multimplicações de matrizes através de operaçõpes basicas, até é boa ideia.

Isto é um pouco na onda do que já anda por aí feito, mas eu acho um trabalho interessante fazeres um programa de computador que calcule o valor de pi com muitas casas decimais. Isso permite-te aplicar conceitos de geometria e compreender a fundo as limitações de um computador enquanto máquina bem como o que é um "tipo de dados", e tambem o que é pi, que a maior parte das pessoas não sabe ao certo o que é.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O algoritmo simplex resume-se à inversão de uma matriz e multiplicação de uma matriz por um vector coluna. Ok... e umas simplificações matriciais semelhantes à eliminação de gauss. O que quero dizer é que qualquer calculadora com capacidade de calculo matricial é tudo o que é necessario para aplicar o simplex de forma mortalmente simples, talvez não seja grande ideia estar a trabalhar num programa de computador para isso.

Mas isto é o meu ponto de vista... se o objectivo é mesmo implementar multimplicações de matrizes através de operaçõpes basicas, até é boa ideia.

Será assim tão simples? Primeiro à a parte da leitura dos dados, depois tens que decidir se aplicas o "primal" ou o "dual", escolher a linha e coluna pivot. Depois, dependendo da quantidade de trabalho que queres ter, podes entrar na parte da reoptimização e análise de sensibilidade, que, se não me engano, já envolve inequações, por exemplo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu também já não me lembro bem, mas penso que envolvia sistemas de equações indeterminados o que descarta a resolução pelo método Gauss e afins para sistemas determinados.

O simplex procura a solução óptima num espaço de soluções possíveis.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu lembro-me de fazer isso na altura que tive Investigação Operacional, a mostrar passo a passo a resolução do Simplex. Não é uma coisa complicada, mas é fixe para entreter. Acho que devo ter isso algures no disco antigo...

Para 12º até parece ser um trabalho porreiro.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu lembro-me de fazer isso na altura que tive Investigação Operacional, a mostrar passo a passo a resolução do Simplex. Não é uma coisa complicada, mas é fixe para entreter. Acho que devo ter isso algures no disco antigo...

Para 12º até parece ser um trabalho porreiro.

podias me arranjar isso?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem tenho que ver primeiro se o tenho, já que se o tiver está no disco antigo e ele neste momento não está ligado ao PC.

Mas não sei se irás perceber o código. Está em Haskell ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sem querer estar a desviar muito o tópico da questão inicial... eu não disse que se usava a eliminação de gauss. Disse que se tinha que por a matriz na 'forma canónica' do simplex. Depois dessa matriz extrai-se a submatriz B^-1, se essa não existir então acham-se os elementos em falta atravez da um sistema matricial simples. E depois daí pode tirar-se o ponto optimo a partir de quaisquer condições iniciais.

Isto com uma ferramenta de calculo matricial são tudo operações basicas. Só envolve calculo da matriz inversa e multiplicação matricial. Mais nada.

Eu lembro-me de quando fiz investigação operacional o problema do simplex era suposstamente o mais dificil e mais demorado. Vi muito pessoal a resolve-lo à mão através de sistemas de equanções pois era como o professor tinha ensinado. Quando eu e um colega meu nos apercebemos que podiamos usar calculadora o tempo de resolução passou de 40 minutos a 5 minutinhos... era só mesmo o trabalho de por os valores na máquina.

Claro que depende um pouco do que se quer do trabalho...  Por exemplo.. um programa para inverter matrizes é engraçado de fazer mesmo que a calculadora faça isso por si propria. Acho que é mais ou menos o caso do simplex.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu lembro-me de quando fiz investigação operacional o problema do simplex era suposstamente o mais dificil e mais demorado. Vi muito pessoal a resolve-lo à mão através de sistemas de equanções pois era como o professor tinha ensinado. Quando eu e um colega meu nos apercebemos que podiamos usar calculadora o tempo de resolução passou de 40 minutos a 5 minutinhos... era só mesmo o trabalho de por os valores na máquina.

Claro que depende um pouco do que se quer do trabalho...  Por exemplo.. um programa para inverter matrizes é engraçado de fazer mesmo que a calculadora faça isso por si propria. Acho que é mais ou menos o caso do simplex.

Lestes o meu post anterior? É que aquilo que tu dizes que é fácil, é só uma das partes do problema. À partida não queremos um programa onde temos que indicar as operações, queremos que ele decida sozinho. Não é apenas implementar as funções necessárias no algoritmo.

E só a leitura dos dados, para ser fácil de usar, já dava bastante trabalho...

E não te esqueças da parte da reoptimização e análise de sensibilidade, que também têm muito que se lhe diga.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu já não toco no simplex desde que fiz Investigação Operacional, e para dizer a verdade não estou a ver grande utilidade deste sem ser aquilo para que foi criado ( forças armadas ) , mas isso já é outra conversa.

Mas rui carlos, eu li o que tu dissseste, mas discordo. A leitura dos dados e equacionalização ( uou! esta palavra existe?? ) do problema são precisamente a parte de um problema que tem que ser feita pela pessoa que o resolve. Isto seja qual for o programa.

Mas para falarmos deste caso em particular.... como sugerias que fosse o programa? que tipo de dados devia aceitar e como, que tipo de resoltados devia dar?

Sinceramente não estou a ver forma mais facil e/ou simples de encarar o problema do que inserir uma matriz numa calculadora, ou num prograa tipo matlab. Se o utilizador não sabe o que é o simplex... aí tambem não está capacitado para interpretar os seus resultados.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Idealmente o programa devia aceitar algo em notação matemática e não na notação de "programador". Algo como:

MAX z = 2 x + 3 y1 - 2 y2
ST x + y = 2
   -y + 2 y1 <= 20
   y1 - y2 <= 0

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois... é o velho dilema entre o óbvio e o pratico. Qual dos dois é mais facil? depende da curva de aprendizagem. Para mim inserir uma matriz na calculadora, matlab, python, etc é incomparavelmente mais rápido e pratico do que inserir essa mescla de caracteres. No entanto para quem não está familiarizado com estas tecnologias pode não valer a pena andar a trepar curvas de aprendizagem que podem ser lentas.

Realmente, se formos pedir a um aluno do secundario para fazer um programa que faça um calculo que não seja possivel obter com a tecnologia actual de forma imediata... ficamos realmente sem opções.

Ok... eu deixo a minha pequena birra... overblue tens aí uma ideia, simplex.

Obrigado pela discussão :)

Mas atenção que implementar uma sintaxe para um principiante tambem não é pera doce.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Bem, liguei o disco antigo e ainda tinha o Simplex. Se te servir de alguma coisa aqui está ele.

Warning: Código muito mal feito...

import Text.ParserCombinators.Parsec
import List
import Maybe
import GHC.IOBase
import System.Environment

data Sinal = Mais | Menos
    deriving (Eq, Show)

data Op = Maior | Menor | Igual
    deriving (Eq, Show)
    
data MaxMin = Max | Min
    deriving (Eq,Show)

data Board = Board ([string], [string], [[Float]])

type Var = (Float, String)
type Restricao = (Op, [Var], Float)
type Restricoes = [Restricao]
type FO = (MaxMin, [Var])

instance Show Board where
    show (Board (left, top, (z:m))) = (mostraTop top) ++ mostraLinha left m ++ mostraFO z

mostraTop = unwords.(++["\n"])

mostraLinha   []     _    = ""
mostraLinha (v:vv) (l:ll) = v ++ " " ++ (unwords $ map show l) ++ "\n" ++ mostraLinha vv ll

mostraFO z = " Z " ++ (unwords $ map show z) ++ "\n"

main = getArgs >>= (parseFromFile geral) . head >>= \p -> print (Board $ fun p) >> return (resolve (fun p))
    where 
    fun (Left s)  = error $ show s
    fun (Right x) = resolve $ aux $ inicializar x
    aux y = unsafePerformIO (print (Board y) >> return y)

-------------------------------------------------------------------------------------------

nspaces = skipMany $ char ' '

sinal :: Parser Sinal
sinal = do { char '+'; return Mais} 
    <|> do { char '-'; return Menos}
    <|> return Mais

decimal =  do{ char '.'; x <- many1 digit; return x}
       <|> return []

numero :: Parser Float
numero = do{ x <- many digit; 
             x' <- decimal;
             return (aux x x')}
    where
    aux :: String -> String -> Float
    aux [] [] = 1.0
    aux [] s2 = read ('.':s2)
    aux s1 [] = read (s1 ++ ".00")
    aux s1 s2 = read (s1 ++ ('.':s2))


var :: Parser (Float, String)
var = try (do{ s <- sinal;
               nspaces;
               n <- numero;
               v <- many1 alphaNum;
               nspaces;
               return (aux s n, v)}) <?> "var"
    where
    aux Mais  = id
    aux Menos = negate

operador =  do{ string "<="; return Menor}
        <|> do{ string ">="; return Maior}
        <|> do{ string "=";  return Igual}

restricao = do{ ll <- many1 var;
                op <- operador;
                nspaces;
                n <- numero;
                spaces;
                return (op, ll, n)}
                
restricoes = many1 restricao 

maxmin = try (do{ string "Max"; return Max})
     <|> do{ string "Min"; return Min}

fo = do{ m <- maxmin;
         r <- many1 var;
         return (m, r)}

geral :: Parser (FO, Restricoes)         
geral = do{ z <- fo;
            spaces;
            rr <- restricoes;
            return (z,rr)}
            
--------------------------------------------------------------------------------------------------------

nVarsAux ll = length ll

listaVars l ll = sort $ nub ((listaVars' l) ++ concat(map fun ll))
    where
    fun (_,x,_) = listaVars' x
    
listaVars' l = map snd l

topVarsMatrix l n = l ++ (createVars '1' n)

createVars :: Char -> Int -> [string]
createVars _ 0 = []
createVars x y = ("_f" ++ [x]) : createVars (succ x) (y-1)

leftVarsMatrixInit :: Int -> [string]
leftVarsMatrixInit n = createVars '1' n

mkMatrix :: [string] -> Char -> Restricoes -> [[Float]]
mkMatrix lVars c  [x]   =  [mkMatrix' lVars c x]
mkMatrix lVars c (x:xs) = (mkMatrix' lVars c x) : mkMatrix lVars (succ c) xs

mkMatrix' :: [string] -> Char -> Restricao -> [Float]
mkMatrix'   []   _    (op, _  ,num) = [swOP op num]
mkMatrix' (v:vv) c  r@(op,vars,num) = fun v (find ((|| v==vAux).(v==).snd) vars) : mkMatrix' vv c r
    where
    vAux = "_f" ++ [c]
    fun _ Nothing  = 0
    fun v (Just x) | (snd x == v) = swOP op $ fst x
                   | otherwise = 1
                   
swOP Maior = negate
swOP Menor = id

mkFOInit :: [string] -> FO -> [Float]
mkFOInit   []       _     = [0]
mkFOInit (v:vv) z@(sig,r) = fun (find ((v==).snd) r) : mkFOInit vv z
    where
    fun Nothing  = 0
    fun (Just x) = swSig sig $ fst x
    swSig Max = negate
    swSig Min = id

inicializar (z,rr) = (varsEsq, varsTodas, matrix)
    where
    n = nVarsAux rr
    varsDecisao = listaVars (snd z) rr
    varsTodas = topVarsMatrix varsDecisao n
    varsEsq = leftVarsMatrixInit n
    z' = mkFOInit varsTodas z
    matrix = z' : mkMatrix varsTodas '1' rr

----------------------------------------------------------------------------------------------------------------

resolve :: ([string], [string], [[Float]]) -> ([string], [string], [[Float]])
resolve b@(left, top, (z:m)) | (minimum z >= 0) || null (filter (>0) racios)= resolve2 b
                             | otherwise = resolve $ aux (troca left linha (top!!col), top, resolve' (z:m) col linha)
    where
    col = fromJust $ elemIndex (minimum z) z
    linha = fromJust $ elemIndex (minimum (filter (>0) racios)) racios
    racios = map (racio. (split (!!col) last)) m
    racio (x,y) = y / x
    aux x = unsafePerformIO (print (Board x) >> return x)
    split f g x = (f x, g x)

troca (l:ll) 0 v = v:ll
troca (l:ll) x v = l : troca ll (x-1) v

resolve' :: [[Float]] -> Int -> Int -> [[Float]]
resolve' a@(z:m) col line = resolve'' a col linha' (line+1)
    where
    linha = (m !! line)
    elemPivot = linha !! col
    linha' = map (/elemPivot) linha

resolve'' :: [[Float]] -> Int -> [Float] -> Int -> [[Float]]
resolve'' [] _ _ _ = []    
resolve'' (_:t) col l 0 = l : resolve'' t col l (-1)
resolve'' (h:t) col l x = zipWith (fun (h !! col)) h l : resolve'' t col l (x-1)
    where
    fun k l1 l2 = l1 - (k*l2)

resolve2 :: ([string], [string], [[Float]]) -> ([string], [string], [[Float]])
resolve2 b@(left, top, (z:m)) | val >= 0 || null (filter (<0) racios) = b
                              | otherwise = resolve2 $ aux (troca left linha (top!!col), top, resolve' (z:m) col linha)
    where
    vals = map last m
    val = minimum $ vals
    linha = fromJust $ elemIndex val vals
    col   = fromJust $ elemIndex (maximum (filter (<0) racios)) racios
    racios = zipWith fun (m!!linha) z
    fun 0 _ = 0
    fun _ 0 = 0
    fun e1 e2 = e2 / e1
    aux x = unsafePerformIO (print (Board x) >> return x)

Aproveitei para testar com o exemplo do Rui Carlos. Reparei que não está aceitar casos de igualdade, mas que é facilmente contornavel e não me apatece estar a mexer no código. Com os ajustes da sintaxe para o programa fica tipo

Max 2x + 3y1 - 2y2

x + y <= 2

x + y >= 2

-y + 2y1 <= 20

y1 - y2 <= 0

O que produz o seguinte output.

simplex teste.txt

x y y1 y2 _f1 _f2 _f3 _f4

_f1 1.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 2.0

_f2 -1.0 -1.0 0.0 0.0 0.0 1.0 0.0 0.0 -2.0

_f3 0.0 -1.0 2.0 0.0 0.0 0.0 1.0 0.0 20.0

_f4 0.0 0.0 1.0 -1.0 0.0 0.0 0.0 1.0 0.0

Z -2.0 0.0 -3.0 2.0 0.0 0.0 0.0 0.0 0.0

x y y1 y2 _f1 _f2 _f3 _f4

_f1 1.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 2.0

_f2 -1.0 -1.0 0.0 0.0 0.0 1.0 0.0 0.0 -2.0

y1 0.0 -0.5 1.0 0.0 0.0 0.0 0.5 0.0 10.0

_f4 0.0 0.5 0.0 -1.0 0.0 0.0 -0.5 1.0 -10.0

Z -2.0 -1.5 0.0 2.0 0.0 0.0 1.5 0.0 30.0

x y y1 y2 _f1 _f2 _f3 _f4

x 1.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 2.0

_f2 0.0 0.0 0.0 0.0 1.0 1.0 0.0 0.0 0.0

y1 0.0 -0.5 1.0 0.0 0.0 0.0 0.5 0.0 10.0

_f4 0.0 0.5 0.0 -1.0 0.0 0.0 -0.5 1.0 -10.0

Z 0.0 0.5 0.0 2.0 2.0 0.0 1.5 0.0 34.0

x y y1 y2 _f1 _f2 _f3 _f4

x 1.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 2.0

_f2 0.0 0.0 0.0 0.0 1.0 1.0 0.0 0.0 0.0

y1 0.0 -0.5 1.0 0.0 0.0 0.0 0.5 0.0 10.0

y2 -0.0 -0.5 -0.0 1.0 -0.0 -0.0 0.5 -1.0 10.0

Z 0.0 1.5 0.0 0.0 2.0 0.0 0.5 2.0 14.0

x y y1 y2 _f1 _f2 _f3 _f4

x 1.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 2.0

_f2 0.0 0.0 0.0 0.0 1.0 1.0 0.0 0.0 0.0

y1 0.0 -0.5 1.0 0.0 0.0 0.0 0.5 0.0 10.0

y2 -0.0 -0.5 -0.0 1.0 -0.0 -0.0 0.5 -1.0 10.0

Z 0.0 1.5 0.0 0.0 2.0 0.0 0.5 2.0 14.0

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora