Introdução concisa a algoritmos para matemáticos

Estou procurando um texto introdutório conciso sobre algoritmos com uma teoria de alta razãoDeveria começar do início, mas depois progredir rapidamente, sem gastar muito tempo com exemplos do mundo real, técnicas elementares de prova, etc. Como matemático de pesquisa, tenho uma sólida formação em matemática que felizmente emprego para entender formalismos e provas condensadas, por exemplo .

Existem tais textos? Alguma recomendação?

Eu gosto muito deste livro:

Sanjoy Dasgupta, Christos Papadimitriou e Umesh Vazirani: Algoritmos
Publicado por McGraw-Hill 2007.

Não calculo sua proporção sugerida, mas acho que você também vai gostar :)

Jeff Erickson não dirá isso sozinho, mas suas notas de aula on-line estão entre as melhores disponíveis para cobrir os conceitos básicos de design de algoritmos em um nível que não apadrinha o leitor. Eu os uso na minha classe de algoritmos de graduação e, para um matemático de pesquisa, essas notas transmitem o tipo (e o nível) certo de intuição, permitindo que você preencha os detalhes facilmente.

" A arte da programação de computadores " de Knuth provavelmente seria o livro com a maior proporção.

Se você quer um livro mais estilo livro, então " Introdução aos Algoritmos " de Cormen, Leiserson, Rivest e Stein seria minha sugestão para um matemático.

Há também muitas notas de aula e alguns Wikilivros sobre algoritmos.

Design de algoritmo de Kleinberg Tardos Este livro ajuda a desenvolver um entendimento concreto de como projetar bons algoritmos e falar sobre sua correção e eficiência. (Eu estudei isso no meu primeiro ano na faculdade, muito legível)

Para obter uma cópia / anotações / referências de palestras on-line (como sugerido por Suresh Venkat), consulte as anotações de Jeff Erikson . Eles são realmente incríveis!

Eu iria para Otimização Combinatória: Teoria e Algoritmos - Korte & Vygen . Você fornecerá uma boa visão geral dos algoritmos, com foco constante na otimização. Este livro é destinado a pessoas com uma forte inclinação matemática IMHO.

Isso iria bem com os algoritmos: Dasgupta e Papdimitrou, acredito.

Eu escrevi uma disposição para o curso de algoritmos que participei. Seu propósito era exatamente isso; para ser uma versão concisa dos tópicos mais importantes abordados em nossa caixa de texto (que era o CLRS). Estou relutante em publicá-lo no Scribd.com ou em qualquer outro lugar até ter examinado o documento minuciosamente e estar satisfeito com seu conteúdo, mas uma cópia de trabalho pode ser obtida em https://github.com/CasperBHansen/DIKU_AD_2013/ . Para lê-lo, você precisará saber como criar o documento pdf a partir da fonte LaTeX, para que serve o repositório. O documento em si tem apenas 65 páginas.

Uma cópia mais antiga pode ser baixada diretamente do meu site em http://casperbhansen.dk/files/ad-disposition.pdf - isso obviamente contém mais erros de digitação, que foram corrigidos desde então.

Ele contém vários erros de digitação porque foi escrito durante apenas alguns dias, enquanto passava por outro exame e, obviamente, me preparando para o exame de algoritmos praticando provas, e ainda tenho que corrigir os erros de digitação e erros, pois tenho estado muito ocupado desde então. Mas tenho certeza de que qualquer pessoa que o leia reconhecerá os erros facilmente, pois geralmente estão em contradição com o texto ou as fórmulas que o acompanham, portanto é fácil descobrir isso sempre que ocorre um erro de digitação.

Espero que possa ajudá-lo a começar.

Aqui estão duas outras referências que podem ser úteis.

• Algoritmos de Sedgewick você disse "introdutório"; esse livro às vezes é usado nas aulas de graduação em ciências da computação, embora possa ser usado em algumas aulas de pós-graduação. Sedgewick tem outras referências muito técnicas no TCS e parte desse estilo matemático é refletida nos algoritmos e é geralmente um estilo sucinto. a cobertura é muito central para (T) CS (mas não tanto em áreas avançadas). também escreveu "influências" que ele fez sua tese de doutorado sob Knuth.

• Computadores e intratabilidade, um guia para a teoria da completude NP, uma referência mais antiga, mas ainda muito relevante. concentra-se na completude da PN, é claro, mas de várias maneiras "é onde está a maior parte da ação". o escopo é amplo e provavelmente será atraente para os matemáticos, pois é focado em muitos objetos matemáticos, como gráficos etc., e observe que há uma seção sobre teoria dos números. como afirma a wikipedia

O livro está desatualizado em alguns aspectos, uma vez que não cobre desenvolvimentos mais recentes, como o teorema do PCP. Ainda está impresso e é considerado um clássico: em um estudo de 2006, o mecanismo de busca CiteSeer listou o livro como a referência mais citada na literatura sobre ciência da computação. [3]

$1990$

tente Enciclopédia concisa de ciência da computação , Wiley. infelizmente, um índice completo / completo desta referência não parece estar disponível na web [uma omissão um tanto incomum hoje em dia, talvez Wiley possa corrigir isso a pedido], mas o índice completo parece ser navegável na amazon. possui uma cobertura muito mais ampla que o TCS, como conceitos de hardware etc., mas parece cobrir partes significativas do TCS, por exemplo:

• Informação e Dados
• Programas
• Matemática da Computação
• Teoria da Computação
• Metodologias
• Aplicações

é uma versão abreviada de 902pp da enciclopédia completa, Encyclopedia of Computer Science, 4ª Edição , 2064pp