Finite State Morphology Overview
Finite State Morphology is a detailed study of word formation processes, including inflection, derivation, and compounding. It covers concepts like word forms, roots, affixes, and morphemes with examples from computational morphology. This study explores how regular expressions are converted into finite state automata and provides insights into computational analysis of word forms and their morphosyntactic properties.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Salahadden College of Science Salahadden University College of Science 4 4th University- - Erbil Erbil Computer Department th Stage Computer Department Stage CS CS Batch Batch DESIGN AND ANALYSIS OF ALGORITHMS Lecture -1 by Kanar Y. Qader 2021-2022
Lecture Outlines What is an algorithm? Design and Analysis of Algorithms What is a program? Pseudocode The characteristics of an algorithm Attributes of Algorithms Choice of algorithms Kinds of analyses Fundamentals of the Analysis of Algorithm Efficiency Complexity Types of Notations for Time Complexity Understanding Notations of Time Complexity with Example
What is an algorithm? -An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time. -An algorithm is a finite sequence of well-defined operations that halts in a finite amount of time.
What is Algorithm?. Con. The word algorithm comes from the name of a Persian mathematician Abu Ja far Mohammed ibn-i Musa al Khowarizmi. Algorithm is not equal to Program! is a tool for solving problem. refers to a special method for solution of a problem. Pseudocode .
Design and Analysis of Algorithms Analysis: predict the cost of an algorithm in terms of resources and performance Design: design algorithms which minimize the cost
Informal definition of an algorithm used in a computer . problem Algorithm
What is a program? A program is the expression of an algorithm in a programming language a set of instructions which the computer will follow to solve a problem
8 The Problem-solving Process Analysis Problem specification Design Algorithm Implementation Program Compilation Executable (solution)
Pseudocode: We introduce a pseudocode to show how we shall specify the algorithms. Example of pseudocode:
The characteristics of an algorithm are: Precision the steps are precisely stated. Uniqueness results of each step are uniquely defined and only depend on the input and the result of the preceding steps. Finiteness the algorithm stops after a finite number of instructions are executed. Input the algorithm receives input. - Input precession . Output the algorithm produces output. - output precession . Generality the algorithm applies to a set of inputs.
Attributes of Algorithms Correctness Give a correct solution to the problem Efficiency Time Space most important Clarity program maintenance Elegance
Kinds of analyses Worst-case: (usually) T(n) = maximum time of algorithm on any input of size n. Average-case: (sometimes) T(n) = expected time of algorithm over all inputs of size n. Need assumption of statistical distribution of inputs. Best-case: Cheat with a slow algorithm that works fast on some input.
Fundamentals of the Analysis of Algorithm Efficiency The Analysis Framework Time efficiency, also called time complexity, represents the amount of time required by the algorithm to run to completion. Time grows linearly as the input size increases. Space efficiency, also called space complexity, refers to the amount of memory units required by the algorithm in addition to the space needed for its input and output.
Complexity Complexity means computational complexity . computational complexity is a characterization of the time or space requirements for solving a problem by a particular algorithm. Lesser the complexity better an algorithm.
Complexity While measuring the time complexity of an algorithm , we concentrate on developing only the frequency count for all key statements(statements that are important and are the basic instructions of an algorithm). This is because , it is difficult to get reliable timing figure because of clock limitations and the multiprogramming or the sharing environment.
Understanding Notations of Time Complexity with Example O(expression) is the set of functions that grow slower than or at the same rate as expression. It indicates the maximum required by an algorithm for all input values. It represents the worst case of an algorithm's time complexity. Omega(expression) is the set of functions that grow faster than or at the same rate as expression. It indicates the minimum time required by an algorithm for all input values. It represents the best case of an algorithm's time complexity. Theta(expression) consist of all the functions that lie in both O(expression) and Omega(expression). It indicates the average bound of an algorithm. It represents the average case of an algorithm's time complexity.
Types of Notations for Time Complexity any series of signs or symbols used to represent quantities or elements in a specialized system, such as music or mathematics. Now we will discuss and understand the various notations used for Time Complexity. Big Oh denotes "fewer than or the same as" <expression> iterations. Big Omega denotes "more than or the same as" <expression> iterations. Big Theta denotes "the same as" <expression> iterations. Little Oh denotes "fewer than" <expression> iterations. Little Omega denotes "more than" <expression> iterations.
