Scribd Logo
Upload

Welcome to Scribd!

  • 77 views

    Essential Thinking. Introduction To Problem Solving: Antoni Lig Eza

    Uploaded by

    Teklit Berihu
    This document outlines the contents and goals of a lecture on essential thinking and problem solving. It discusses using examples to improve analytical thinking and introduce tools like Prolog for knowledge representation and problem solving. The lecture aims to demonstrate intelligent thinking and establish foundations for future learning. It will cover taxonomies of problems and methods, as well as specific techniques like search strategies, inference methods, and handling inconsistencies. The content will be taught through examples, analysis, and questions to encourage independent thinking.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Essential Thinking. Introduction To Problem Solving: Antoni Lig Eza

    Uploaded by

    Teklit Berihu
    77 views26 pages
    This document outlines the contents and goals of a lecture on essential thinking and problem solving. It discusses using examples to improve analytical thinking and introduce tools like Prolog for knowledge representation and problem solving. The lecture aims to demonstrate intelligent thinking and establish foundations for future learning. It will cover taxonomies of problems and methods, as well as specific techniques like search strategies, inference methods, and handling inconsistencies. The content will be taught through examples, analysis, and questions to encourage independent thinking.

    Original Description:

    this is a book on essential thinking

    Original Title

    Essential Thinking Intro

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document outlines the contents and goals of a lecture on essential thinking and problem solving. It discusses using examples to improve analytical thinking and introduce tools like Prolog for knowledge representation and problem solving. The lecture aims to demonstrate intelligent thinking and establish foundations for future learning. It will cover taxonomies of problems and methods, as well as specific techniques like search strategies, inference methods, and handling inconsistencies. The content will be taught through examples, analysis, and questions to encourage independent thinking.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    77 views26 pages

    Essential Thinking. Introduction To Problem Solving: Antoni Lig Eza

    Uploaded by

    Teklit Berihu
    This document outlines the contents and goals of a lecture on essential thinking and problem solving. It discusses using examples to improve analytical thinking and introduce tools like Prolog for knowledge representation and problem solving. The lecture aims to demonstrate intelligent thinking and establish foundations for future learning. It will cover taxonomies of problems and methods, as well as specific techniques like search strategies, inference methods, and handling inconsistencies. The content will be taught through examples, analysis, and questions to encourage independent thinking.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 26

    Essential Thinking.

    Introduction to Problem Solving


    Antoni Ligeza

    Faculty of EEACSE Department of Automatics AGH2011 Krakw, Poland

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    1 / 26

    Outline
    1

    References, What is Worth Learning, Assumptions Introduction: Some Essential Questions Some First Examples Aims and Methods Further Problem Characteristics Three Further Example Problems Plan to be developed Prolog
    A Ligeza (AGH-UST) Essential Thinking 2011 2 / 26

    References
    1

    Stuart J. Russel, Peter Norvig: Articial Intelligence. A Modern Approach. Third Edition. Pearson, Prentice Hall, Boston, 2010. http://aima.cs.berkeley.edu/. Ivan Bratko: Prolog Programming for Articial Intelligence. Fourth Edition, 2011. Pearson, Addison Wesley, 2012. http: //www.pearsoned.co.uk/HigherEducation/Booksby/Bratko/ Frank van Harmelen, Vladimir Lifschitz, Bruce Porter (Eds.): Handbook of Knowledge Representation. Elsevier B.V., Amsterdam, 2008. Michael Negnevitsky: Articial Intelligence. A Guide to Intelligent Systems. Addison-Wesley, Pearson Education Limited, Harlow, England, 2002. Adrian A. Hopgood: Intelligent Systems for Engineers and Scientists. CRC Press, Boca Raton, 2001. Joseph C. Giarratano, Gary D. Riley: Expert Systems. Principles and Programming. Fourth Edition, Thomson Course Technology, 2005.
    A Ligeza (AGH-UST) Essential Thinking 2011 3 / 26

    References
    1

    George Polya: How to Solve it?. Princeton University Press, 1945; PWN 1993. http://en.wikipedia.org/wiki/How_to_Solve_It. John Mason, Leone Burton, Kaye Stacey: Thinking Mathematically. Addison-Wesley, 1985; WSiP, 2005. Mordechai Ben-Ari: Mathematical Logic for Computer Science. Springer-Verlag, London, 2001. Michael R. Genesereth, Nils J. Nilsson: Logical Foundations of Articial Intelligence. Morgan Kaufmann Publishers, Inc., Los Altos, California, 1987. Zbigniew Huzar: Elementy logiki dla informatykw. Ocyna Wyawnicza Politechniki Wrocawskiej, Wrocaw, 2007. Peter Jackson: Introduction to Expert Systems. Addison-Wesley, Harlow, England, 1999. Antoni Ligeza: Logical Foundations for Rule-Based Systems. Springer-Verlag, berlin, 2006.
    A Ligeza (AGH-UST) Essential Thinking 2011 4 / 26

    What is worth learning?


    A bit provocative position statement

    Languages enable communication and knowledge representation; Wieviel Sprachen du sprichst, sooftmal bist du Mensch; Goethe Problem Solving analytical thinking; cross-curricular competencies, Learning persistent learning, quick learning, focused learning, learning on-demand, ...

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    5 / 26

    Assumptions
    About the course in Polish, blackboard back in use, building permanent foundations for the future, not overformalized, examples, examples, examples, methods and tools, full comprehension, important: methods and search not the nal solution, independent work; individual thinking, https://www.ai-class.com/
    A Ligeza (AGH-UST) Essential Thinking 2011 6 / 26

    STUDENT CONDUCT POLICY: Stanford Standards


    AI Course: Stanford Standards
    To the extent a Student is registered as a student in an accredited institution or educational institution with its own policy regarding student conduct or an "honor code," those terms shall apply to any such Student. Additionally, unless the following conicts with such a policy or honor code, a Student of the Online Course agrees that he or she: will not harass other Students, Attendees or Visitors; will not cheat on any homework assignment or exams for the Online Course; will not post any of the course materials online; will not share content or solutions to homework assignments or exams; and will notify the instructors immediately if he or she becomes aware of any other Student cheating or breaching the Terms of Use.
    A Ligeza (AGH-UST) Essential Thinking 2011 7 / 26

    Thinking What is the Essence of it?

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    8 / 26

    Thinking = Reasoning Intelligence = Problem Solving


    Some inspiring questions
    What is the essence of thinking? How is it performed? Does only man think? What about animals and machines? What is the essence of intelligence? Can one learn/improve intelligence? Measure/evaluate? Can we have intelligent machines? More intelligent than people?

    Some practical questions


    What is the essence of reasoning? How is it performed? What is knowledge? Can it be measured/evaluated? Relationship between knowledge and intelligence? What is a problem? A solution? How to represent and process knowledge? Methods of reasoning? Caneza (AGH-UST) mechanical intelligence? A Lig we have Essential Thinking
    2011 9 / 26

    Analytical thinking vs. brute search The spoiled chessboard problem

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    10 / 26

    Lessons learned

    Analytical thinking problem solving


    basic problem solving method is search, a stable search space must be dened, a search method is necessary, decomposition is power! appropriate formalizm is power! heureka: important, but how does it work?

    Analytical Thinking

    Brute Search

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    11 / 26

    Another Example: Four-Digit Palindrom Case


    Four Digit Palindrom
    a four digit palindrom: 1221, 7337, 2992,... observe: 1221:11=111, 7337:11=667, 2992:11=272,... Hypothesis: Every four-digit palindrom numebr is divisible by 11.

    Analytical thinking vs. brute search


    is the hypothesis true or not? try several examples; try to invent a counterexample, try to induce regularity or chcek all cases? proove or disprove!

    Analytical Thinking
    A Ligeza (AGH-UST)

    Essential Thinking

    Brute Search
    2011 12 / 26

    Another Example: The Zebra Puzzle


    a) b) c) d) e) f) g) h) i) j) k) l) m) n) o) Norweg zamieszkuje pierwszy dom; Anglik mieszka w czerwonym domu; Zielony dom znajduje sie po lewej stronie domu biaego; Dunczyk pija herbatk e; Palacz Rothmansw mieszka obok hodowcy kotw; Mieszkaniec ztego domu pali Dunhille; Niemiec pali Marlboro; Mieszkaniec srodkowego domu pija mleko; Palacz Rothmansw ma sasiada, ktry pija wode; Palacz Pall Malli hoduje ptaki; Szwed hoduje psy; Norweg mieszka obok niebieskiego domu; Hodowca koni mieszka obok ztego domu; Palacz Philip Morris pija piwo; W zielonym domu pija sie kawe.
    Essential Thinking 2011 13 / 26

    A Ligeza (AGH-UST)

    Lessons learned

    Analytical thinking problem solving


    basic problem solving method is search; but: combinatorial explosion! a stable search space must be dened; but: how to choose it? a search method is necessary; perhaps computer can help? decomposition is power! But often it does not work! appropriate formalizm is power! Readable to computers... heureka: important, but how does it work? Maybe systematic approach?

    Analytical Thinking

    Brute Search

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    14 / 26

    Goals of the Lecture. And Its Contents


    Goals: Where are we going?
    glorication of Intelligent Thinking; demonstrating the power of IT, improving analytical thinking; cross-curricular competencies; building permanent foundations, elimination of thoughtlessness, learning problem solving, introduction to P ROLOG, search for M.Sc., Ph.D.???

    By what methods?
    examples, examples, examples, critical analysis, stating right questions, search for answers, taxonomy of problems, taxonomy of methods; tools and their application.
    A Ligeza (AGH-UST) Essential Thinking 2011 15 / 26

    Problem Solving - what is necessary?

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    16 / 26

    A Generic Problem Example http://freeweb.siol.net/danej/ riverIQGame.swf

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    17 / 26

    Problem Solving - what is necessary?


    A word on toolkit
    language its roles, knowledge representation formalism, knowledge processing tools operators, problem statement, search space; state-space, constraints, heuristics, search strategy; memory vs. repeated search, domain ontology, the goal explict (exact state) or implicit (criterion), path to the goal vs. nal solution.

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    18 / 26

    Inconsistency Fascinating and Inspiring

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    19 / 26

    Problem Solving - some questions to be raised


    About the problem and solution
    does any solution exist? is the solution unique? should we search for the rst solution or all of them? can the solutions be compared/evaluated? should we search for satisfactory or optimal solution? is the optimal solution unique? does an optimal solution exists? Pareto optimal solutions?

    About solutions
    candidate solution, admissible solution, legal solution, satisfactory solution, semi-optimal, -optimal, cgdominant solution, optimal solution.
    A Ligeza (AGH-UST) Essential Thinking 2011 20 / 26

    Lessons learned

    Analytical thinking problem solving


    basic problem solving method is search; but: combinatorial explosion! a stable search space must be dened; but: how to choose it? a search method is necessary; perhaps computer can help? decomposition is power! But often it does not work! appropriate formalizm is power! Readable to computers... heureka: important, but how does it work? Maybe systematic approach?

    Analytical Thinking

    Brute Search

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    21 / 26

    Three generic examples

    A cryptoarithemtic problem

    SEND + MORE -----MONEY

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    22 / 26

    Three generic examples

    Towers of Hanoi

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    23 / 26

    Three generic examples


    Missionaries and Cannibals

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    24 / 26

    Contents proposal
    1 2 3

    Tools: P ROLOG. Taxonomy of problems. Overview of methods. Search: Backtrack Search, DFS, BFS, UC, ID, IDS; Greedy Search, A*, IDA*, ... Inference: deduction, abduction, induction, case-based, rule-based,... Fuzzy sets, fuzzy logic. Multiple-Valued logics. Paradoxes. Inoconsitency and paraconsistency. Dealing with inconsistency. AND-OR search, games, Min-Max, Alpha-Beta,... Plan generation, robot world modeling. Constraint Programming, Constraint Logic Programming, Constraint Propagation. Diagnostics. Consistency-Based Reasoning.

    4 5

    6 7 8

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    25 / 26

    Prolog

    A Ligeza (AGH-UST)

    Essential Thinking

    2011

    26 / 26

    You might also like