Едва ли има друга технология, която променя нашето ежедневие толкова бързо и необратимо, както компютъра. Изследвайки методите и техниките, които правят възможен съвременния дигитален свят, тя доставя природно-научния фундамент на компютърните технологии.
Респективно, уникалната еволюция на компютрите е тясно свързана с развитието на информатиката. Със същата скорост, с която компютрите превземат света, информатиката – от частична дисциплина на математиката и електротехниката – се превръща в самостоятелна базова наука.
Теоретична информатика.
Изследва абстрактните концепции и методи, които правят възможно изграждането на съвременните компютърни системи. Произхожда директно от математиката, като възниква в началото на 20-ти век в дълбочината на кризата на основите на хилядолетната математика. Предоставя солидна научна основа за останалите области на информатиката.
Основни тематични области на съвременната теоретична информатика:
- Логика и дедукция – област на математиката, занимаваща се с основополагащи проблеми на математическите теории. Основно изследва формалните системи (калкюли);
- Формални езици – теорията на формалните езици разглежда анализа, класификацията и изграждането на изкуствените езици. Теорията предоставя методи и техники за работа със съвременните езици за програмиране и построяване на съответните компилатори;
- Теория на автоматите – изследва абстрактни модели за анализ и синтез на системи със състояния;
- Теория на изчислимостта – теорията изследва съществуването на алгоритми и алгоритмичната решимост на проблемите;
- Теория на комплексността – занимава се с квантитативни изследвания на свойствата на стратегиите за решения.
Машина на Тюринг.
Най-старият и същевременно най-експлоатираният модел за формално представяне на понятието „изчислимост“. Предложен през 1936 г. от Алън Тюринг (носещ неговото име). Машината на Тюринг изпълнява във всяко отношение изискванията за един формален модел, с помощта на който могат да се формулират математически прецизни твърдения за изчислимостта. Същевременно, притежава вътрешна простота и яснота, доставяйки изненадващо интуитивен достъп до тази сложна материя.
Криза на основите
В 18-ти век математиката вече е развита наука, но това не е абстрактната наука, която познаваме днес. Твърдо закотвена в реалния свят, тя се развива основно посредством постановка на проблеми от физически наблюдения. Числата са не повече от мерки за реални обекти – далеч от нематериалните абстрактни структури на модерната теория на числата. През 19-ти век визията постепенно се променя в посока на абстрактната математика. Числата и символите се отделят от физическата им интерпретация – те стават все по-абстрактни величини. В основополагащото си мулениум слово пред международния конгрес на математиците в Париж през 1900 г., Давид Хилберт дава сериозен тласък на развитието на математиката като абстрактна наука.
JFLAP (Java Formal Languages and Automata Package)
Графична среда, която може да се използва като помощно средство в усвояване на базовите концепции на теоретичната информатика – формални езици и граматики, крайни автомати, машини на Тюринг, Л-системи. Разработването на средата започва около 1990 г. в Rensselaer Polytechnic Institute под ръководството на Сюзън Роджър. От 1994 г. проектът се развива и поддържа от Duke University. JFLAP е подходяща за реализиране на интерактивни форми на обучение.
Л-Системи
Л-системите са специален вид граматики, които демонстрират възможностите за използването на формални средства за моделиране. Наречени са на името на техния създател - унгарския биолог Aristid Lindenmayer (1925-1989). Първоначално те са предназначени за моделиране на биологически системи. Все повече се използват в компютърната графика и дизайн.
