Bøger af Marco T. Morazán

This textbook introduces formal languages and automata theory for upper-level undergraduate or beginning graduate students. While it contains the traditional mathematical development usually employed in computational theory courses, it is also quite different from many of them. Machines, grammars, and algorithms developed as part of a constructive proof are intended to be rendered as programs. The book is divided into four parts that build on each other. Part I reviews fundamental concepts. It introduces programming in FSM and reviews program design. In addition, it reviews essential mathematical background on sets, relations, and reasoning about infinite sets. Part II starts the study of formal languages and automata theory in earnest with regular languages. It first introduces regular expressions and shows how they are used to write programs that generate words in a regular language. Given that regular expressions generate words, it is only natural to ask how a machine can recognize words in a regular language. This leads to the study of deterministic and nondeterministic finite-state machines. Part III starts the exploration of languages that are not regular with context-free languages. It begins with context-free grammars and pushdown automata to generate and recognize context-free languages, and it ends with a discussion of deterministic pushdown automata and illustrates why these automatons are fundamentally different from nondeterministic pushdown automata. Part IV eventually explores languages that are not context-free, known as context-sensitive languages. It starts by discussing the most powerful automaton known to mankind: the Turing machine. It then moves to grammars for context-sensitive languages, and their equivalence with Turing machines is explored. The book ends with a brief chapter introducing complexity theory and explores the question of determining if a solution to a problem is practical.

This textbook presents a systematic methodology for program development by using design recipes, i.e. a series of steps, each with a specific outcome, that takes a problem solver from a problem statement to a working and tested programmed solution. It introduces the reader to generative recursion, heuristic searching, accumulative recursion, tail recursion, iteration, mutation, loops, program correctness, and vectors. It uses video game development to make the content fun while at the same time teaching problem-solving techniques.The book is divided into four parts. Part I presents introductory material on basic problem solving and program design. It starts by reviewing the basic steps of a design recipe using structural recursion on a list. It then proceeds to review code refactoring-a common technique used to refine programs when a better or more elegant way is found to solve a problem-and introduces the reader to randomness. Next, Part II explores a new type of recursion called generative recursion. It navigates the reader through examples involving fractal image generation, efficient sorting, and efficient searching techniques such as binary, depth-first, and breadth-first search. Part III then explores a new type of recursion called accumulative (or accumulator) recursion. Examples used include finding a path in a graph, improving insertion sorting, and list-folding operations. Finally, Part IV explores mutation. To aid the reader in properly sequencing mutations it presents Hoare Logic and program correctness. In addition, it introduces vectors, vector processing, in-place operations, and circular data. Throughout the whole book complexity analysis and empirical experimentation is used to evaluate solutions.This textbook targets undergraduates at all levels as well as graduate students wishing to learn about program design. It details advanced types of recursion, a disciplined approach to the use of mutation, and illustrates the design process by developing a video game exploiting iterative refinement.

This textbook is about systematic problem solving and systematic reasoning using type-driven design. Divide and conquer is the process by which a large problem is broken into two or more smaller problems that are easier to solve and then the solutions for the smaller pieces are combined to create an answer to the problem.